Binary Search Tree Visualizer

A binary search tree keeps one promise. Everything to the left of a key is smaller, everything to the right is larger, and the same holds inside every subtree.

Finding a key is then a walk down from the root: compare, go left or right, repeat. The walk is short only if the tree is.

The promise says nothing about shape, and shape is where the cost lives. Sedgewick and Wayne state it as a proposition: search, insertion, deletion, minimum and maximum all take time proportional to the height of the tree in the worst case. That height can be anything between the logarithm of the number of keys and the number of keys itself. A tree of a thousand keys might be ten levels deep. It might be a thousand.

It takes no malice to build the thousand. Insert keys that are already sorted and each new one hangs off the right side of the last. The result obeys the ordering rule perfectly and is a linked list in every way that matters. Sorted input is not exotic. It is what a log file, a list of invoice numbers or an export from another tree looks like.

Every balanced binary tree is built from a single repair, the rotation. Take a node and one of its children. Lift the child into the parent’s place, let the parent drop to the other side, and hand the child’s inner subtree across to the old parent. Three links change. Nothing else moves.

The reason it is safe is worth saying slowly, because everything later depends on it. The subtree that changes hands holds exactly the keys that lie between the two nodes, and after the move it still sits between them. The Dartmouth course notes state the consequence plainly: a rotation changes only the links, keeps the search-tree ordering, and takes constant time. One side of the pair gets a level shorter and the other a level longer. Balancing a tree is the art of deciding where to spend that trade.

Strict balance and loose balance

The first scheme to decide was published in 1962 by Adelson-Velsky and Landis, and the tree carries their initials. The AVL rule is local and strict: at every node, the two subtrees may differ in height by at most one. Each node stores its height, or just the difference. After an insertion you walk back up the path, refresh the stored heights, and at the lowest node whose sides now differ by two you rotate once, or twice if the heavy child leans the other way.

How tall can such a tree get? The sparsest AVL tree of a given height is built from the sparsest trees of the two heights below it, which is the Fibonacci recurrence, and the golden ratio falls out. The answer is a logarithm to the base of the golden ratio, which works out to about 1.44 lg n, and the fuller statement in the Wikipedia article puts the height in levels below 1.4405 log2(n + 2) - 0.3277. So an AVL tree is never more than about 44 percent taller than a perfect one.

The red-black tree asks for less. Each node carries one extra bit, a color. The root is black, a red node never has a red child, and every path from a node down to an empty link passes the same number of black nodes. Those rules cannot force equal heights. They force something weaker: since reds cannot touch, the longest path can at most alternate colors while the shortest is all black. The NIST dictionary states it as no leaf being more than twice as far from the root as any other, and the bound that follows is 2 lg(n + 1) levels.

What is bought with the slack? Less repair work. An AVL insertion ends with one single or double rotation, but a deletion may have to rebalance at one ancestor after another, all the way up. The Linux kernel’s documentation gives the red-black side of the ledger: the limits are 2 and 3 rotations, two to rebalance after an insertion and three after a deletion, at the price of slightly slower lookups. NIST adds the other half in a single sentence, that an AVL tree is at least as balanced as a red-black tree. Trees that are searched far more than they are changed favor AVL. Trees that churn favor red-black.

The wider tree hiding inside

The red-black rules look arbitrary until you see where they came from. NIST notes that the structure was first called a symmetric binary B-tree, described by Bayer in 1972, and only later given its colors by Guibas and Sedgewick. The name is the explanation. Take any red-black tree, remove each red node, and attach its two children directly to its black parent. Pat Morin’s Open Data Structures walks through what is left: every node has two, three or four children, and every leaf sits at the same depth. That is a 2-4 tree.

Read backwards, a red node is not a node at all. It is a second or third key living in the same wide node as its black parent, and red is the glue. The black-count rule is the wide tree’s promise that all leaves are level. The ban on two reds in a row is its limit of three keys in a node. Sedgewick and Wayne teach the same idea with a narrower tree, calling red links the ones that bind two small nodes into a larger one.

Even the repairs translate. When a wide node overflows it splits and passes a key up to its parent. Morin shows the binary version of that split: color the black node red and its two red children black. That is the recoloring step of red-black insertion, seen from above, and it is why red drifts toward the root. Merging two wide nodes is the same recoloring run backwards. Borrowing a key from a neighbor is the awkward one, and it is where the rotations come in.

Why deletion is the hard part

Insertion adds a leaf, and a leaf is easy to hang. Deletion can aim at a node with two children, which leaves two subtrees and one place to attach them. The classic answer, credited to Hibbard in 1962, is to replace the key with its successor, the smallest key to its right, and remove that node instead. Sedgewick and Wayne point out the flaw: the choice of successor over predecessor is arbitrary and not symmetric, and a long run of random deletions and insertions leaves a plain tree skewed.

In a red-black tree the trouble is color. Unlink a red node and nothing is owed. Unlink a black one and every path through that spot is one black node short. The textbook cure is to imagine an extra black sitting where the node was and to push it upward through four cases on the sibling’s color and its children’s colors, until it meets a red node that can absorb it, reaches the root, or is settled by a final rotation. Sedgewick’s paper on left-leaning red-black trees remarks that deletion was incompletely specified in the original paper, which says something about how long the difficulty has been felt.

From memory to disk

A wide node that holds several keys is a curiosity in memory and a necessity on a disk. The Cornell notes put a disk access at about five milliseconds, which is five million nanoseconds, so the goal is to make each read decide as much as possible. A B-tree stretches the 2-4 idea until a node fills a disk block, and Morin presents it as exactly that generalization. The same notes call its insertion and deletion notoriously difficult to implement correctly.

You have almost certainly used all of these today. Java’s TreeMap is documented as a red-black tree. The Linux kernel lists red-black trees behind its I/O schedulers, high-resolution timers and virtual memory areas. PostgreSQL documents its B-tree index as the standard multi-way balanced tree, SQLite’s file format is built from B-tree pages, and Rust’s standard sorted map is a B-tree because, its documentation argues, one heap allocation and one likely cache miss per key is too much to pay on a modern machine.

Fifteen keys, four trees

Insert the numbers 1 to 15, in order, into each kind of tree. Plain, red-black and AVL finish at 15, 6 and 4 levels. The plain tree is a chain with 14 links. The AVL tree is a perfect triangle and needed 11 rotations to stay that way. The red-black tree needed 9 and sits comfortably inside its bound of 8 levels. The 2-3-4 tree has 3 levels and never rotated; it split nodes instead.

Run the same test with 500 keys and the four heights are 500, 9, 15 and 8. The gap between the first number and the other three is the entire subject.

Balance does have limits. It guarantees the number of steps, not the speed of each one, and Rust’s complaint about pointer-chasing applies to every one-key-per-node tree, balanced or not. It keeps keys in order, which a hash table does not, but pays a logarithm for every lookup that a hash table often avoids. And a bound is a worst case. Sedgewick and Wayne show that keys arriving in random order keep even the plain tree shallow, about 1.39 lg N comparisons for a search, which is why the failure waits quietly until the day the data arrives sorted.