Langsung ke konten utama

Binary Search Tree

Pengertian Binary Search Tree

Binary search tree adalah sebuah metode dari data structure yang mempunyai ciri sebagai berikut:

  1. Bagian kiri dari subtree adalah nodus yang mempunyai nilai yang lebih kecil
  2. Bagian kanan dari subtree adalah nodus yang mempunyai nilai yang lebih besar
  3. Bagian kiri dan kanan dari subtree harus berupa binary search tree juga

Mencari Sebuah Angka (searching)


200px-Binary_search_tree.svg

Ilustrasi Binary Search Tree dari geeksforgeeks

Bisa kita lihat dari contoh diatas, bagian kiri dari binary search tree merupakan nilai yang kecil sedangkan bagian kanannya adalah nilai-nilai yang besar.

Kita bisa mengambil contoh angka 7. Ketika angka 7 ingin dicari pada binary search tree diatas, maka dia akan mengecek. Apakah 8 lebih kecil atau besar dari 7? Karena lebih kecil, maka 7 akan dicari di bagian kiri. Kemudian, akan dicek lagi. Apakah 7 lebih kecil daripada 3? Jawabannya adalah tidak, sehingga 7 dicari dibagian kanan. Lalu ketika sampai di 6, karena 7 lebih besar daripada 6, maka lokasi 7 pasti di kanan dari cabang si 6. Begitulah kira - kira cara kerja dari binary search tree. 

Memasukkan Sebuah Angka pada BST (insertion)

         100                               100
        /   \        Insert 5            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                     / 
                                    5

Coba kita lihat illustrasi ketika kita akan melakukan insertion pada binary search tree. Nah, pada contoh diatas, saya ingin memasukkan 5 pada binary search tree tersebut. Karena angka 5 lebih kecil daripada 100, maka saya akan menaronya di bagian kiri dari cabang 100. Lalu karena lebih kecil dari 20, saya taro lagi di bagian kiri dari 20. Nah ketika bertemu 10. otomatis 5 akan ditaro di kiri cabang dari 10 karena nilainya lebih kecil daripada 10.

Menghapus Sebuah Angka pada BST (delete)

Setelah kita mempelajari insertion, sekarang kita akan membahas tentang delete. Seperti namanya sendiri, kita akan menghapus angka yang ada di binary search tree sesuai dengan angka yang ingin dihapus. Kemungkinan dan cara dalam melakukan delete pada binary search tree adalah sebagai berikut:
1) Nodus yang ingin di hapus ada pada daun: Yaudah hapus aja langsung, gampang kan?
              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80
2) Nodus yang ingin di hapus hanya mempunyai satu cabang atau keturunan: Salin keturunannya lalu taro di tempat di mana angka tersebut di hapus.
              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80
3) Nodus yang ingin di hapus hanya mempunyai dua cabang atau keturunan: Cari keturunan di bagian kanan yang mempunyai nilai paling kecil. Dalam contoh ini, karena 60 lebih besar dari 50 dan kebetulan paling kecil di bagian kanan 50, maka angka ini naik jadi paling atas dan angka 50 dihapus.
             50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80

Sumber:



Komentar

Posting Komentar

Postingan populer dari blog ini

How do you get to the top of Mt Coronet in Pokemon Diamond?

Note: If you are going to try to catch Dialga or Palkia (diamond or pearl) make sure you have a bunch of Ultra and Dusk balls!! First, Fly to Hearthome city and head west, Route 208. Enter the cave and once inside, you should go north.When you first enter the cave, you need to head west to the opposite side. Once you reach the west entrance, head north and surf across the pond. Use rock climb to reach the stairs up. In the next room: Go- North, West, South, Upstairs, North, West over bridge, down stairs, up north, stairs,up stairs, cross bridge, down stairs, down stairs, upstairs and in cave door. In the Next room: Up stairs, up stairs Again Next room: up stairs, north, west, south, Out. Now you are outside. Follow the path and use rock climb when you get there. Now don't use rock climb again, instead, head west and through the grass until you reach another cave. Inside, use rock climb, follow the path, down the stairs then east, you're out of the cave. ...
Posting Komentar
Baca selengkapnya

Heaps & tries

Heap Minggu lalu kita sudah membahas AVL Tree dan sekarang kita akan membahas Heap & Tries. Heap adalah sebuah struktur data dengan konsep binary tree. Heap mempunyai dua jenis yaitu: Min - heap Max - heap Min - Max heap Heap dapat diimplementasikan dengan linked list, namun akan lebih gampang jika menggunakan array. Agar lebih jelas, lebih baik kita lihat gambar berikut ini. Heap dari geeksforgeeks Min - Heap Pada min - heap terdapat aturan agar heap itu dapat dibuat. Aturan tersebut adalah angka atau huruf yang ada di root harus paling kecil daripada anak - anaknya. Hal ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih kecil daripada bawahnya. Insertion Berbeda dengan BST yang mempunyai aturan kiri harus yang kecil dan kanan yang besar, min - heap hanya menghiraukan atasnya. Pada kasus min - heap berarti atasnya harus lebih kecil daripada bawahnya. Agar kita mengerti cara menginsertnya, lihat gambar berikut: Kita ak...
Posting Komentar
Baca selengkapnya