Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Binary Search Tree memiliki beberapa operasi misalnya :
- Searching : Pencarian dalam binary search tree
untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses
iterative. Langkah pertama dalam pencarian ialah dengan melakukan identifikasi
root node. Bila root node null maka key yang dicari tidak ada. Sebaliknya bila
root tersebut exist, maka langkah selanjutnya ialah membandingkan nilai key
dengan node root tersebut. Bila nilai root node sama seperti key yang dicari,
maka nilai root node tersebut akan dikembalikan sebagai hasil. Bila nilai key
lebih kecil dari node, maka pencarian diarahkan ke subtree di sisi kiri dari
node, proses ini dilakukan terus berulang hingga key ditemukan. Sebaliknya bila
nilai key lebih besar dari node, maka langkah selanjutnya ialah memilih subtree
di sisi kanan node tersebut. Dalam kasus terburuk, pencarian ini akan mencapai
ujung subtree terjauh dari root, atau setara dengan tinggi dari tree tersebut.
- Insertion Proses insertion (memasukkan suatu data)
dilakukan mulai secara bersamaan dengan proses pencarian data. Bila key tidak
sesuai dengan nilai yang ada di root, pencarian dilakukan ke subtree kanan atau
kiri. Hingga berada pada node luar, untuk kemudian dilakukan penambahan data
key baru. Dengan kata lain dilakukan proses pemeriksaan root dan secara
recursive memasukkan suatu node baru di sisi kiri bila nilainya lebih kecil,
atau di sisi kanan bila nilainya lebih besar (atau bisa juga sama besar)
dibandingkan dengan nilai dari root tersebut.
- Deletion : Terdapat beberapa aturan dasar yang perlu
diperhatikan dalam langkah menghapus suatu node, yakni.
1. Bila node tersebut tidak memiliki child, node tersebut
dapat langsung dihapus
2. Bila node tersebut memiliki child, maka node (parent)
tersebut dihapus dan child dari node tersebut menggantikan posisi dari node
parent
3.Bila node tersebut memiliki dua children, maka langkah
pertama yang dilakukan ialah mengganti nilai node parent dengan salah satu
child, hapus nilai node parent awal, secara recursive hapus nilai node child
yang telah digunakan untuk mengganti nilai node parent sebelumnya, kemudian
lakukan seperti pada kasus pertama atau kedua
Suatu node dengan children, lebih sulit untuk dihapus.
Bila node child lebih besar dari node parent yang digantikan maka disebut
in-order successor. Sebaliknya bila node child lebih kecil dari node parent
yang digantikan, maka disebut in-order predecessor.
Referensi :
Binusmaya
