Belajar Data Structure - Self-Balancing Tree (AVL & Red-Black)

#Pendahuluan

Setelah di episode 11 kita melihat masalah BST yang bisa menjadi skewed dan berubah dari O(log n) menjadi O(n), pada episode ini kita mempelajari solusinya: self-balancing tree — AVL tree dan Red-Black tree. Keduanya menjaga tree tetap seimbang secara otomatis melalui operasi rotasi, menjamin O(log n) untuk search, insert, dan delete.

AVL dan Red-Black tree adalah dua pendekatan berbeda untuk masalah yang sama: AVL lebih ketat dalam menjaga keseimbangan (lebih sedikit ketinggian, lebih banyak rotasi), sementara Red-Black lebih longgar (sedikit lebih tinggi, tetapi lebih sedikit rotasi saat insert/delete). Pemilihan antara keduanya tergantung pada pola akses: read-heavy atau write-heavy.

#AVL Tree

#Konsep Dasar

AVL tree dinamai dari penemunya (Adelson-Velsky dan Landis). Setiap node memiliki balance factor = height(subtree kiri) - height(subtree kanan). Balance factor harus selalu -1, 0, atau 1. Jika melampaui batas ini, tree harus dirotasi.

#Rotasi

Ketika balance factor melampaui batas, empat jenis rotasi diperlukan:

Single Rotation:

• LL Rotation: subtree kiri-kiri → rotasi kanan
• RR Rotation: subtree kanan-kanan → rotasi kiri

Double Rotation:

• LR Rotation: subtree kiri-kanan → rotasi kiri lalu kanan
• RL Rotation: subtree kanan-kiri → rotasi kanan lalu kiri

#Visualisasi LL Rotation

Sebelum LL Rotation:    Sesudah LL Rotation:
        30                    20
       /                     /  \
      20                   10    30
     /
    10

#Implementasi AVL

AVL tree node dengan balance factor

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1
 
def height(node):
    return node.height if node else 0
 
def balance_factor(node):
    return height(node.left) - height(node.right) if node else 0
 
def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))
 
def rotate_right(z):
    y = z.left
    T2 = y.right
    y.right = z
    z.left = T2
    update_height(z)
    update_height(y)
    return y
 
def rotate_left(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    update_height(z)
    update_height(y)
    return y

#Insert dengan Rebalancing

AVL insert dengan rotasi

def avl_insert(root, value):
    if root is None:
        return AVLNode(value)
 
    if value < root.value:
        root.left = avl_insert(root.left, value)
    elif value > root.value:
        root.right = avl_insert(root.right, value)
    else:
        return root
 
    update_height(root)
    bf = balance_factor(root)
 
    # LL
    if bf > 1 and value < root.left.value:
        return rotate_right(root)
    # RR
    if bf < -1 and value > root.right.value:
        return rotate_left(root)
    # LR
    if bf > 1 and value > root.left.value:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    # RL
    if bf < -1 and value < root.right.value:
        root.right = rotate_right(root.right)
        return rotate_left(root)
 
    return root

#Red-Black Tree

#Aturan Red-Black

Red-Black tree memiliki lima aturan:

1. Setiap node berwarna merah atau hitam
2. Root selalu hitam
3. Semua leaf (None) berwarna hitam
4. Jika node merah, children-nya harus hitam (tidak ada dua merah berturut-turut)
5. Setiap path dari root ke leaf memiliki jumlah node hitam yang sama

#Perbandingan dengan AVL

#Kapan Memilih Mana?

• AVL: read-heavy workload, dataset relatif statis, search lebih sering dari insert/delete
• Red-Black: write-heavy workload, insert/delete lebih sering, digunakan di standard library

#Perbandingan Lookup

Bandingkan waktu lookup pada balanced vs skewed tree:

Perbandingan balanced vs skewed

import time
 
def skewed_height(n):
    return n - 1
 
def balanced_height(n):
    import math
    return math.floor(math.log2(n))
 
for n in [1000, 10000, 100000, 1000000]:
    print(f"n={n:>9}: skewed={skewed_height(n):>7}, balanced={balanced_height(n):>3}")

Pada n = 1 juta, skewed tree perlu 999.999 langkah, sementara balanced tree hanya perlu 19 langkah — perbedaan 50.000x.

#Penutup

Inti yang harus dibawa pulang:

• Self-balancing tree menjamin O(log n) untuk search, insert, delete.
• AVL: balance factor ±1, lebih banyak rotasi, lebih pendek → read-heavy.
• Red-Black: aturan longgar (5 aturan), lebih sedikit rotasi → write-heavy.
• Empat jenis rotasi AVL: LL, RR, LR, RL.
• Red-Black tree digunakan di Java TreeMap, C++ std::map, Linux kernel.

Di episode 13 selanjutnya kita akan membahas B-Tree dan B+ Tree — tree dengan branching factor tinggi yang dirancang untuk meminimalkan disk I/O, menjadi fondasi database index (MySQL InnoDB, PostgreSQL) dan file system (ext4, NTFS). Ini adalah world di mana disk I/O lebih mahal dari CPU — dan B-Tree dirancang khusus untuk mengatasi masalah ini!