Dari permasalahan diatas tentunya dapat kita simpulkan bahwa alangkah baiknya jika kita dapat melakukan operasi pencarian dengan kecepatan eksekusi tinggi (seperti pada tabel kontigu dan pencarian biner) dan operasi penambahan dan penghapusan dengan kecepatanek sekusi tinggi (seperti pada senarai berkait).Disinilah keunggulan Binary Search Tree akansangat berguna,dimana Binary Search Treedapat menjadi solusi permasalahan tersebut karena pencarian serta penambahan dan penghapusan elemennya memiliki kecepatan eksekusi yang tinggi. Operasi pencarian, penambahan, dan penghapusan pada Binary Search Tree memiliki run-time O (log n).
Misalkan kita memiliki int arr[] = {70, 60, 30, 50, 40,20}, data para int arr harus diurutkan terlebih dahulu menggunakan teknik sorting seperti bubble sort. Sehingga array kita akan menjadi int arr[] = {20,30,40,50,60,70}. Apabila angka yang dicari adalah angka 40, berikut gambaran dari implementasi BinarySearch:
1stCycle:
(20,30,40,50,60,70)
LOW=0
HIGH=N
MID=(LOW+HIGH)/3
(arr[MID]==40)
(20,30,40,50,60,70)(50==40)//FALSE
HIGH = MID-1
*Array di mulai dari index ke 0, maka index ke 3 berisi nilai 50.
2ndCycle:
(20,30,40,50,60,70)
MID = (LOW + HIGH)/2= (0+2)/2=1
(arr[MID]==40)
(20,30,40,50,60,70)
(30==40)//FALSE
LOW = MID+1
3rdCycle:
(20,30,40,50,60,70)
MID=(LOW+HIGH)/2=(2+2)/2+2
(arr[MID]==40)
(20,30,40,50,60,70)
(40==40) // TRUE
Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.
Berikut implementasi dari Binary Search menggunakan Bahasa C:
Binary Search Tree adalah sebuah pohon biner yang mempunyai properti tambahan. Properti ini adalah :
Semua elemen pada upapohon (subpohon) kiri nilainya lebih kecil atau sama dengan nilai akar.
Semua elemen pada upapohon kanan nilainya lebih besar dari nilai akar.
Upa pohon kiri dan kanan merupakan Binary Search Tree.
Terdapat 3 operasi yang sangat mendasar dan juga sangat penting pada binary search tree yaitu operasi pencarian, penambahan, dan penghapusan elemen. Ketiga operasi tersebut merupakan operasi yang sangat mendasar yang harus ada pada setiap struktur penyimpanan data.
Untuk melakukan operasi pencarian pada Binary Search Tree, pertama-tama kita bandingkan dahulu kunci data yang ingin kita cari dengan kunci dari data akar, jika tidak cocok maka cari pada upapohon kiri atau kanan sampai kunci data yang ingin dicari cocok.Berikut sketsa kasar algoritma operasi pencarian pada Binary Search Tree : Algoritma Cari Simpul (kunci K, pohon P) Jika pohon P kosong kembalikan nilai NULL (tak terdefinisi). Jika kunci K cocok dengan kunci akar t maka kembalikan simpul P. Jika kunci K > kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kanan (P) ) Jika kunci K <= kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kiri(P).
