Binary Search Tree (BST)

Binary Search Tree adalah data struktur binary tree yang node yang berada di kiri key – nya lebih kecil daripada node diatasnya, dan yang berada di kanan key – nya lebih besar daripada node diatasnya. Node yang berada di kiri dan kanan subtree juga harus menjadi binary search tree jika dari node diatas mereka merupakan binary search tree.

Untuk mencari dalam sebuah binary search tree, dapat dilakukan dengan membandingkan dengan root yang ada. Jika key yang dicari sama dengan root, maka program akan me – return root. Jika key yang dicari lebih besar, maka kita akan menggunakan recursif untuk mencari key pada bagian kanan root, dan jika key yang dicari lebih kecil daripada root, kita akan menggunakan recursif untuk mencari key pada bagian kiri root.

Untuk memasukkan sebuah key dalam sebuah binary search tree, kita akan selalu menambahkan key baru sebagai sebuah leaf dalam binary search tree. Kita akan mencari sebuah node yang merupakan sebuah leaf, dan saat leaf tersebut ditemukan, atau memang data yang ada baru hanya ada root, kita akan perlu menentukan lokasi key baru akan berada dikanan atau kiri leaf yang ditemukan.

Untuk menghapus sebuah key dalam sebuah binary search tree, terdapat 3 kemungkinan yang dapat terjadi. Yang pertama adalah data yang ingin dihapus terletak pada leaf. Maka kita hanya akan perlu menghapusnya. Jika data yang ingin dihapus memiliki 1 anak, maka anak yang dimiliki data tersebut akan menggantikkan posisinya. Jika data yang ingin dihapus memiliki 2 anak, maka kita dapat memilih key paling besar dari anak yang berada dikiri data tersebut atau key paling kecil dari anak yang berada dikanan data tersebut.

Berikut coding untuk delete dalam binary search tree. (menggunakan data terkecil dari anak yang berada dikanan)

Sumber:

https://www.geeksforgeeks.org/binary-search-tree-data-structure/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/