AVL Tree

AVL tree, dinamai dari penemunya Adelson-Velsky dan Landis (1962), adalah self-balancing BST pertama dalam sejarah ilmu komputer. Inti AVL adalah aturan sederhana: untuk setiap node, |balance factor| ≤ 1 — artinya selisih height subtree kiri dan subtree kanan paling banyak 1. Saat insert atau delete menyebabkan BF suatu node menjadi +2 atau -2, AVL melakukan rotasi untuk memulihkan keseimbangan. Empat jenis rotasi: LL, RR, LR, RL — masing-masing untuk pola ketidakseimbangan yang berbeda. Pada Chapter ini kita akan membedah keempat rotasi dengan diagram Mermaid, mengimplementasikan AVL tree lengkap dengan insert yang otomatis rebalancing, dan memverifikasi bahwa operasi pada data terurut pun menghasilkan tree height O(log n).

Properti AVL #

Sebuah BST adalah AVL tree bila untuk setiap node:

text

|height(left) - height(right)| ≤ 1

Konsekuensi: height AVL tree dengan n node terjamin ≤ 1.44 log₂(n + 2). Untuk n = 1 juta, height ≤ 30.

Empat Kasus Ketidakseimbangan #

Saat insert menyebabkan BF root = +2 atau -2, ada empat pola berbeda tergantung di mana node baru disisipkan:

Kasus LL (Left-Left) #

Node baru disisipkan di subtree kiri dari anak kiri. Solusi: rotasi kanan pada node yang unbalanced.

flowchart TD subgraph Sebelum["Sebelum (BF=+2)"] Z1["Z (BF=+2)"] --> Y1["Y (BF=+1)"] Z1 --> T4["T4"] Y1 --> X1["X (BF=0)"] Y1 --> T3["T3"] X1 --> T1["T1"] X1 --> T2["T2"] end subgraph Sesudah["Sesudah rotasi kanan"] Y2["Y"] --> X2["X"] Y2 --> Z2["Z"] X2 --> T1a["T1"] X2 --> T2a["T2"] Z2 --> T3a["T3"] Z2 --> T4a["T4"] end

Kasus RR (Right-Right) #

Node baru disisipkan di subtree kanan dari anak kanan. Solusi: rotasi kiri pada node yang unbalanced. Cermin LL.

Kasus LR (Left-Right) #

Node baru disisipkan di subtree kanan dari anak kiri. Solusi: rotasi kiri pada anak kiri, lalu rotasi kanan pada root. Dua tahap.

flowchart TD Z["Z (BF=+2)"] --> Y["Y (BF=-1)"] Z --> T4["T4"] Y --> T1["T1"] Y --> X["X (BF=0)"] X --> T2["T2"] X --> T3["T3"]

LR: pertama rotasi kiri pada Y (mengubah pola menjadi LL), lalu rotasi kanan pada Z.

Kasus RL (Right-Left) #

Node baru disisipkan di subtree kiri dari anak kanan. Solusi: rotasi kanan pada anak kanan, lalu rotasi kiri pada root. Cermin LR.

Implementasi Rotasi Dasar #

Dua rotasi fundamental: right rotate dan left rotate. Empat kasus (LL, RR, LR, RL) adalah kombinasi dari keduanya.

cpp
#include <iostream>
#include <algorithm>

template <typename T>
struct AVLNode {
    T data;
    AVLNode* left;
    AVLNode* right;
    int height;     // cached height
    explicit AVLNode(const T& v) : data(v), left(nullptr), right(nullptr), height(0) {}
};

template <typename T>
int h(const AVLNode<T>* n) { return n ? n->height : -1; }

template <typename T>
void update_height(AVLNode<T>* n) {
    n->height = 1 + std::max(h(n->left), h(n->right));
}

template <typename T>
int bf(const AVLNode<T>* n) { return n ? h(n->left) - h(n->right) : 0; }

template <typename T>
AVLNode<T>* rotate_right(AVLNode<T>* y) {
    AVLNode<T>* x = y->left;
    AVLNode<T>* t2 = x->right;
    x->right = y;
    y->left = t2;
    update_height(y);
    update_height(x);
    return x;            // new root of subtree
}

template <typename T>
AVLNode<T>* rotate_left(AVLNode<T>* x) {
    AVLNode<T>* y = x->right;
    AVLNode<T>* t2 = y->left;
    y->left = x;
    x->right = t2;
    update_height(x);
    update_height(y);
    return y;
}

template <typename T>
AVLNode<T>* insert(AVLNode<T>* node, const T& v) {
    // 1. Insert BST standar
    if (node == nullptr) return new AVLNode<T>(v);
    if (v < node->data)      node->left  = insert(node->left,  v);
    else if (v > node->data) node->right = insert(node->right, v);
    else return node;     // no duplicate

    // 2. Update height
    update_height(node);

    // 3. Rebalance
    int balance = bf(node);

    // LL
    if (balance > 1 && v < node->left->data) {
        return rotate_right(node);
    }
    // RR
    if (balance < -1 && v > node->right->data) {
        return rotate_left(node);
    }
    // LR
    if (balance > 1 && v > node->left->data) {
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }
    // RL
    if (balance < -1 && v < node->right->data) {
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }

    return node;          // already balanced
}

template <typename T>
void inorder(AVLNode<T>* n) {
    if (n == nullptr) return;
    inorder(n->left);
    std::cout << n->data << "(h=" << n->height << ") ";
    inorder(n->right);
}

template <typename T>
void print_tree(AVLNode<T>* n, int depth = 0) {
    if (n == nullptr) return;
    std::string indent(depth * 2, ' ');
    print_tree(n->right, depth + 1);
    std::cout << indent << n->data << " (h=" << n->height << ", BF=" << bf(n) << ")\n";
    print_tree(n->left, depth + 1);
}

int main() {
    AVLNode<int>* root = nullptr;
    // Insert terurut — pada BST biasa akan jadi skewed
    for (int v : {10, 20, 30, 40, 50, 25}) {
        root = insert(root, v);
    }

    std::cout << "In-order traversal:\n  ";
    inorder(root);
    std::cout << "\n\nStruktur tree (rotated 90°):\n";
    print_tree(root);

    // Verifikasi height O(log n)
    std::cout << "\nRoot height = " << root->height << " (ideal log2(6) ~ 2.58)\n";
    return 0;
}

Output yang Dihasilkan:

text
In-order traversal:
  10(h=0) 20(h=1) 25(h=0) 30(h=2) 40(h=1) 50(h=0) 

Struktur tree (rotated 90°):
    50 (h=0, BF=0)
  40 (h=1, BF=-1)
30 (h=2, BF=0)
    25 (h=0, BF=0)
  20 (h=1, BF=0)
    10 (h=0, BF=0)

Root height = 2 (ideal log2(6) ~ 2.58)

Struct AVLNode: menambahkan field height yang di-cache. Tanpa cache, menghitung height O(n) per node — total O(n²) per insert. Dengan cache, update height O(1) per node.
rotate_right(y): x = y->left, t2 = x->right. Pindahkan t2 menjadi left child y. x menjadi root baru subtree. Update height y dulu (anak), lalu x (parent) — urutan penting karena height parent bergantung pada height anak.
rotate_left(x): cermin rotate_right. y = x->right, t2 = y->left. Pindahkan t2 menjadi right child x. y menjadi root baru.
Insert dengan rebalancing: setelah insert BST biasa, update height node, lalu cek balance factor. Empat kasus: LL → rotate right, RR → rotate left, LR → rotate left pada anak kiri lalu rotate right pada node, RL → rotate right pada anak kanan lalu rotate left pada node.
Hasil insert [10, 20, 30, 40, 50, 25]: tree tetap balanced dengan root 30, height 2. Tanpa AVL, insert terurut menghasilkan right-skewed tree height 5. AVL menghemat ~60% height.
Verifikasi BF: setiap node |BF| ≤ 1. Root BF = 0 (subtree kiri height 1, subtree kanan height 1).

Analisis Kompleksitas AVL #

Operasi	Waktu	Catatan
Search	O(log n)	Sama dengan BST biasa
Insert	O(log n)	1-2 rotasi per insert
Delete	O(log n)	Bisa sampai O(log n) rotasi
Height terjamin	≤ 1.44 log n	Lebih ketat dari Red-Black

AVL vs Red-Black Tree #

Aspek	AVL	Red-Black
Ketat balancing	Tinggi (	BF
Height praktis	≈ 1.44 log n	≈ 2 log n
Search lebih cepat	Ya (height lebih kecil)	Tidak
Insert/delete lebih lambat	Ya (banyak rotasi)	Tidak (lebih sedikit rotasi)
Dipakai di STL	Tidak	`std::map`, `std::set`
Cocok untuk	Read-heavy, database index	Write-heavy, general purpose

Ringkasan #

AVL tree: BST dengan aturan |BF| ≤ 1 untuk setiap node. Height terjamin ≤ 1.44 log n.
Empat kasus ketidakseimbangan: LL (rotasi kanan), RR (rotasi kiri), LR (rotasi kiri anak kiri + rotasi kanan), RL (rotasi kanan anak kanan + rotasi kiri).
Implementasi menyimpan height pada setiap node agar perhitungan BF O(1). Update height dari anak ke parent setelah modifikasi subtree.
AVL sangat ketat → ideal untuk read-heavy. Red-Black lebih longgar → ideal untuk write-heavy.
std::map/std::set memakai Red-Black, bukan AVL — trade-off antara kecepatan search dan frekuensi rotasi.