05 - Binary Search Tree - 2101664883 - Joseph Lazarus Joshua Refassy

Binary Search Tree

Binary Search Tree adalah aturan dimana left child dari parent selalu memiliki nilai lebih kecil dari nilai parent dan right child selalu memiliki nilai lebih besar dari parent.

Binary Search Tree mempunyai beberapa operator dasar:
- find(x) : cari x dalam BST -> sama saja dengan search  <- menggunakan BST, search jadi mudah
- insert(x) : memasukkan x dalam BST
- remove(x) : menghapus x dalam BST

Aturan dalam Delete:
- Jika node adalah leaf, maka hapus saja
- Jika node yang ingin di delete masih memiliki anak setidaknya satu anak, maka delete saja node yang ingin di delete, lalu gantikan posisi yang di delete tadi dengan anak yang di delete.
- Jika node adalah parent yang memiliki dua anak, maka delete node yang ingin di delete, lalu cari pengganti untuk posisi node yang di delete. Cara carinya ialah lihat anak sebelah kiri lalu cari nilai node yang tertinggi dari sana, setelah itu gantikan nilai tertinggi dari node yang ada di left child dengan node yang telah di delete.

Berikut adalah contoh dari masing-masing operator dasar

Find (Search)

Insert

Step 1

Step 2

Step 3

Hasil

Remove (Delete)

Hapus (21)

Karena (21) tidak memiliki child alias leaf, maka hapus saja

Hapus (37)

Node dengan nilai tertinggi dari kiri Node yang ingin dihapus dijadikan pengganti

Hapus (30)

Nilai tertinggi dari left child yang akan dihapus menggantikan posisi yang akan dihapus