Binary Search Tree

BST (Binary Search Tree) adalah Tree yang bisa mempercepat pencarian, sorting data dengan tepat, memiliki kemudahan entri data dana penghapusan data. BST adalah binary tree namun memiliki kemampuan auto sorting.

BST pada anak kiri memiliki nilai yang lebih kecil daripada parentnya dan pada anak kanan memiliki nilai yang lebih besar dari parentnya.

1. Searching
Pencarian data mudah karena hanya perlu membandingkan data dengan root terlebih dahulu, jika lebih kecil maka akan lanjut pencarian ke kiri, dan apabila lebih besar dari root, maka melakukan pencarian ke kanan.

2. Insertion
Memulai memasukkan data dari root terlebih dahulu, apabila kosong maka data pertama akan menjadi root. dan sama halnya apabila data selanjutnya lebih kecil dari root maka data baru akan dibuat di sebelah kiri root, dan apabila data selanjutnya lebih besar dari root maka data baru akan dibuat di sebelah kanan root. Lakukan terus sampai menemukan node kosong yang bisa ditimpa dengan data baru.

3. Deletion
Jika data terdapat pada ujung tree (leaf), maka langsung hapus saja. Apabila memiliki 1 anak, tinggal sambungkan ke parent si data yang akan dihapus. Jika memiliki 2 anak, carilah data yang tepat untuk menggantikan data yang akan di delete, bagaiman mendapatkannya ? yaitu dengan melakukan pencarian data dari bagian kiri root lalu ke kanan sampai ditemukan data paling ujung (predecessor) atau bisa juga dengan melakukan pencarian data dari bagian kanan root lalu ke kiri sampai ditemukan data yang paling ujung (successor) kemudian replace data yang akan dihapus dengan data tersebut.

Namun dari semua advantage yang dimiliki BST, ada bagian dimana BST bisa menjadi tree yang sama saja seperti linkedlist biasa, misalkan akan mengisi data 1,2,3,4,5. apabila data pertama yang masuk 1 maka root = 1, dan 2,3,4,5 akan berada di bagian kanan dari root. Tidak ada bedanya dengan LinkedList, padahal tujuan dari BST sendiri agar mempermudah pencarian data. Nah hal ini disebut dengan Skewed Tree (kekanan terus / kekiri terus).

Sekian pembahasan teori mengenai BST, jika ada yang mau ditanyakan seputar BST, silahkan comment.
Thank you~