Balanced Trees: AVL, Red-Black & B-Trees

A Binary Search Tree (BST) promises O(log n) search because at each node, you eliminate half the remaining candidates. This promise is only kept when the tree is balanced — when the height h ≈ log₂ n.

The height of a tree is the length of the longest root-to-leaf path. For a perfect binary tree with n nodes, h = ⌊log₂ n⌋. For a degenerate tree (a right-chain), h = n − 1.

Consider building a BST by inserting {1, 2, 3, 4, 5} in order. Each new key is larger than all previous keys, so every insertion goes right. The resulting tree is a right-leaning chain: search for 5 requires visiting all 5 nodes. This is O(n), not O(log n).

The core insight: the shape of a BST is determined by insertion order, and many real-world sequences (sorted IDs, timestamps, alphabetical strings) produce degenerate or near-degenerate trees. A self-balancing BST solves this by performing cheap restructuring operations — rotations — after insertions and deletions to keep height bounded.

Key theorem: If a BST on n nodes has height h, then search/insert/delete take Θ(h) time. All three balanced-tree families guarantee h = O(log n), giving Θ(log n) worst-case operations.

# Illustrate height degradation
def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

# Inserting 1..8 in sorted order into a plain BST
# produces a right chain: height = 7 (n-1)
# Inserting the same keys in level-order
# produces a perfect tree: height = 2 (log2(8)-1)

A rotation is a local restructuring of three nodes that changes the tree's shape while preserving the BST property. There are two kinds: left rotation and right rotation. They are inverses of each other.

Right rotation at node y (y has a left child x):

    y              x
   / \            / \
  x   C    →    A   y
 / \                / \
A   B              B   C

After a right rotation at y: x becomes the new subtree root, y becomes x's right child, and B (x's old right subtree) becomes y's new left child.

Why does this preserve the BST property? Because in the original tree: keys(A) < x < keys(B) < y < keys(C). After rotation: keys(A) < x, x's right child is y, y's left subtree is B, y's right subtree is C. So keys(A) < x < keys(B) < y < keys(C) — unchanged. The in-order traversal is identical before and after.

Left rotation is the mirror: at node x with right child y, y becomes the new root, x becomes y's left child, and y's old left subtree becomes x's new right child.

Rotations run in O(1) time (only a constant number of pointer changes). They are the only restructuring primitive used by AVL and red-black trees. The entire art of self-balancing is knowing when to rotate and which rotation to apply.

Important: a single rotation changes height by at most 1. To fix a large imbalance, we sometimes need a double rotation — two rotations in sequence.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.height = 1  # for AVL

def rotate_right(y):
    x = y.left
    B = x.right
    # Perform rotation
    x.right = y
    y.left = B
    # Update heights (AVL)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x  # new subtree root

def rotate_left(x):
    y = x.right
    B = y.left
    y.left = x
    x.right = B
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

An AVL tree (Adelson-Velsky and Landis, 1962) is the original self-balancing BST. Its invariant is beautifully simple:

AVL Invariant: For every node, the heights of its left and right subtrees differ by at most 1.

Define the balance factor of a node as: bf(v) = height(v.right) − height(v.left). The AVL invariant requires bf(v) ∈ {−1, 0, +1} for every node v.

Height bound: An AVL tree on n nodes has height at most 1.44 log₂(n+2). This is derived via Fibonacci trees (the worst-case AVL shape), which are the thinnest possible AVL trees. Concretely, an AVL tree with a million nodes has height at most ≈29. A balanced binary tree would have height 20 — so AVL costs at most 44% overhead in height.

Insertion: Insert as in a regular BST, then walk back up to the root updating heights. At the first ancestor where |bf| becomes 2, apply one of four rotation cases to restore balance. Crucially, once you fix the first violation, all ancestors are automatically balanced — you need at most O(log n) height updates and at most 2 rotations per insertion.

The four imbalance cases (all symmetric — only two conceptually distinct cases):

1. Left-Left (bf = −2, left child bf = −1): single right rotation at the unbalanced node.
2. Right-Right (bf = +2, right child bf = +1): single left rotation.
3. Left-Right (bf = −2, left child bf = +1): left rotation at left child, then right rotation at node. (Double rotation)
4. Right-Left (bf = +2, right child bf = −1): right rotation at right child, then left rotation at node. (Double rotation)

Deletion is more involved: after deleting a node (using the standard BST deletion), walk upward and fix all violations. Unlike insertion, deletion may require O(log n) rotations in the worst case (though each is O(1)).

Trade-offs: AVL's strict balance makes search very fast (shorter trees than red-black). But the strict invariant means more rotations during insertion/deletion compared to red-black trees. AVL trees are preferred for read-heavy workloads.

def get_height(node):
    return node.height if node else 0

def get_bf(node):
    return get_height(node.right) - get_height(node.left)

def rebalance(node):
    bf = get_bf(node)
    if bf == -2:  # left-heavy
        if get_bf(node.left) > 0:  # Left-Right case
            node.left = rotate_left(node.left)
        return rotate_right(node)  # Left-Left case
    if bf == 2:   # right-heavy
        if get_bf(node.right) < 0:  # Right-Left case
            node.right = rotate_right(node.right)
        return rotate_left(node)  # Right-Right case
    return node  # already balanced

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node  # duplicate
    node.height = 1 + max(get_height(node.left), get_height(node.right))
    return rebalance(node)

A red-black tree relaxes AVL's strict balance in exchange for cheaper writes. Each node carries a color — red or black — and the tree maintains five invariants:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL sentinel) is black.
4. If a node is red, both its children are black. (No two consecutive red nodes.)
5. For every node v, all simple paths from v to descendant leaves contain the same number of black nodes. This count is called the black-height bh(v).

Height bound: A red-black tree with n internal nodes has height at most 2 log₂(n+1). Proof sketch: by property 5, every root-to-leaf path has the same black-height bh. By property 4, at most half the nodes on any path are red. So bh ≥ h/2, which gives h ≤ 2 bh ≤ 2 log₂(n+1).

Intuition via 2-3-4 trees: A red-black tree is an encoding of a 2-3-4 tree (a B-tree of order 4). A red node and its black parent represent a single 3-node or 4-node in the 2-3-4 tree. This correspondence is the deep reason why red-black trees work: they inherit the perfect balance of 2-3-4 trees.

Insertion: Insert as a red node (to avoid violating property 5). This may create a red-red violation (property 4). Fix it with recoloring and rotations, propagating upward. There are 3 structurally distinct cases:

• Case 1 (uncle is red): Recolor parent and uncle black, grandparent red. Move the violation up two levels.
• Case 2 (uncle is black, triangle shape): Rotate parent toward the violation to convert to Case 3.
• Case 3 (uncle is black, line shape): Rotate grandparent away from the violation and swap colors of parent and grandparent.

Insertion requires at most 2 rotations and O(log n) recolorings.

Deletion is the hard case — it requires up to 3 rotations and up to O(log n) fixup steps. This is why red-black trees have a reputation for tricky implementation.

Why red-black over AVL? Red-black trees are preferred when writes are frequent. The Linux kernel's CFS scheduler stores processes in a red-black tree sorted by virtual runtime — every context switch is an insertion/deletion, so minimizing rotation count matters.

# Pseudocode for RB-Insert-Fixup (from CLRS)
# z is the newly inserted red node
def rb_insert_fixup(T, z):
    while z.parent.color == RED:
        if z.parent == z.parent.parent.left:  # parent is left child
            y = z.parent.parent.right  # uncle
            if y.color == RED:           # Case 1: uncle is red
                z.parent.color = BLACK
                y.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.parent
            else:
                if z == z.parent.right:  # Case 2: triangle
                    z = z.parent
                    left_rotate(T, z)
                # Case 3: line
                z.parent.color = BLACK
                z.parent.parent.color = RED
                right_rotate(T, z.parent.parent)
        else:  # symmetric: parent is right child
            # ... mirror of above ...
            pass
    T.root.color = BLACK

Both AVL and red-black trees guarantee O(log n) operations, but their constants differ in practically important ways.

Use AVL when: the workload is read-heavy (many lookups, few inserts/deletes), and you want the shortest possible tree. Example: an in-memory dictionary that is built once and queried millions of times.

Use red-black when: the workload is write-heavy or balanced read/write. Example: std::map (C++ STL), Java's TreeMap/TreeSet, Linux's process scheduler, interval trees for memory management.

An important practical note: in modern hardware, the difference in height (1.44 vs 2 times log n) often matters less than cache behavior. Both trees have terrible cache locality compared to B-trees for large datasets, because each node is a separate heap allocation. For in-memory data structures where n fits in L3 cache, the difference is negligible. For n in the millions on disk, neither AVL nor red-black is appropriate — that is where B-trees dominate.

When your data does not fit in RAM, binary trees become catastrophically slow. A hard disk read is ~10 ms; an SSD read is ~0.1 ms; a RAM access is ~100 ns. If each tree node requires one disk read, and you have 1 million records, a balanced binary tree needs ~20 disk reads per lookup. On a spinning disk that's 200 ms per query — unacceptably slow for a database.

The key insight: disk I/O is block-oriented. A single disk read fetches a page of data (typically 4KB–16KB), not a single byte. If a tree node fits in one page, you pay the same cost whether the node holds 1 key or 1000 keys. So we should make each node hold as many keys as fit in a page — increasing the fanout (number of children) dramatically reduces tree height.

A B-tree of order t (minimum degree t) satisfies:

1. Every non-root node has at least t−1 keys (at least t children).
2. Every node has at most 2t−1 keys (at most 2t children).
3. All leaf nodes are at the same depth (perfect balance!).
4. The keys within a node are stored in sorted order.
5. A node with k keys has exactly k+1 children (for internal nodes).

Height bound: A B-tree with n keys and minimum degree t has height h ≤ log_t⌈(n+1)/2⌉. With t = 1000 and n = 10⁹, h ≤ 3. Three disk reads to find any key among a billion records.

Search: Navigate from root to leaf. At each node, binary-search (or scan) the sorted keys to find the right child pointer. O(log_t n) nodes visited, O(log t) comparisons per node — total O(log n) comparisons.

Insertion: Find the leaf where the key belongs. If the leaf has room (< 2t−1 keys), insert directly. If full, split the node: the median key moves up to the parent, and the node splits into two nodes of t−1 keys each. The split may cascade upward. Crucially, B-tree insertion works top-down: as you traverse the tree to find the insertion point, you pre-emptively split any full nodes you encounter. This ensures the parent always has room to receive the promoted key. Result: insertions require O(h) disk reads/writes = O(log_t n).

Deletion is more complex: if a key is deleted and the node falls below t−1 keys, either borrow a key from a sibling (via the parent) or merge with a sibling.

# B-tree search (pseudocode)
def btree_search(node, k):
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
    if i < len(node.keys) and k == node.keys[i]:
        return (node, i)  # found
    if node.is_leaf:
        return None       # not found
    # Fetch child from disk (disk read!)
    child = disk_read(node.children[i])
    return btree_search(child, k)

# The expensive operation is disk_read() — this is why
# minimizing the number of nodes visited (via high fanout)
# is the whole point of B-trees.

Most databases use a variant called a B+ tree, not a plain B-tree. The difference:

• In a B-tree, keys appear in internal nodes AND leaves. A search can terminate at an internal node if it finds the key.
• In a B+ tree, all data lives in the leaves. Internal nodes contain only routing keys (copies of keys used to direct searches). All leaves are linked together in a doubly-linked list.

Why B+ trees dominate databases:

1. Range queries: SELECT * FROM orders WHERE date BETWEEN '2024-01-01' AND '2024-12-31' requires visiting every key in a range. In a B+ tree, find the starting leaf, then walk the leaf linked list. In a plain B-tree, you'd need an in-order traversal involving internal nodes — much messier. Range scans are a core database operation and B+ trees make them a simple linked-list traversal.

2. Higher fanout: Internal nodes store only keys (no data records), so they are smaller, so more keys fit per page, so the tree is shallower. A typical B+ tree internal node with 8-byte keys and 8-byte pointers on a 4KB page holds ~250 entries. With t ≈ 250, a three-level tree holds 250³ ≈ 15 million keys. The root can often be kept in RAM permanently.

3. Simpler internal structure: Since internal nodes don't hold data, deletion from internal nodes never removes data — you just update routing keys. This simplifies the deletion algorithm.

PostgreSQL, MySQL InnoDB, SQLite all use B+ trees for their primary indexes. InnoDB's primary key index is a clustered B+ tree: the leaf pages contain the actual row data, not just a pointer to it. Secondary indexes in InnoDB store the primary key as the value, so a secondary index lookup requires two B+ tree traversals.

Filesystem B-trees: HFS+, NTFS, ext4 (htree), XFS, and Btrfs all use B-trees or B+ trees for directory entries and extent maps. When you list a directory with 100,000 files, the filesystem descends a B-tree rather than doing a linear scan.

-- Demonstrating why B+ tree range scans are efficient:
-- A BETWEEN query in PostgreSQL will:
--   1. Descend the B+ tree to find the first matching leaf (O(log n))
--   2. Walk the linked leaf list until the range ends (O(k) for k results)
-- Total: O(log n + k) -- optimal!

EXPLAIN SELECT * FROM orders
WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31';
-- PostgreSQL output:
-- Index Scan using orders_date_idx on orders
--   Index Cond: (order_date >= '2024-01-01' AND order_date <= '2024-12-31')
-- This is exactly a B+ tree descent + leaf chain walk.

Understanding why B-tree operations preserve the invariant is essential for understanding why the tree remains balanced after thousands of mutations.

The split operation is the heart of B-tree insertion. When a node v is full (has 2t−1 keys), we split it:

1. The median key (at index t−1) moves up to v's parent.
2. v is split into two nodes: the left half (keys 0..t−2) stays as v; a new right node gets keys t..2t−2.
3. The parent gains one key and one additional child pointer.

Why this preserves the B-tree invariant:

• After split, each half-node has exactly t−1 keys — exactly the minimum. ✓
• The parent gains one key. If the parent was not full (< 2t−1 keys), no further action needed. ✓
• If the parent was full... but the top-down insertion algorithm pre-splits full nodes on the way down, so the parent is never full when we try to insert into it. ✓
• All leaves remain at the same depth, because we only create new nodes by splitting (horizontally) or by creating a new root (increasing depth uniformly). ✓

Root splitting is special: when the root is full, we create a new root, make the old root its only child, and then split the old root. This is the only way a B-tree grows taller, and it grows from the top — every leaf moves one level deeper simultaneously, preserving perfect leaf depth.

Analogy: Think of the tree as a company org chart. When a manager's team gets too large (node full), they are promoted and their team is split between two new managers (split). The CEO only gets promoted when absolutely necessary (root split), and when it happens, everyone moves one level down simultaneously.

Merge operation (for deletion) is the inverse of split: if a node has only t−1 keys and its sibling also has t−1 keys, merge them with the separator key from the parent into a single node with 2t−2 keys (then remove the separator from the parent, which may cascade). This preserves minimum occupancy.

# B-tree split (Python pseudocode)
def split_child(parent, i):
    """Split parent.children[i] which is full (has 2t-1 keys)."""
    t = parent.t
    full_child = parent.children[i]
    new_child = BTreeNode(t, is_leaf=full_child.is_leaf)

    # new_child gets the upper half of full_child's keys
    new_child.keys = full_child.keys[t:]       # keys t..2t-2
    full_child.keys = full_child.keys[:t-1]    # keys 0..t-2

    if not full_child.is_leaf:
        new_child.children = full_child.children[t:]
        full_child.children = full_child.children[:t]

    # Median key moves up to parent
    median = full_child.keys[t-1] if ... else ...  # before truncation
    parent.keys.insert(i, median)
    parent.children.insert(i+1, new_child)
    disk_write(full_child)
    disk_write(new_child)
    disk_write(parent)

We said AVL deletion needs O(log n) rotations worst-case and red-black insertion needs O(log n) recolorings. Does this mean they are expensive on average? No — amortized analysis shows that a sequence of m operations on an n-node tree costs O(m log n) total, and in many practical scenarios much less.

The potential method is a powerful amortized analysis technique. Define a potential function Φ that measures how "close to trouble" the data structure is. The amortized cost of an operation is its actual cost plus the change in potential: â_i = c_i + Φ_i − Φ_{i-1}.

For red-black trees, one can define Φ as the number of red nodes with a black parent that have a red uncle (roughly, the number of potential Case 1 recolorings needed). An insertion increases Φ by at most 1 and each Case 1 recoloring decreases Φ by at least 1 while doing O(1) work — so the amortized cost per insertion is O(1) recolorings amortized, even though the worst-case is O(log n).

Practical takeaway: In a long sequence of insertions into a red-black tree, the O(log n) recoloring worst case is rare. Most insertions hit Cases 2 or 3 (which terminate immediately) or do a small number of Case 1 recolorings. Empirical measurements show fewer than 3 rotations per insertion on average.

For B-trees in databases, the amortized analysis is even more favorable: splits are rare because nodes are only split when full. With t = 100, a node must have 199 keys inserted before it splits — and splits propagate upward only when parents are also full, which is even rarer. In practice, B-tree operations almost never touch more than 3-4 nodes even for millions of keys.

One of the most powerful ideas in data structures is augmentation: store additional information in each BST node to support new query types, while maintaining balance as before.

Order-statistic trees augment each node with size = number of nodes in its subtree. This supports:

• rank(x): how many elements are ≤ x? O(log n)
• select(k): find the k-th smallest element. O(log n)

When rotating, update sizes in O(1): after a rotation, the children's sizes are unchanged but the rotated nodes' sizes must be recomputed from their children. Since rotations only affect a constant number of nodes, augmentation does not increase the asymptotic complexity.

Interval trees augment each node (which stores an interval [lo, hi]) with max_hi = the maximum hi value in the subtree. A query "find an interval overlapping [a, b]" descends the tree in O(log n) by checking if the left subtree's max_hi ≥ a (if so, there might be an overlap there).

The Linux kernel's mm_struct uses an interval tree (red-black augmented) to store virtual memory areas (VMAs). When handling a page fault at address x, the kernel descends this interval tree to find the VMA containing x in O(log n) instead of O(n) linear search.

The augmentation theorem (CLRS Theorem 14.1): If information f(v) stored at node v can be computed from v's key, v's augmented information, and the augmented information of its children, then augmenting a red-black tree with f preserves O(log n) insert/delete.

# Order-statistic tree: size-augmented AVL insert
def insert(node, key):
    if node is None:
        return Node(key)  # size = 1
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    # Update size BEFORE rebalancing
    node.size = 1 + size(node.left) + size(node.right)
    node.height = 1 + max(height(node.left), height(node.right))
    return rebalance(node)  # rotations must also update size!

def select(node, k):
    """Return k-th smallest element (1-indexed)."""
    left_size = size(node.left)
    if k == left_size + 1:
        return node.key
    elif k <= left_size:
        return select(node.left, k)
    else:
        return select(node.right, k - left_size - 1)