Binary search tree merupakan binary tree yang sudah tersortir. Kebanyakan Binary Search Tree menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.
Binary Search Tree mempuyai beberapa operasi dasar yaitu :
•>Find : Fungsi untuk mencari angka di dalam sebuah Binary Search Tree. Dilakukan dengan fungsi rekrusif dari root sampai meneukan angka yang kita inginkan. Konsepnya adalah dimulai dari root, jika root merupakan angka yang kita cari, return root. Jika angka yang kita cari lebih kecildaripada root, rekrusive fungsi ke subtree sebelah kiri. Jika angka yang kita cari lebih besar dari root, rekrusive fungsi ke subtree sebelah kanan.
•> Insert : Fungsi untuk menambahkan suatu node dari sebuah Binary Search Tree. Dilakukan dengan fungsi rekursif dari root dan key yang akan dimasukkan. Konsepnya adalah dimulai dari root jika key lebih kecil dari root maka, akan berpindah ke subtree sebelah kiri root dan jika lebih besar dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kanan dari subtree sebelah kanan root dan jika lebih kecil dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kiri dari subtree sebelah kiri root. Jika berpindah ke elemen yang masih kosong maka akan dipush kedalam tree.
•> Remove : Fungsi untuk menghapus suatu node dari sebuah Binary Search Tree. Dilakukan dengan mencari data yang akan dihapus dalam tree. Jika sudah dihapus maka, yang akan menggantikan data yang dihapus adalah:
1. Jika data yang dihapus adalah parent dengan single children maka, yang akan menggantikannya adalah childrennya.
2. Jika data yang dihapus adalah leaf maka, langsung dihapus saja.
3. Jika data yang dihapus adalah parent dengan 2 children maka, yang akan menggantikannya adalah subtree sebelah kanan nya yang paling kiri atau subtree sebelah kiri yang paling kanan tergantung dengan pembuat treenya.
Tidak ada komentar:
Posting Komentar