Binary search tree (BST) merupakan struktur data bersifat hirarkis yang menggunakan node sebagai dasarnya, seperti halnya pada linked list. BST ini digunakan untuk Fast Searching, Rapid Sorting, Easy Insertion, dan Deletion Data. Dalam BST, tiap node hanya boleh memiliki maksimal dua sub-tree dan kedua subtree tersebut harus terpisah. Subtree sebelah kiri akan memiliki node yang nilainya lebih rendah daripada parent node, sedangkan sebelah kanan berisikan node yang memiliki nilai lebih tinggi daripada parent node.
Insertion
Memasukkan sebuah nilai baru kepada binary tree akan selalu masuk ke bagian paling bawah. Dimulai dengan mencari nilai root sampai ke leaf node, dan jika nilai yang dimasukkan lebih kecil dari leaf node, maka angka yang dimasukkan akan berada di sebelah kiri leaf node, berlaku sebaliknya dengan nilai yang lebih besar.
Searching
Dalam mencari suatu nilai pada BST, akan dilihat dan dibandingkan dengan nilai pada root. Bila nilai yang diinginkan sama dengan nilai pada root, makan root adalah nilai yang dicari. Namun jika yang dicari lebih kecil, makan akan mencari pada subtree disebelah kiri node root. Berlaku sebaliknya, jika nilai yang dicari lebih besar daripada root, maka akan mencari pada subtree sebelah kanan dari node root.
Deletion
Ada beberapa kondisi didalam melakukan Deletion pada BST :
- Jika node yang akan dihapus adalah leaf node, makan dapat langsung menghapus leaf node tersebut.
- Jika node yang dihapus hanya memiliki 1 subtree, child node ini akan dicopy ke node yang akan dihapus, baru dilakukan deletion.
- Jika node yang akan dihapus memiliki 2 subtree, dapat dilakukan dengan 2 cara, yaitu dengan mengambil nilai maksimum dari sebelah kiri, atau dengan nilai minimum pada subtree sebelah kanan..
Sumber :
No comments:
Post a Comment