Binary Search Tree sendiri adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.
Sub Topics
- Operations: Search, Insertion, Deletion
- Program Example
- Expression Tree Concept
- Create Exp. Tree from prefix
- Create Exp. Tree from postfix
- Create Exp. Tree from Infix
- Prefix, Postfix, Infix Traversal
1. Operations
Binary search tree memiliki beberapa basic operation:
- find(x) = search / cari "x" BST
- insert(x)= push / masukkan '"x" ke dalam BST
- remove(x) = pop / hapus "x" dari BST
- find(x) = search / cari "x" BST
- insert(x)= push / masukkan '"x" ke dalam BST
- remove(x) = pop / hapus "x" dari BST
Search:
Pencarian (Searching) dimulai dari rootnya (di gambar adalah angka 50).
Jika angka yang dicari belum ditemukan, maka pencarian akan
dilanjutkan, jika angka yang dicari lebih kecil dari root, maka
pencarian akan ke sebelah kiri root, jika sebaliknya maka akan dicari ke
sebelah kanan root. Begitu seterusnya samapi ditemukan angka yang
dicari.
Misal jika angka yang dicari adalah 23, maka pencarian akan dimulai dari:
Misal jika angka yang dicari adalah 23, maka pencarian akan dimulai dari:
- 23 != root, maka 23 dibandingkan dengan root
- 23 < 50, maka pencarian dilanjutkan ke sebelah kiri
- 23 != 17, maka 23 dibandingkan dengan 17
- 23 > 17, maka pencarian dilanjutkan ke sebelah kanan
- 23 == 23, maka pencarian telah berhasil dan selesa
Insertion
Data yang lebih kecil daripada root / parent,
diletakan di sebelah kiri.
Data yang lebih besar daripada root /
parent diletakan disebelah kanan.
contoh:
insert 35 kedalam BST. Maka 35 akan diletakan
di sebelah kanan 32. 
Deletion
Ada 3 cases yang harus diperhatikan:
- Jika kuncinya adalah leaf, hapus saja nodenya
-
Jika kuncinya adalah node yang hanya mempunyai
satu anak, hapus nodenya dan konek anaknya kepada orangtuanya.
-
Jika kuncinya adalah node mempunyai dua anak,
temukan anak yang paling benar yang mempunyai sub tree disebelah kiri, gantikan
kuncinya dengan kunci P’s dan hapus P secara recursive.
