Binary Search Tree

BINARY SEARCH TREE

Binary search tree mirip seperti Binary tree pada umumnya, tetapi binary search tree memiliki ketentuan tambahan, yaitu di sebelah kiri pada suatu node harus selalu lebih besar / kecil  dan sebaliknya untuk yang di sebelah kanan node.

Seperti pada contoh diatas, angka paling atas (root) adalah 8 dan disebelah kiri 8 ada 3 yang merupakan angka lebih kecil dari 8. Dibawah 3 ada angka 1 di sebelah kiri 3 karena merupakan angka yang lebih kecil, dan di sebelah kanan 3 ada angka 6 yang merupakan angka lebih besar dari 3. angka di sebelah kanan 3 harus lebih besar dari 3 tetapi tidak boleh lebih besar dari 8, karena sudah termasuk dari bagian sebelah kiri angka 8 dimana semua yang di sebelah kiri 8 harus lebih kecil. Sama halnya di sebelah kanan 8 yang merupakan semua angka yang lebih besar dari 8.

BINARY SEARCH TREE OPERATION

INSERTION

Insertion adalah teknik binary search tree yang mau memasukkan data / menyisipkan data pada tree. Cara pada Insertion di BST (Binary Search Tree) pun berbeda dibanding binary tree biasa karena pada BST harus memperhatikan besar kecilnya nilai pada suatu angka.

Seperti pada gambar diatas, angka yang ingin dimasukkan adalah 7, maka program akan memeriksa apakah angka 7 lebih besar dari 8 (root) atau lebih kecil. Karena lebih kecil, dia pasti masuk ke bagian sebelah kiri dari angka 8. Lalu dicek lagi apakah 7 lebih besar dari 3. Karena lebih besar, maka angka 7 masuk ke sebelah kanan dari 3 dan begitu seterusnya sampai masuk ke bagian kanan sebelah angka 5.

DELETION

Ada 2 kasus dalam proses delete di BST. Kasus pertama adalah ketika node yang ingin dihapus adalah node yang paling bawah, Maka tinggal langsung delete saja node tersebut. Namun Ketika node tersebut memiliki child, maka ada beberapa kondisi yang harus dilihat agar Tree tersebut tidak berantakan.

Seperti pada gambar diatas, angka 20 adalah angka yang mau di delete. Sehingga cara yang akan digunakan adalah dengan melihat angka paling besar dari sebelah kiri 20 atau angka paling kecil dari sebelah kanan 20. Logikanya adalah dengan melihat angka paling besar di sebelah kiri 20 (seperti pada contoh) yaitu 19, sudah pasti angka 19 akan selalu lebih besar dari node-node di sebelah kiri 20 namun tetap lebih kecil dari node-node yang ada di sebelah kanan. Sehingga setelah menghilangkan angka 20, angka yang menggantikan tempat node angka 20 adalah angka 19.