Pohon Pencarian Biner

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 dengan nilai dari node.
• Subpohon kanan dari sebuah node hanya memuat nilai-nilai yang lebih besar atau sama dengan dengan nilai dari node.

Kelebihan utama dari pohon pencarian biner adalah keterkaitannya dengan algoritma pengurutan dan algoritma 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 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.

Operasi-operasi

Pencarian

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 kiri, sehingga kita secara rekursif mencari subpohon kiri dengan cara yang sama. Jika nilai yang dicari lebih besar dari akar, maka pencarian dilakukan terhadap subpohon kanan sehingga kita secara rekursif mencari subpohon kanan 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.

Berikut adalah algoritma pencarian dalam bahasa pemrograman Python:

def search_binary_tree(node, key):
    if node is None:
        return None  # not found
    if key < node.key:
        return search_binary_tree(node.left, key)
    elif key > node.key:
        return search_binary_tree(node.right, key)
    else:
        return node.value

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.