Belajar Data Structure - Binary Search Tree (BST)

#Pendahuluan

Setelah di episode 10 kita memahami binary tree — node dengan left dan right child, empat traversals, dan cara mengukur height/size — pada episode ini kita mempelajari Binary Search Tree (BST), binary tree dengan aturan ordering: untuk setiap node, semua elemen di subtree kiri lebih kecil, dan semua elemen di subtree kanan lebih besar.

BST adalah jembatan antara binary tree biasa dan balanced tree. Ia memberikan O(log n) untuk search, insert, dan delete jika tree seimbang — tetapi menjadi O(n) saat tree skewed. Memahami trade-off ini adalah motivasi untuk self-balancing tree di episode 12.

#Aturan BST

Untuk setiap node dengan value V:

• Semua node di subtree kiri memiliki value < V
• Semua node di subtree kanan memiliki value > V
• Dilarang ada duplikat (atau ditangani secara spesifik)

In-order traversal BST selalu menghasilkan urutan terurut — ini adalah property yang membedakan BST dari binary tree biasa.

#Operasi BST

#Insert

Insert ke BST

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

#Search

Search di BST

def search(root, value):
    if root is None or root.value == value:
        return root
    if value < root.value:
        return search(root.left, value)
    return search(root.right, value)

#Delete (3 Kasus)

Delete di BST memiliki tiga kasus:

Kasus 1: Node tanpa children (leaf) — cukup hapus node.

Kasus 2: Node dengan satu child — ganti node dengan child-nya.

Kasus 3: Node dengan dua children — temukan in-order successor (node terkecil di subtree kanan), salin nilainya, lalu hapus successor tersebut.

Delete dari BST

def delete(root, value):
    if root is None:
        return root
 
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        # Kasus 1 & 2: no child atau one child
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
 
        # Kasus 3: two children
        successor = find_min(root.right)
        root.value = successor.value
        root.right = delete(root.right, successor.value)
 
    return root
 
def find_min(node):
    while node.left:
        node = node.left
    return node

#Masalah: Worst Case O(n)

Jika elemen di-insert secara terurut (misal: 1, 2, 3, 4, 5), tree menjadi skewed — setiap node hanya punya satu child. Ini mengubah BST menjadi linked list, dan semua operasi menjadi O(n).

Skewed BST:     Balanced BST:
  1               3
   \             / \
    2           2   4
     \             / \
      3           1   5
       \
        4
         \
          5

Inilah motivasi untuk self-balancing tree (AVL, Red-Black) di episode 12 yang menjaga tree tetap seimbang secara otomatis.

#In-Order Successor & Predecessor

• In-order successor: node terkecil di subtree kanan (untuk delete)
• In-order predecessor: node terbesar di subtree kiri

#Praktik

Uji BST dengan input sorted

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root
 
def in_order(node):
    if node is None:
        return []
    return in_order(node.left) + [node.value] + in_order(node.right)
 
root = None
for val in [5, 3, 7, 1, 4, 6, 8]:
    root = insert(root, val)
 
print("In-order:", in_order(root))
print("Height:", height(root))
 
skewed = None
for val in [1, 2, 3, 4, 5]:
    skewed = insert(skewed, val)
 
print("Skewed height:", height(skewed))

#Penutup

Inti yang harus dibawa pulang:

• BST: left < parent < right → in-order traversal = urutan terurut.
• Insert, search: O(log n) average, O(n) worst (skewed).
• Delete: 3 kasus — leaf, satu child, dua children (pakai in-order successor).
• Masalah: tree skewed mengubah O(log n) menjadi O(n).
• Solusi: self-balancing tree (AVL, Red-Black) → episode 12.

Di episode 12 selanjutnya kita akan membahas self-balancing tree (AVL & Red-Black) — bagaimana menjaga tree tetap seimbang secara otomatis dengan rotasi, menjamin O(log n) untuk semua operasi. AVL untuk read-heavy, Red-Black untuk write-heavy. Pastikan kalian sudah memahami BST karena self-balancing tree membangun di atasnya!