Balanced search trees

A binary search tree is only as fast as it is short. Insert keys in sorted order and an unbalanced BST becomes a linked list: every operation O(n). Balanced trees fix this with one cheap local operation — the rotation — applied after updates so the height stays O(log n) no matter what order keys arrive in. This lesson builds an AVL tree, explains red-black trees (what std::map is), and sketches the alternatives.

1. Why balance

A BST's operations walk one root-to-leaf path, so they cost O(height). For n keys:

Sorted input, reverse-sorted input, or "mostly sorted" input (timestamps, IDs) all build the worst case. A balanced tree promises height c · log₂ n for a small constant c, whatever the input order: about 1.44 for AVL, 2 for red-black.

2. Rotations

A rotation changes the shape of three links and keeps the in-order sequence — and so the BST order — exactly the same:

x moves up, y moves down, and the subtree B (keys between x and y) changes parent. Heights change only for x and y, so a rotation is O(1).

With unique_ptr ownership, the order of the moves matters — every assignment to a unique_ptr destroys what it held:

#include <memory>
#include <print>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

void rotate_right(std::unique_ptr<Node>& slot) {
    std::unique_ptr<Node> x = std::move(slot->left);  // 1. take x out of y
    slot->left = std::move(x->right);                 // 2. B becomes y's left
    x->right = std::move(slot);                       // 3. y becomes x's right
    slot = std::move(x);                              // 4. x takes y's place
}

void print_inorder(const Node* n) {
    if (!n) return;
    print_inorder(n->left.get());
    std::print("{} ", n->key);
    print_inorder(n->right.get());
}

int main() {
    // y = 4 with left child x = 2 (children 1, 3) and right child 5.
    auto root = std::make_unique<Node>(4);
    root->left = std::make_unique<Node>(2);
    root->left->left = std::make_unique<Node>(1);
    root->left->right = std::make_unique<Node>(3);
    root->right = std::make_unique<Node>(5);

    print_inorder(root.get());
    std::println("  root {}", root->key);
    rotate_right(root);
    print_inorder(root.get());
    std::println("  root {}", root->key);   // same order, new root 2
}

A tempting shortcut — keep a raw Node* x = slot->left.get() and then assign to slot->left — destroys x in step 2 and leaves you with a dangling pointer.

3. AVL trees

An AVL tree (Adelson-Velsky and Landis, 1962) stores each node's height and keeps every node's balance factor

balance(n) = height(n.left) - height(n.right)   ∈ { -1, 0, +1 }

An insert or erase changes one subtree's height by at most one, so on the way back up an ancestor can reach ±2. Four cases fix it:

A single rotation can't fix a zig-zag: it just mirrors it. That's why the "inner" cases need two.

Worked example: rebalance on the way up

Insert and erase are an ordinary recursive BST over the owning slots, plus one call after the recursive step. Recursion is fine here: the height is O(log n), so the depth is tiny.

#include <algorithm>
#include <memory>
#include <print>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    int height = 1;
};

int h(const Node* n) { return n ? n->height : 0; }
int balance(const Node* n) { return h(n->left.get()) - h(n->right.get()); }
void update(Node* n) { n->height = 1 + std::max(h(n->left.get()), h(n->right.get())); }

void rotate_right(std::unique_ptr<Node>& slot) {
    std::unique_ptr<Node> x = std::move(slot->left);
    slot->left = std::move(x->right);
    update(slot.get());          // the old top is now the lower node: fix it first
    x->right = std::move(slot);
    slot = std::move(x);
    update(slot.get());
}

void rotate_left(std::unique_ptr<Node>& slot) {
    std::unique_ptr<Node> y = std::move(slot->right);
    slot->right = std::move(y->left);
    update(slot.get());
    y->left = std::move(slot);
    slot = std::move(y);
    update(slot.get());
}

void rebalance(std::unique_ptr<Node>& slot) {
    Node* n = slot.get();
    update(n);
    if (balance(n) > 1) {
        if (balance(n->left.get()) < 0) rotate_left(n->left);    // left-right
        rotate_right(slot);
    } else if (balance(n) < -1) {
        if (balance(n->right.get()) > 0) rotate_right(n->right); // right-left
        rotate_left(slot);
    }
}

void insert(std::unique_ptr<Node>& slot, int key) {
    if (!slot) {
        slot = std::make_unique<Node>(key);
        return;
    }
    if (key < slot->key) insert(slot->left, key);
    else if (slot->key < key) insert(slot->right, key);
    else return;
    rebalance(slot);
}

int main() {
    std::unique_ptr<Node> root;
    for (int k = 1; k <= 1000; ++k) insert(root, k);   // sorted: the worst case for a plain BST
    std::println("1000 sorted keys: height {}, root {}", root->height, root->key);
}

A plain BST would have height 1000 here; the AVL tree has height 10.

Faded example: the mirror case

rotate_left is the mirror image of rotate_right. Write it from the diagram in section 2 without looking above — swap every left and right:

void rotate_left(std::unique_ptr<Node>& slot) {
    std::unique_ptr<Node> y = /* ??? */;
    slot->right = /* ??? */;
    update(slot.get());
    y->left = /* ??? */;
    slot = std::move(y);
    update(slot.get());
}

Erasing

Erase is the BST erase — a leaf or a one-child node is replaced by its child; a two-child node is replaced by its in-order successor — followed by rebalance on every node on the way back up. Unlike insert, one erase can need a rotation at every level: shortening one subtree can unbalance each ancestor in turn.

How tall can an AVL tree get?

Let N(h) be the fewest nodes an AVL tree of height h can have. Its root has one subtree of height h − 1 and, at worst, one of height h − 2:

N(1) = 1,  N(2) = 2,  N(h) = 1 + N(h - 1) + N(h - 2)

That's the Fibonacci recurrence, so N(h) grows like φʰ (φ ≈ 1.618), and inverting it gives h < 1.4405 log₂(n + 2) − 0.3277. A million keys: at most 28 levels.

4. Red-black trees

std::set and std::map in libstdc++, libc++ and MSVC are red-black trees. Every node is red or black, and:

1. Every node is red or black.
2. The root is black.
3. Every leaf (the null children) is black.
4. A red node has no red child.
5. Every path from a node down to its null leaves has the same number of black nodes.

Rules 4 and 5 together mean the longest path (alternating red and black) is at most twice the shortest (all black): height ≤ 2 log₂(n + 1). That's looser than AVL's 1.44, but repairs are cheaper:

• Insert adds a red node. If its parent is red (a rule-4 violation), look at the uncle: if the uncle is red, recolour parent and uncle black and the grandparent red, and continue upward; if the uncle is black, one or two rotations plus a recolour finish the job. At most two rotations per insert.
• Erase needs at most three rotations, against AVL's up to one per level.

Fewer structural changes per update, plus colour bits that fit in spare pointer bits, is why the standard library chose red-black trees: map-heavy workloads mix inserts, erases and lookups, and red-black trees are cheaper to update while still guaranteeing O(log n).

5. Randomised alternatives

Two simpler structures get O(log n) expected time by using randomness instead of strict rules:

• Treap: a BST by key and a heap by a random priority. Rotations restore the heap order after an insert; the tree's shape is that of a random BST, so a node's expected depth is about 1.39 log₂ n.
• Skip list: a sorted linked list with extra "express lanes": each node is promoted to the next level with probability ½. Search drops down a level at a time. Popular in concurrent code (Redis, LevelDB's memtable) because local updates are easy to make lock-free.

6. B-trees and the cache

All the trees above have one key per node, so a search touches log₂ n nodes scattered across memory — log₂ n likely cache misses. A B-tree stores many sorted keys per node (sized to a few cache lines or a disk page), so the height is log_B n with B in the tens or hundreds: a million keys in three or four node visits, each a sequential scan within one node. Databases and filesystems use B-trees; Abseil's btree_map is a drop-in std::map replacement that's often several times faster. Level 10's data-oriented design picks this thread up.

Summary

• Search trees cost O(height); without balancing, sorted input gives height n.
• A rotation re-hangs three links in O(1) and preserves in-order.
• AVL: store heights, keep balance factors in {−1, 0, +1}, fix ±2 on the way back up with one of four cases (two need double rotations). Height < 1.44 log₂ n.
• Red-black: five colour rules, height ≤ 2 log₂ n, at most 2 rotations per insert and 3 per erase — the standard library's choice.
• Treaps and skip lists trade guarantees for simplicity; B-trees trade pointer chasing for cache-friendly fat nodes.