SESSION – 5
Binary Search Tree
Adalah sebuah sebuah tree yang memiliki kelebihan dari structure data yang lain. BST (Binary Search Tree) digunakan untuk menulusuri/mencari (searching) dan melakukan proses pengurutan (sorting). Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, Update, dan delete.
BST memiliki beberapa operasi antara lain :
- Insert(x) = sebagai operasi untuk memasukkan node x ke dalam BST
- Update(x) = sebagai operasi untuk mengupdate node x di dalam BST
- Delete(x) = sebagai operasi untuk menghapus node x dari BST
- Insert
Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).
- Update
Seperti pada Binary Tree biasa, namun disini update akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.
- Delete
Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.
BST Memiliki Sifat – sifat :
- Setiap simpul memiliki nilai
- Sub pohon kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.
- Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.