Pohon Pencarian Biner
Dalam ilmu komputer, sebuah pohon pencarian biner (PPB) adalah sebuah pohon biner yang memiliki sifat-sifat berikut:
Kelebihan utama dari pohon pencarian biner adalah keterkaitannya dengan algoritme pengurutan dan algoritme pencarian yang dapat lebih efisien, seperti "in-order traversal".
Pohon pencarian biner adalah sebuah struktur data dasar yang digunakan untuk membentuk struktur data yang lebih abstrak seperti set, multiset, dan array asosiatif.
Jika PPB memperkenankan nilai-nilai duplikat, maka PPB merupakan sebuah multiset. Pohon jenis ini menggunakan ketaksamaan longgar ("non-strict inequalities"), sehingga semua yang berada di subpohon bagian dari sebuah node adalah lebih kecil atau sama dengan nilai dari node, dan semua yang berada di subpohon bagian dari node adalah lebih besar atau sama dengan nilai dari node.
Jika PPB tidak memperkenankan nilai-nilai duplikat, maka PPB merupakan sebuah set dengan nilai-nilai unik, sama seperti set pada matematika (himpunan). Pohon tanpa nilai-nilai duplikat menggunakan ketaksamaan kaku ("strict inequalities"), artinya subpohon dari sebuah node hanya memuat node-node dengan nilai yang lebih kecil dari nilai node, dan subpohon hanya memuat nilai-nilai yang lebih besar.
Beberapa definisi PPB menggunakan sebuah ketaksamaan longgar hanya pada satu sisi, sehingga nilai-nilai duplikat diperkenankan. Walaupun demikian, definisi-definisi PPB tersebut membatasi dengan baik bagaiman sebuah pohon dengan banyak nilai duplikat dapat diseimbangkan.
Pencarian sebuah nilai tertentu pada pohon biner adalah sebuah proses yang dapat dilakukan secara rekursif karena nilai-nilai yang disimpan adalah terurut. Pencarian dimulai dengan memeriksa akar ("root"). Jika nilai yang dicari sama dengan akar, maka nilai ditemukan. Jika nilai yang dicari kurang dari akar, maka pencarian dilakukan terhadap
subpohon, sehingga kita secara rekursif mencari subpohon dengan cara yang sama. Jika nilai yang dicari lebih besar dari akar, maka pencarian dilakukan terhadap subpohon sehingga kita secara rekursif mencari subpohon dengan cara yang sama. Jika kita mencapai sebuah ujung ("leaf") dan belum menemukan yang dicari, maka nilai tersebut tidak ada dalam
pohon. Sebuah pembandingan dapat dibuat dengan pencarian biner, yang beroperasi hampir mirip degan pengaksesan acak pada sebuah array.
Operasi tersebut membutuhkan waktu O (log "n") pada kasus rata-rata, dan pada kasus terburuk membutuhkan waktu O ("n") ketika pohon tak seimbang yang menyerupai sebuah list berkai.
Penyisipan dimulai sebagaimana sebuah pencarian dilakukan. Jika akar tidak sama dengan nilai sisipan, kita mencari subpohon atau seperti di atas. Pada suatu saat kita akan mencapai sebuah node luar dan menambahkan nilai sisipan sebagai anak atau anak, bergantung pada nilai node. Dengan kata lain, kita memeriksa akar dan secara rekursif menyisipkan node yang baru
ke subpohon jika nilai yang baru lebih kecil atau sama dengan akar, atau menyisipkan ke subpohon jika nilai yang baru lebih besar dari root.
Variasi prosedural di atas adalah destruktif. Cara di atas hanya menggunakan ruang yang tetap, sehingga pohon versi sebelumnya menjadi hilang. Alternatif cara adalah seperti contoh Python berikut, kita dapat merekonstruksi kembali semua "pendahulu" dari node yang disisipkan; Semua referensi ke akar pohon asal akan tetap valid, yang membuat phon menjadi sebuah struktur data persisten.
Cara pertama di atas menggunakan ruang O (log "n") pada kasus rata-rata dan O ("n") dalam kasus terburut.
Pada kasus berikutnya, operasi membutuhkan waktu yang berbanding lurus dengan tinggi pohon pada kasus terburuk, yaitu O (log "n") pada kasus rata-rata, dan O ("n") pada kasus terburuk.
Cara lain menjelaskan penyisipan adalah bahwa untuk menyisipkan sebuah node baru dalam pohon, nilainya terlebih dahulu dibandingkan dengan nilai dari akar. Jika nilainya lebih kurang dari nilai akar, nilai tersebut kemudian dibandingkan dengan nilai dari anak akar. Jika nilainya lebih besar dari nilai akar, nilai tersebut
dibandingkan dengan nilai dari anak akar. Proses tersebut berlanjut, sampai node yang baru dibandingkan dengan node ujung, dan kemudian ditambahkan sebagai node anak atau anak bergantung nilainya.