Binary search tree: cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan binary search tree

Sorted array memberi binary search yang cepat, tetapi menyisipkan elemen baru menggeser semua yang ada setelahnya. Hash table memberi lookup dan insert yang cepat, tetapi tidak menyimpan urutan, sehingga tidak bisa menjawab "key terkecil yang lebih besar dari 42 itu apa?" atau "tampilkan semua key antara 10 dan 20". Binary search tree menjaga key tetap terurut dan tetap memungkinkan insert dan delete yang cepat. Ini adalah dasar dari ordered map dan set seperti TreeMap di Java dan std::map di C++, yang memakai varian self-balancing.

Aturannya dengan bahasa sederhana

Setiap node punya sebuah key, anak kiri opsional, dan anak kanan opsional. Untuk setiap node: semua key di subtree kirinya lebih kecil, dan semua key di subtree kanannya lebih besar. Untuk mencari key, mulai dari root lalu bandingkan: ke kiri jika key lebih kecil, ke kanan jika lebih besar, berhenti jika sama atau jika sudah keluar dari tree.

Contoh langkah demi langkah: membangun dan mencari di tree

Insert 8, 3, 10, 1, 6, 14, 4 dengan urutan ini. Setiap key baru turun dari root dan menjadi leaf di tempat ia keluar dari tree.

Mencari 4 membandingkan dengan 8, 3, 6, lalu 4: empat perbandingan pada tree berisi tujuh key. Mencari 7 membandingkan dengan 8, 3, 6, lalu tidak menemukan anak kanan dari 6, jadi 7 tidak ada.

Implementasi Python

Insert dan search berupa loop pendek. Delete punya tiga kasus: node tanpa anak (hapus saja), satu anak (ganti dengan anaknya), atau dua anak (salin in-order successor-nya, yaitu key terkecil di subtree kanan, lalu hapus successor itu).

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

Kompleksitas waktu dan ruang

Kasus terburuk itu nyata, bukan sekadar teori: memasukkan key yang sudah terurut (1, 2, 3, ...) ke BST biasa membuat setiap node hanya punya anak kanan, dan tree menjadi linked list. Urutan insert acak memberi tinggi yang diharapkan O(log n).

Varian seimbang dan kesalahan umum

Self-balancing tree menjaga tinggi tetap O(log n) dengan menyusun ulang lewat rotasi setelah insert dan delete.

• Memvalidasi BST hanya dengan memeriksa induk dan anak. Teruskan rentang (low, high) yang valid ke bawah.
• Lupa mengembalikan root (yang mungkin baru) dari insert dan delete rekursif, sehingga perubahan hilang.
• Rekursi yang dalam pada tree yang merosot: batas rekursi default Python sekitar 1000, jadi rantai 5000 node membuat kode rekursif crash. Pakai loop atau jaga tree tetap seimbang.
• Kebijakan duplikat yang tidak jelas: putuskan apakah duplikat diabaikan, dihitung, atau selalu masuk ke satu sisi.

Kapan memakai BST dan pertanyaan wawancara yang khas

Gunakan balanced BST ketika Anda butuh data terurut dengan insert dan delete yang sering: range query, pencarian floor dan ceiling, statistik peringkat, atau iterasi dalam urutan terurut. Gunakan hash table jika Anda hanya butuh lookup key yang tepat. Di Python, pustaka standar tidak punya tree map; pilihan umumnya adalah sorted list dengan modul bisect untuk data kecil atau yang jarang berubah, atau paket pihak ketiga sortedcontainers.

Pertanyaan wawancara yang khas: validasi BST, mencari elemen terkecil ke-k (traversal in-order), lowest common ancestor, mengubah sorted array menjadi BST seimbang (pilih elemen tengah sebagai root), dan mencari in-order successor dari sebuah node.