Binary Search Tree

Binary Search Tree

Binary Search tree adalah data structure Binary Tree yang sudah di sort sehingga mendukung searching yang lebih cepat dan juga insertion dan deletion yang lebih mudah.

 

Diatas adalah contoh binary search tree. Dapat dilihat binary search tree sudah di sort. Elemen di kiri selalu yang lebih kecil dan elemen yang dikanan selalu lebih besar.

Dalam binary search tree terdapat 3 operasi dasar yaitu:

           1. Find atau Search: yaitu mencari sebuah elemen dalam binary search tree

           2. Insert atau Push: Yaitu memasukkan sebuah elemen ke dalam binary search tree.      

           3. Remove atau Pop: yaitu menghapus sebuah elemen dalam binary search tree.

      Operasi Find:
Karena Binary search tree sudah di sort maka pencarian sebuah elemen menjadi lebih mudah dan cepat.

Langkah-langkah operasi Find:

           1. Operasi find dimulai dari node berada di akar binary search tree

     2. Lalu memeriksa apakah elemen pada node adalah elemen yang dicari, jika iya maka operasI

         find berakhir jika tidak maka akan lanjut ke langkah berikutnya.

           3. Jika elemen lebih kecil dari pada elemen pada node maka akan mencari secara rekursif pada

               subtree bagian kiri. Jika elemen lebih besar maka akan mencari secara rekursif pada subtree 

               bagian kanan.

      Operasi Insert:

      Insert pada binary search tree dilakukan secara rekursif karena insert elemen baru yang lebih kecil harus dikiri dan harus kosong nodenya sedangkan yang lebih besar harus di kanan dan juga harus kosong.

Langkah-langkah operasi Insert:

      1. Operasi Insert dimulai dari node berada di akar binary search tree

            2. Jika elemen yang ingin dimasukkan lebih kecil daripada elemen pada node maka nodeakan     

                ke subtree kiri secara rekursif, jika lebih besar maka node akan ke subtree kanan secara

                rekursif.

            3. Hal tersebut dilakukan sampai menemukan node yang kosong. Lalu memasukkan elemennya 

                disana.

      Berikut adalah ilustrasi insert pada Binary Search Tree

 

  

Insert 1

Insert 2

 

 

 

Insert 3

 





 Insert 4

Insert 1: Node dimulai dari akar karena elemen yang ingin dimasukkan lebih besar maka ke subtree kanan.

Insert 2: Karena node yang sekarang elemennya lebih besar dari pada elemen yang ingin dimasukkan maka ke subtree kiri.

Insert 3: Karena node yang sekarang elemennya lebih kecil dari pada elemen yang ingin dimasukkan maka ke subtree kanan.

Insert 4: Karena nodenya kosong maka dimasukkan disana elemennya.

 

 

Operasi Delete:

Delete pada binary search tree terdapat 3 kasus yaitu:

J           1. Jika node yang ingin didelete adalah daun dari binary search tree tersebut. Maka bisa langsung didelete.

             2. Jika node yang ingin didelete memiliki 1 child maka child tersebut harus dihubungkan ke 

                 pada parent node yang ingin didelete. Lalu baru mengdelete node tersebut.

             3. Jika node yang ingin didelete memiliki 2 child maka kita harus mencari elemen terbesar pada 

                 subtree kiri atau elemen terkecil pada subtree kanan (yang akan kita akan sebut elemen X) 

                 lalu mengantikan elemen node yang ingin didelete tersebut dengan elemen X dan menghapus 

                 node X.

        Berikut adalah ilustrasi Delete pada binary search tree

 

 

 

 Delete 1

 Delete 2

Delete 1: Node yang ingin didelete memiliki 2 child maka pada kasus tersebut ia memilih elemen terbesar pada subtree kiri (elemen X).

Delete 2: Lalu node yang ingin didelete diberikan elemen X kemudian Node X dihapus