Pohon pencarian biner

Pohon pencarian biner atau binary search tree (BST) adalah pohon biner yang menata nilai secara terstruktur agar pencarian cepat, bukan karena keberuntungan. Topik ini membangun BST dari nol dengan insert, search, dan delete pada berkas bst.py, membahas tiga kasus penghapusan, lalu mengukur akibat pohon miring yang menjatuhkan biaya operasi dari $O(\log n)$ ke $O(n)$. Demo Java menyusul dengan insert dan search yang setara. Invarian yang menopang semuanya diperiksa lebih dahulu lewat diagram.

Invarian BST#

BST menempelkan satu janji pada setiap node, yaitu seluruh nilai di subtree kiri lebih kecil dari nilai node, sedangkan seluruh nilai di subtree kanan lebih besar. Janji ini disebut invarian (invariant), sifat yang wajib benar pada setiap node sebelum dan sesudah setiap operasi. Kata seluruh adalah bagian yang paling sering disalahpahami, karena membandingkan node dengan anak langsungnya saja tidak cukup, dan contoh pohon yang lolos cek semacam itu dibedah pada pembahasan validasi BST. Diagram berikut menyorot node 50 yang seluruh subtree kirinya bernilai kurang dari 50 dan seluruh subtree kanannya bernilai lebih besar, dengan aturan yang sama berlaku mandiri pada node 30, 70, dan seterusnya.

Akibat praktisnya besar. Pencarian berbiaya $O(h)$ dengan $h$ tinggi pohon, karena setiap perbandingan membuang satu cabang utuh, persis pola pencarian biner pada array terurut. Penelusuran inorder yang dikenakan pada BST pun otomatis mengeluarkan nilai terurut naik, fakta yang dipakai dua kali pada topik ini, yaitu memverifikasi hasil delete dan menemukan elemen terkecil ke-k. Menjaga invarian bukan formalitas, melainkan seluruh sumber kecepatan BST.

Implementasi dari nol#

Berkas berikut memuat implementasi lengkap, dari kelas Node hingga uji coba di bagian bawah berkas. Penyisipan berjalan rekursif, pencarian memilih iterasi, dan penghapusan berbagi pola pengembalian akar yang menjaga sambungan node induk tetap benar.

"""Implementasi BST dari nol: insert, search, delete, dan inorder."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def insert(akar, nilai):
    # sisipkan nilai dengan menjaga invarian kiri < node < kanan
    if akar is None:
        return Node(nilai)
    if nilai < akar.nilai:
        akar.kiri = insert(akar.kiri, nilai)
    elif nilai > akar.nilai:
        akar.kanan = insert(akar.kanan, nilai)
    return akar   # nilai yang sama tidak disisipkan dua kali

def search(akar, nilai):
    # pencarian memangkas satu cabang pada setiap langkah
    while akar is not None and akar.nilai != nilai:
        if nilai < akar.nilai:
            akar = akar.kiri
        else:
            akar = akar.kanan
    return akar

def node_terkiri(akar):
    # node terkiri menyimpan nilai terkecil pada subtree
    while akar.kiri is not None:
        akar = akar.kiri
    return akar

def delete(akar, nilai):
    if akar is None:
        return None
    if nilai < akar.nilai:
        akar.kiri = delete(akar.kiri, nilai)
    elif nilai > akar.nilai:
        akar.kanan = delete(akar.kanan, nilai)
    else:
        # kasus 1 dan 2: tanpa anak atau cukup satu anak menggantikan
        if akar.kiri is None:
            return akar.kanan
        if akar.kanan is None:
            return akar.kiri
        # kasus 3: dua anak, ganti nilai dengan inorder successor
        penerus = node_terkiri(akar.kanan)
        akar.nilai = penerus.nilai
        akar.kanan = delete(akar.kanan, penerus.nilai)
    return akar

def inorder(akar, hasil):
    # penelusuran inorder pada BST menghasilkan urutan naik
    if akar is not None:
        inorder(akar.kiri, hasil)
        hasil.append(akar.nilai)
        inorder(akar.kanan, hasil)

def daftar_inorder(akar):
    hasil = []
    inorder(akar, hasil)
    return hasil

# bangun pohon BST dari daftar nilai
akar = None
for x in [50, 30, 70, 20, 40, 60, 80]:
    akar = insert(akar, x)

print("inorder awal         :", daftar_inorder(akar))
print("cari 40              :", search(akar, 40) is not None)
print("cari 65              :", search(akar, 65) is not None)

akar = delete(akar, 20)   # kasus 1: node tanpa anak (leaf)
print("hapus 20 (leaf)      :", daftar_inorder(akar))

akar = delete(akar, 30)   # kasus 2: node dengan satu anak
print("hapus 30 (satu anak) :", daftar_inorder(akar))

akar = delete(akar, 50)   # kasus 3: node dengan dua anak
print("hapus 50 (dua anak)  :", daftar_inorder(akar))
print("akar yang baru       :", akar.nilai)

inorder awal         : [20, 30, 40, 50, 60, 70, 80]
cari 40              : True
cari 65              : False
hapus 20 (leaf)      : [30, 40, 50, 60, 70, 80]
hapus 30 (satu anak) : [40, 50, 60, 70, 80]
hapus 50 (dua anak)  : [40, 60, 70, 80]
akar yang baru       : 60

Nilai yang sama dengan node yang sudah ada tidak disisipkan ulang, sehingga duplikat tidak menggandakan node. Fungsi insert mengembalikan akar subtree yang mungkin sudah berubah, dan pemanggil menugaskannya kembali dengan akar = insert(akar, x), pola yang membuat sambungan terbentuk otomatis bila node baru ditambahkan pada kedalaman mana pun. Fungsi search sengaja ditulis iteratif karena tidak ada pekerjaan tersisa setelah turun selesai, cukup berjalan sampai menemukan nilai atau mencapai None. Penelusuran inorder dikumpulkan ke daftar dan dipakai sebagai alat periksa, karena BST yang benar selalu menghasilkan urutan naik 20 sampai 80, dan urutan itu tetap naik setelah ketiga penghapusan selesai.

Penghapusan dengan tiga kasus#

Menghapus node pada BST memiliki tiga kasus yang ketiganya ditangani di tempat node ditemukan.

1. Node tanpa anak (leaf) dikembalikan sebagai None, dan induknya kehilangan satu cabang tanpa penataan ulang lain.
2. Node dengan satu anak digantikan langsung oleh anak tunggalnya, sebab anak itu sendiri sudah menjadi pohon yang sah.
3. Node dengan dua anak menyalin nilai inorder successor, yaitu node terkiri dari subtree kanan, lalu successor yang kini ganda dihapus dari subtree kanan.

Kasus ketiga paling menarik karena strukturnya dipertahankan, bukan diruntuhkan. Inorder successor adalah nilai terkecil pada subtree kanan, dan nilai itu pasti lebih besar dari seluruh subtree kiri sekaligus lebih kecil dari sisa subtree kanan, sehingga invarian tetap terjaga setelah penggantian. Baris intinya hanya tiga.

# tidak-dijalankan
# inti kasus dua anak pada delete, diambil dari bst.py
penerus = node_terkiri(akar.kanan)   # inorder successor
akar.nilai = penerus.nilai           # nilai 50 diganti 60
akar.kanan = delete(akar.kanan, penerus.nilai)   # hapus 60 yang kini ganda

Keluaran bst.py memperlihatkan ketiga kasusnya berurutan. Menghapus 20 hanya menghilangkan satu leaf tanpa menggeser node lain, menghapus 30 menaikkan 40 sebagai penggantinya, dan menghapus 50 menempatkan 60 sebagai akar baru. Inorder setelah setiap langkah tetap naik tanpa celah, dan itulah alat verifikasi termurah yang tersedia.

Bahaya pohon miring#

Biaya insert, search, dan delete dinyatakan $O(h)$ dengan $h$ tinggi pohon, bukan $O(\log n)$ secara mutlak. Pohon seimbang menepati $h \approx \log_2 n$ sehingga operasinya terasa seperti pencarian biner, sedangkan pohon miring (degenerate) menghilangkan cabang dan mengubah pohon menjadi rantai setinggi $n - 1$ dengan operasi $O(n)$. Bentuk pohon sepenuhnya ditentukan urutan penyisipan, dan urutan penyisipan yang terurut menghasilkan bentuk yang paling buruk.

"""BST seimbang dan miring: perbandingan tinggi serta langkah pencarian."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def insert(akar, nilai):
    if akar is None:
        return Node(nilai)
    if nilai < akar.nilai:
        akar.kiri = insert(akar.kiri, nilai)
    else:
        akar.kanan = insert(akar.kanan, nilai)
    return akar

def tinggi(akar):
    # tinggi pohon kosong didefinisikan -1
    if akar is None:
        return -1
    return 1 + max(tinggi(akar.kiri), tinggi(akar.kanan))

def langkah_cari(akar, target):
    # hitung node yang dikunjungi sampai target ditemukan
    langkah = 0
    while akar is not None and akar.nilai != target:
        akar = akar.kiri if target < akar.nilai else akar.kanan
        langkah += 1
    return langkah

# pohon seimbang: akar dipilih dari nilai tengah
seimbang = None
for x in [50, 30, 70, 20, 40, 60, 80]:
    seimbang = insert(seimbang, x)

# pohon miring: penyisipan nilai terurut naik membentuk rantai
miring = None
for x in [20, 30, 40, 50, 60, 70, 80]:
    miring = insert(miring, x)

print("tinggi pohon seimbang    :", tinggi(seimbang))
print("tinggi pohon miring      :", tinggi(miring))
print("langkah cari 80 seimbang :", langkah_cari(seimbang, 80))
print("langkah cari 80 miring   :", langkah_cari(miring, 80))

tinggi pohon seimbang    : 2
tinggi pohon miring      : 6
langkah cari 80 seimbang : 2
langkah cari 80 miring   : 6

Penyisipan terurut naik 20 sampai 80 menghasilkan rantai setinggi enam sisi, sedangkan penyisipan yang menaruh nilai tengah lebih dahulu menghasilkan pohon setinggi dua sisi. Pencarian 80 pada pohon seimbang mengunjungi tiga node, sedangkan pada pohon miring mengunjungi ketujuhnya, dan selisih ini melebar cepat seiring data karena $\log_2 n$ dan $n$ terpisah jauh pada data besar. Kondisi ini menjadi jembatan menuju soal validasi BST karena dua jenis kesalahan berbeda sama-sama mungkin terjadi. Jenis pertama adalah pohon yang sah tetapi melambat karena miring, dan jenis kedua adalah pohon yang cepat tetapi melanggar invarian sehingga wajib ditolak.

Varian Java#

public class BSTDemo {
    static class Node {
        int nilai;
        Node kiri, kanan;
        Node(int nilai) { this.nilai = nilai; }
    }

    // menyisipkan nilai sambil menjaga invarian BST
    static Node insert(Node akar, int nilai) {
        if (akar == null) return new Node(nilai);
        if (nilai < akar.nilai) akar.kiri = insert(akar.kiri, nilai);
        else if (nilai > akar.nilai) akar.kanan = insert(akar.kanan, nilai);
        return akar;
    }

    // pencarian iteratif yang memangkas satu cabang per langkah
    static boolean search(Node akar, int nilai) {
        while (akar != null && akar.nilai != nilai) {
            if (nilai < akar.nilai) akar = akar.kiri;
            else akar = akar.kanan;
        }
        return akar != null;
    }

    public static void main(String[] args) {
        int[] data = {50, 30, 70, 20, 40, 60, 80};
        Node akar = null;
        for (int x : data) {
            akar = insert(akar, x);
        }
        System.out.println("cari 40 : " + search(akar, 40));
        System.out.println("cari 65 : " + search(akar, 65));
    }
}

cari 40 : true
cari 65 : false

Versi Java menyertakan insert dan search saja, karena delete memanjang tanpa menambah wawasan baru di bahasa kedua. Pola pengembalian akar tetap dipertahankan pada insert, sedangkan search mengikuti versi iteratif Python dengan perbandingan int langsung. Keluaran true dan false dari dua pencarian identik maknanya dengan True dan False pada versi Python. Pohon contoh dibangun dari daftar literal {50, 30, 70, 20, 40, 60, 80} lewat perulangan for each yang menyisipkannya satu per satu. Untuk penghapusan, struktur tiga kasus pada bst.py dapat dipindahkan ke Java dengan mengganti None menjadi null dan pemeriksaan is None menjadi pemeriksaan == null.

Kesalahan umum#

1. Memvalidasi BST dengan membandingkan anak langsung saja. Pohon contohnya memiliki 10 sebagai akar, 5 dan 15 sebagai anak, serta 6 di bawah 15. Pohon itu lolos cek semacam itu padahal 6 melanggar invarian karena berada di subtree kanan dari 10. Perbaikannya adalah mengoper batas rentang pada setiap pemanggilan rekursif.
2. Lupa menugaskan ulang hasil insert dan delete. Menulis insert(akar, x) tanpa akar = membuat node baru terpasang di salinan referensi lokal lalu hilang, dan pohon tetap seperti semula. Pola pengembalian akar wajib ditiru di setiap pemanggilan.
3. Mengganti nilai pada delete dua anak dengan nilai sembarang. Hanya inorder successor atau inorder predecessor yang menjamin invarian selamat. Nilai lain membuat inorder tidak lagi naik dan seluruh operasi BST menjadi tidak dapat diandalkan.
4. Mengira BST menjamin $O(\log n)$ pada semua kasus. Jaminan itu berlaku pada pohon seimbang, sedangkan pohon miring dari penyisipan terurut menjatuhkan semua operasi ke $O(n)$.

Ringkasan#

• Invarian kiri < node < kanan berlaku untuk seluruh subtree pada setiap node, bukan hanya anak langsung.
• insert dan delete berbagi pola pengembalian akar, sedangkan search cukup menuruni satu jalur secara iteratif.
• Delete menangani tiga kasus, dan kasus dua anak diselesaikan dengan inorder successor dari subtree kanan.
• Biaya operasi adalah $O(h)$, yaitu $O(\log n)$ pada pohon seimbang dan $O(n)$ pada pohon miring.

Referensi#

• Binary search tree — Wikipedia — definisi invarian serta ketiga kasus penghapusan yang menjadi rujukan bagian implementasi.
• Algorithms, 4th Edition — Princeton University — materi BST Princeton yang memuat analisis biaya insert, search, dan delete.