Binary
Search Tree merupakan salah satu struktur data yang mendukung proses searching
lebih cepat, penyortiran yang cepat, serta kemudahan dalam penyisipan dan
penghapusan. BST juga disebut dengan versi binary tree yang tersortir. Setiap
node memiliki key yang berbeda.
Keunikan
BST adalah node-node yang masuk sudah tersortir menjadi 2 bagian, yaitu subtree
kiri dan subtree kanan. Pada bagian paling atas merupakan akar. Subtree kiri
berisi elemen-elemen yang lebih kecil dari akar/root, sedangkan subtree kanan
berisi elemen-elemen yang lebih besar dari root. Node masuk akan disortir
dengan cara tadi. Node yang lebih kecil akan disimpan di sebelah kiri, dan jika
masuk lebih dalam akan tetap di sebelah kiri, begitu juga node yang lebih besar
akan selalu masuk ke subtree yang kanan. Hal ini untuk mempermudah pencarian
data, serta penyisipan dan penghapusan data.
Operasi-operasi
pada BST:
·
find(x) : untuk mencari x dalam BST
·
insert(x) : untuk menyisipkan x baru ke
dalam BST
·
remove(x): menghapus x dari BST
Seperti
yang telah dikatakan sebelumnya bahwa BST mendukung proses pencarian yang
mudah, mari kita coba mencari node, kita sebut X.
a Dimulai
dari root, jika root berisikan key yang kita cari (X), maka pencarian berhasil
b Jika
X lebih kecil dari root, maka lakukan pencarian secara rekursif di sebelah kiri
root, jika lebih besar maka lakukan pada sebelah kanan root.
Untuk
melakukan penyisipan (Insertion) juga dilakukan metode rekursif.
a. Dimulai
dari root
b. Jika
key X yang ingin kita masukkan lebih kecil dari key pada node, maka key X
dimasukkan ke subtree kiri, jika lebih besar, dimasukkan ke subtree kanan.
c. Ulangi
langkah b sampai ada node kosong, kemudian insert
Untuk proses penghapusan (Deletion), kita perlu
memperhatikan hal berikut.
50
/ \
20
75
/ \ \
10 30 80
·
Jika key yang ingin dihapus berada di dalam
leaf (node yang tidak memiliki child/anak), maka node dapat dihapus langsung.
Contoh: delete(10) à
key 10 akan lenyap
·
Jika key tersebut berada di dalam node
yang memiliki 1 anak, maka hapus node tersebut dan hubungkan/copy child-nya ke parent-nya.
Contoh: delete(75) à
copy key 80 ke node 75 à hapus key 75
50
/ \
20
75 (diganti jadi 80)
/ \ \
10
30 80 (dihapus)
·
Jika key tersebut berada di dalam node
yang memiliki 2 anak, cari anak yang paling kanan
dalam subtree kiri (kita
sebut node Q, dan key tersebut merupakan key paling besar). Kemudian ganti key
tersebut dengan key pada node Q secara rekursif.
Contoh: delete(50) à anak paling kanan di subtree kiri adalah 30 à
pindahkan ke node yang ingin dihapus, kemudian ganti key 50 menjadi 30 à
lakukan secara rekursif.
50
/ \
20
75
/ \ \
10 30
80
↓
30 (50 terhapus)
/ \
20
75
/ \
10 80
No comments:
Post a Comment