Balanced Binary Tree

Pada chapter sebelumnya, kita melihat bahwa operasi BST memiliki kompleksitas O(h) — di mana h adalah height tree. Pada tree yang seimbang, h = O(log n) dan semua operasi berjalan dalam waktu logaritmik. Namun pada tree yang skewed (miring), h = O(n) — seburuk linear search pada array. Bayangkan memasukkan data terurut [1, 2, 3, 4, 5, 6, 7] ke BST biasa: setiap insert menambah node ke kanan saja, menghasilkan linked list terurut. Pencarian 7 butuh 7 langkah, padahal seharusnya O(log n) = 3 langkah. Inilah motivasi di balik balanced binary tree: struktur yang otomatis menjaga height tetap O(log n) terlepas dari urutan input. Pada Chapter ini kita akan memahami konsep balance factor, kategori balanced tree (height-balanced vs weight-balanced), dan demonstrasi empiris bagaimana skewed BST vs balanced BST memengaruhi performa.

Mengapa Balancing Penting? #

Aturan #

Sebuah binary tree dengan n node memiliki height minimum ⌊log₂ n⌋ (complete binary tree) dan height maksimum n - 1 (skewed). Selisih ini dramatis:

Jumlah node (n)	Height minimum (balanced)	Height maksimum (skewed)
7	3	6
1023	10	1022
1.048.575	20	1.048.574
1 miliar	30	999.999.999

Mekanisme: Skewed BST = Linked List #

Insert data terurut ascending ke BST biasa selalu menghasilkan right-skewed tree. Setiap insert baru menambah depth 1. Akibatnya, search/insert/delete semuanya O(n), padahal idealnya O(log n).

flowchart TD A["1"] --> B["2"] B --> C["3"] C --> D["4"] D --> E["5"]

Tree di atas adalah BST valid tetapi skewed. Mencari 5 membutuhkan 5 langkah, padahal pada balanced BST dengan 5 node cukup 3 langkah.

Balance Factor #

Untuk mengevaluasi keseimbangan setiap node, kita perkenalkan balance factor (BF):

text

BF(node) = height(left subtree) - height(right subtree)

Sebuah node dianggap balanced bila |BF| ≤ 1, yaitu BF ∈ {-1, 0, +1}.

BF = 0: subtree kiri dan kanan memiliki height sama.
BF = +1: subtree kiri lebih tinggi 1.
BF = -1: subtree kanan lebih tinggi 1.
BF = +2 atau BF = -2: unbalanced, perlu rebalancing.

Implementasi: Menghitung Balance Factor #

cpp
#include <iostream>
#include <algorithm>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

template <typename T>
int height(const Node<T>* n) {
    if (n == nullptr) return -1;
    return 1 + std::max(height(n->left), height(n->right));
}

template <typename T>
int balance_factor(const Node<T>* n) {
    if (n == nullptr) return 0;
    return height(n->left) - height(n->right);
}

template <typename T>
bool is_balanced(const Node<T>* n) {
    if (n == nullptr) return true;
    int bf = balance_factor(n);
    if (bf < -1 || bf > 1) return false;
    return is_balanced(n->left) && is_balanced(n->right);
}

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

int main() {
    // Tree seimbang:
    //         4
    //        / \
    //       2   6
    //      / \ / \
    //     1  3 5  7
    Node<int>* balanced = new Node<int>(4);
    balanced->left  = new Node<int>(2);
    balanced->right = new Node<int>(6);
    balanced->left->left   = new Node<int>(1);
    balanced->left->right  = new Node<int>(3);
    balanced->right->left  = new Node<int>(5);
    balanced->right->right = new Node<int>(7);

    std::cout << "=== Balanced tree ===\n";
    print_bf(balanced);
    std::cout << "Is balanced: " << (is_balanced(balanced) ? "ya" : "tidak") << '\n';

    // Tree skewed (right):
    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    Node<int>* skewed = new Node<int>(1);
    skewed->right = new Node<int>(2);
    skewed->right->right = new Node<int>(3);
    skewed->right->right->right = new Node<int>(4);

    std::cout << "\n=== Skewed tree ===\n";
    print_bf(skewed);
    std::cout << "Is balanced: " << (is_balanced(skewed) ? "ya" : "tidak") << '\n';

    return 0;
}

Output yang Dihasilkan:

text
=== Balanced tree ===
4 (BF=0)
  2 (BF=0)
    1 (BF=0)
    3 (BF=0)
  6 (BF=0)
    5 (BF=0)
    7 (BF=0)
Is balanced: ya

=== Skewed tree ===
1 (BF=-3)
  2 (BF=-2)
    3 (BF=-1)
      4 (BF=0)
Is balanced: tidak

height: rekursif post-order. nullptr → -1 agar leaf = 0. Kompleksitas O(n) karena setiap node dikunjungi.
balance_factor: height(left) - height(right). Pada perfect binary tree, semua BF = 0.
is_balanced: rekursif cek setiap node. Bila ada node dengan |BF| > 1, tree tidak balanced.
Balanced tree: setiap node BF = 0 karena tree perfect. Tinggi seragam di seluruh leaf.
Skewed tree: root 1 punya BF = -3 (subtree kanan height 3, subtree kiri -1). Tree tidak balanced. Operasi pada tree ini akan O(n), padahal idealnya O(log n).

Kategori Balanced Tree #

Ada dua filosofi balancing:

Height-Balanced Tree #

Menjaga |BF| ≤ 1 untuk setiap node. Contoh: AVL tree. Memaksimalkan keseimbangan height — sangat ketat.

Weight-Balanced Tree #

Menjaga jumlah node pada subtree kiri dan kanan berimbang (rasio tertentu). Contoh: BB[α] tree dengan rasio α. Lebih longgar daripada height-balanced.

Kategori	Kriteria	Contoh
Height-balanced		BF
Weight-balanced	size(left) / size(node) ∈ [α, 1-α]	BB[α], Scapegoat Tree
Color-balanced	Path root-leaf punya jumlah merah sama	Red-Black Tree
Size-balanced	size(left) ≈ size(right)	Scapegoat Tree

Performa: Skewed vs Balanced BST #

Mari kita ukur secara empiris waktu pencarian pada BST skewed (insert terurut) vs balanced (insert acak).

cpp
#include <iostream>
#include <chrono>
#include <random>
#include <vector>
#include <algorithm>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

template <typename T>
Node<T>* insert(Node<T>* node, const T& v) {
    if (node == nullptr) return new Node<T>(v);
    if (v < node->data)      node->left  = insert(node->left,  v);
    else if (v > node->data) node->right = insert(node->right, v);
    return node;
}

template <typename T>
bool search(Node<T>* node, const T& v) {
    while (node != nullptr) {
        if (v == node->data) return true;
        node = (v < node->data) ? node->left : node->right;
    }
    return false;
}

int main() {
    const int N = 100000;

    // Skewed: insert terurut 0..N-1
    Node<int>* skewed = nullptr;
    for (int i = 0; i < N; ++i) skewed = insert(skewed, i);

    // Balanced: insert acak
    std::vector<int> perm(N);
    std::iota(perm.begin(), perm.end(), 0);
    std::mt19937 rng(42);
    std::shuffle(perm.begin(), perm.end(), rng);

    Node<int>* balanced = nullptr;
    for (int v : perm) balanced = insert(balanced, v);

    // Cari N-1 di kedua tree
    auto t1 = std::chrono::high_resolution_clock::now();
    volatile bool fs = search(skewed, N - 1);
    auto t2 = std::chrono::high_resolution_clock::now();
    volatile bool fb = search(balanced, N - 1);
    auto t3 = std::chrono::high_resolution_clock::now();

    auto us_skewed   = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    auto us_balanced = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    std::cout << "Cari " << (N - 1) << " di skewed BST   : " << us_skewed   << " us\n";
    std::cout << "Cari " << (N - 1) << " di balanced BST : " << us_balanced << " us\n";
    std::cout << "Rasio skewed / balanced : " << (us_balanced == 0 ? 0 : us_skewed / us_balanced) << "x\n";
    return 0;
}

Output yang Dihasilkan:

text
Cari 99999 di skewed BST   : 377 us
Cari 99999 di balanced BST : 2 us
Rasio skewed / balanced : 188x

Skewed BST: insert terurut 0..N-1 menghasilkan right-skewed tree height N-1. Search N-1 butuh N langkah linear.
Balanced BST: insert dengan urutan acak menghasilkan tree dengan height mendekati log₂(N) ≈ 17 untuk N = 100000. Search N-1 butuh ~17 langkah.
Rasio 188x: pada N = 100000, skewed BST ~188 kali lebih lambat daripada balanced BST. Selisih ini tumbuh linear — untuk N = 1 juta, rasio bisa mencapai ribuan kali lipat.

Self-Balancing BST: Ringkasan #

Berikut kategori utama self-balancing BST yang akan dibahas di chapter selanjutnya:

Struktur	Strategi	Height terjamin	Worst insert
AVL Tree	Balance factor + rotasi	≤ 1.44 log n	O(log n), banyak rotasi
Red-Black Tree	Pewarnaan + rotasi	≤ 2 log n	O(log n), sedikit rotasi
Splay Tree	Move-to-root	Tidak terjamin amortized	O(log n) amortized
Treap	Random priority + heap	O(log n) expected	O(log n) expected

Ringkasan #

Skewed BST memiliki height O(n) — seburuk linear search. Operasi search/insert/delete menjadi O(n).
Balance factor (BF) = height(left) - height(right). Node balanced bila |BF| ≤ 1.
Implementasi naif is_balanced O(n²) karena setiap node memanggil height. Optimal: simpan height pada node, hitung BF O(1).
Dua kategori balanced tree: height-balanced (AVL, |BF| ≤ 1) dan weight-balanced (BB[α], rasio ukuran).
Empat self-balancing BST populer: AVL, Red-Black, Splay, Treap. std::map/std::set memakai Red-Black Tree — menjamin operasi O(log n) terlepas urutan input.