Binary Search Tree
Pengertian
Sebelum masuk kedalam konsep Binary Search Tree, ada baiknya kita memahami konsep Tree itu sendiri. Tree adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (relasi one to many).
Lalu apa perbedaannya dengan Binary Search Tree? Binary Search Tree adalah tree yang memiliki maksimal 2 percabangan saja, dan terdapat beberapa aturan. Child node sebelah kiri selalu lebih kecil daripada root node. Child node sebelah kanan selalu lebih besar daripada rootnode. Binary Search Tree biasa dikenal sebagai Sorted Version of Binary Tree.
Seperti pada gambar diatas, root node adalah 50, child node seblah kiri adalah 17, dan child node sebelah kanan adalah 76. Ini artinya child node sebelah kiri selalu lebih kecil dibandingkan root, dan child node kanan selalu lebih besar daripada root.
Operasi Binary Search Tree
Insert:
- Selalu dimulai dari root.
- Jika angka yang akan dimasukkan lebih kecil daripada sub tree, maka cek sebelah kiri dari sub tree. Bila kosong masukkan angka tersebut.
- Bila angka yang akan dimasukkan lebih besar daripada sub tree, maka cek sebelah kanan dari sub tree. Bila kosong, masukkan angka tersebut.
- Lakukan terus sampai menemukan node yang kosong untuk ditaruh sebuah nilai.
Deletion:
Untuk melakukan delete terdapat 3 situasi.
- Bila yang ingin dihapus di bagian leaf, dapat langsung dihapus. Pada gambar diatas, 12 dapat langsung dihapus.
- Bila yang akan dihapus memiliki satu child, hapus node tersebut dan gabungkan antara parent node tersebut dan child dari node tersebut. Pada gambar diatas, bila 72 dihapus, maka 54 menjadi parent 67.
- Bila yang akan dihapus memiliki dua child, cari sub tree bagian kiri kemudian dibandingkan dengan yang kanan. Pada gambar diatas, apabila angka 17 dihapus maka, angka 14 akan naik menggantikan posisi 17, angka 9 akan menjadi parent 12. Bila angka 50 yang dihapus, maka angka 23 akan naik menggantikan posisi 50, dann17 akan menjadi parent 19.
Refrensi:
Binus Maya
No comments:
Post a Comment