Pohon Pencarian Biner itu apa sih?

Dalam ilmu komputer, sebuah pohon pencarian biner (PPB) adalah sebuah pohon biner yang memiliki sifat-sifat berikut:

Setiap node memiliki sebuah nilai.

Subpohon kiri dari sebuah node hanya memuat nilai-nilai yang lebih kecil atau sama dengan nilai dari node.

Subpohon kanan dari sebuah node hanya memuat nilai-nilai yang lebih besar atau sama dengan nilai dari node.

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 kiri dari sebuah node adalah lebih kecil atau sama dengan nilai dari node, dan semua yang berada di subpohon bagian kanan 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 kiri dari sebuah node hanya memuat node-node dengan nilai yang lebih kecil dari nilai node, dan subpohon kanan 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.