Binary Search Tree

Christophorus Wilson Sucahyo

2301869273

Binary Search Tree (BST)

Binary Search Tree adalah struktur data yang memiliki searching dan sorting yang cepat, serta insertion dan deletion yang mudah.

Untuk node pada BST, node kiri akan bernilai lebih kecil dari parent nodenya sedangkan node kanan akan bernilai lebih besar dari parent nodenya (dengan asumsi bahwa key nya berbeda)

 

Pada BST, terdapat 3 basic operations :

-          find(x) : mencari key x di dalam BST

-          insert(x) : memasukkan key x ke dalam BST

-          remove(x) : menghapus key x dari dalam BST

Operation : Search ( find(x) )

-          Dimulai dari root

-          Jika x lebih kecil dari root, maka cari di subtree kiri

-          Jika x lebih besar dari root, maka cari di subtree kanan

 

Operation : Insertion ( insert(x) )

-          Dimulai dari root

-          Jika x lebih kecil dari value di node, maka lanjutkan pengecekan ke subtree kiri

-          Jika x lebih besar dari value di node, maka lanjutkan pengecekan ke subtree kanan

-          Ulangi (secara rekursif) hingga menemukan node kosong untuk x (x selalu menjadi leaf baru)

 

Operations : Deletion ( remove(x) )

-Jika x berada di leaf, maka node tersebut dapat langsung dihapus

-Jika x berada di node yang memiliki satu child, hapus node tersebut dan pindahkan value dari child ke parent

-Jika x berada di node yang memiliki dua child, maka cari child kanan dari subtree kiri, hapus value x, pindahkan value dari child menuju node x, dan hapus node child. (sebaliknya dapat mencari child kiri dari subtree kanan)

Gambar diatas adalah contoh x yang berada di leaf. Node tersebut dapat langsung dihapus.

Gambar diatas adalah contoh x yang memiliki dua child. Tentukan dulu subtree mana yang ingin kita gunakan. Pada contoh diatas kita menggunakan child kanan dari subtree kiri. Langkah pertama adalah hapus x, kemudian pindahkan nilai dari child node ke parent node.