Pohon Pencarian Biner

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.