Chrystopher's Blog

Sesi 5 :

Operasi Binary Search Tree (BST)
Binary Search Tree mempunyai beberapa operasi sederhana sebagai berikut.
1. find (x) : menemukan key X dalam BST.
2. insert (x) : memasukkan key X ke dalam BST.
3. delete (x) : menghapus key X dari BST.

Operasi : Search
1. Karena properti dari BST, menemukan/mencari dalam BST mudah.
2. Misalkan key yang ingin kita cari adalah X :
– Kita mulai pada root.
– Jika root mengandung X, maka pencarian berhasil.
– Jika X lebih kecil daripada key root maka lakukan pencarian secara rekursif pada sub tree kiri, jika tidak, lakukan pencarian secara rekursif pada sub tree kanan.

Operasi : Insertion
1. Insert (pemasukan) ke dalam BST dilakukan secara rekursif.
2. Misalkan node key baru adalah X :
– Mulai pada root
– Jika X lebih kecil dari node key, maka masukkan X ke dalam sub tree kiri, jika tidak, masukkan X ke dalam sub tree kanan.
– Ulangi hingga kita menemukan node kosong untuk meletakkan X (X akan selalu menjadi leaf baru)

Simulasi :

1

2

3

4

Operasi : Deletion
Ada 3 hal yang harus diperhatikan :
1. Jika key-nya berada dalam leaf, hapus saja node tersebut.
2. Jika key-nya berada dalam node yang memiliki satu child, hapus node tersebut dan hubungkan child-nya ke parent-nya.
3. Jika key-nya berada dalam node yang memiliki dua children, cari child paling kanan dari sub tree kiri (node P), ganti key-nya dengan key P dan hapus P secara rekursif. (atau alternatifnya, bisa memilih child paling kiri dari sub tree kanan).

Simulasi :

1.1

1.2

2.1

2.2

3.1

3.2