Binary Search Tree

Binary Search Tree (BST) adalah suatu bentuk struktur data yang menggambarkan hubungan antara elemen satu dengan elemen lainnya. Pada Binary Search Tree hanya dapat memiliki maksimal dua percabangan saja dan memiliki syarat nilai node di kiri harus lebih kecil dari node di kanan.

Keuntungan memakai Binary Search Tree :
1. Proses searching yang jauh lebih cepat
2. Proses sorting yang jauh lebih cepat
3. Mempermudah proses insertion dan deletion

Sebuah Binary Search Tree mempunya 3 fungsi yaitu:
1. Find
2. Insert
3. Remove

Fungsi Search :
1. Searching dimulai dari root, jika nilai x yang dicari, dan x berada di root, maka proses searching selesai
2. Jika nilai x lebih kecil dari root , maka proses searching rekursif ke sebelah kiri
3. Jika nilai x lebih besar dari root, maka proses searching rekursif ke sebelah kanan

Fungsi Insertion :
1. Dimulai dari root
2. Jika nilai x lebih kecil dari key , maka cek dengan sub tree bagian kiri secara rekursif, begitu juga sebaliknya.
3. Ulangi proses tersebut sampai menemukan node yang kosong, untuk insert nilai x

Fungsi Remove :
- Node tanpa child = node dapat langsung dihapus
- Node dengan 1 child = node child akan menggantikan posisinya
- Node dengan 2 child = node akan digantikan oleh node paling kiri dari sub tree kanan , atau dapat juga digantikan oleh child paling kanan dari sub tree kri


Sumber : Power Point Binusmaya