Pohon Pencarian Biner

Sebuah pohon biner terurut dengan lebar 9 dan kedalaman 3, dengan akar 8 dan daun: 1, 4, 7 dan 13.

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

• Setiap simpul (node) memiliki sebuah nilai.
• Sebuah susunan total ditentukan dalam nilai ini.
• Sub pohon (subtree) kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.
• Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.

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.

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 algoritme 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.

Penyisipan

Penyisipan dimulai sebagaimana sebuah pencarian dilakukan. Jika akar tidak sama dengan nilai sisipan, kita mencari subpohon kiri atau kanan seperti di atas. Pada suatu saat kita akan mencapai sebuah node luar dan menambahkan nilai sisipan sebagai anak kiri atau anak kanan, bergantung pada nilai node. Dengan kata lain, kita memeriksa akar dan secara rekursif menyisipkan node yang baru ke subpohon kiri jika nilai yang baru lebih kecil atau sama dengan akar, atau menyisipkan ke subpohon kanan jika nilai yang baru lebih besar dari root.

Berikut adalah penyisipan pohon pencarian biner yang biasa dilakukan dalam C:

void InsertNode(struct node **node_ptr, struct node *newNode) {
    struct node *node = *node_ptr;
    if (node == NULL)
        *node_ptr = newNode;
    else if (newNode->value <= node->value)
        InsertNode(&node->left, newNode);
    else
        InsertNode(&node->right, newNode);
}

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.

def binary_tree_insert(node, key, value):
    if node is None:
        return TreeNode(None, key, value, None)

    if key == node.key:
        return TreeNode(node.left, key, value, None)
    if key < node.key:
        return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
    else:
        return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

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 kiri akar. Jika nilainya lebih besar dari nilai akar, nilai tersebut dibandingkan dengan nilai dari anak kanan akar. Proses tersebut berlanjut, sampai node yang baru dibandingkan dengan node ujung, dan kemudian ditambahkan sebagai node anak kanan atau anak kiri bergantung nilainya.

Penghapusan

Ada kasus-kasus yang mesti diperhatikan:

• Penghapusan sebuah ujung: Penghapusan sebuah node tanpa anak adalah mudah, cukup menghilangkanya dari pohon.
• Penghapusan sebuah node dengan satu anak: Menghapusnya dan mengganti dengan anaknya.
• Penghapusan sebuah node dengan dua anak: Misalkan node yang akan dihapus adalah N. Kita ganti nilai dari N dengan suksesor in-order (anak terkiri dari subpohon kanan) atau dengan predesesor in-order (anak terkanan dari subpohon kiri).