Balanced Trees

A binary search tree costs its height, and its height depends on the order the keys arrived in. A balanced tree removes that dependence. After every insert and delete it checks a local rule, and when the rule is broken it repairs the shape with a rotation, which moves nodes around without changing the order of the keys.

The result is a guaranteed O(log n) for lookup, insert and delete, whatever the input. It is the structure under Java's TreeMap, C++'s std::map and the Linux scheduler's queue of runnable tasks, and it is the answer to the sorted-input disaster of the previous topic.

A Guarantee on Height

Every operation on a search tree walks one path from the root down, so a guarantee on height is a guarantee on everything. "Balanced" never means perfect. Keeping a tree perfectly balanced would mean rebuilding large parts of it on some inserts, at a cost of O(n). A balanced tree only promises that its height stays within a constant factor of the base-2 logarithm of n.

That promise is enough. It turns the million-level chain of the previous topic into a tree somewhere between 20 and 40 levels deep, depending on the design. Measured on Python 3.15 with a textbook red-black tree, a million keys inserted in sorted order, the worst input for a plain tree, produced 37 levels. The same million keys in random order produced 24.

Rotations

A rotation lifts a child into its parent's place. In a right rotation, the left child x rises above its parent y, y becomes x's right child, and the subtree that sat between them, everything larger than x and smaller than y, moves across to become y's left child. Read the tree in order before and after and the sequence is the same: subtree A, then x, then subtree B, then y, then subtree C.

So a rotation makes one side shorter and the other taller while the ordering rule keeps holding. It rewrites three pointers and costs O(1), whatever the size of the subtrees it moves. Every balanced binary tree is a rule about when to rotate.

AVL Trees: Strict Balance

The first balanced tree was published in 1962 by Georgy Adelson-Velsky and Evgenii Landis, and it carries their initials. An AVL tree keeps the heights of every node's two subtrees within one of each other. Each node stores its height or the difference between its children's heights, and an insert that breaks the rule is repaired on the way back up.

The strict rule holds the height below about 1.44 times the base-2 logarithm of n, so a million keys need at most 29 levels. Lookups are as short as a binary tree gets. An insert needs at most one single or double rotation to restore the rule. A delete is less tidy: it may need a rotation at every level on the way back to the root.

Red-Black Trees: Looser Balance, Cheaper Changes

A red-black tree colours every node red or black and keeps three promises. The root is black. No red node has a red child. Every path from a node down to the empty links below it passes the same number of black nodes. The design came from Leonidas Guibas and Robert Sedgewick in 1978, building on Rudolf Bayer's symmetric binary B-trees of 1972.

Together the rules keep the longest path within twice the shortest, so the height stays below twice the base-2 logarithm of n plus one: about 40 levels for a million keys. In exchange for that looser shape, an insert needs at most two rotations and a delete at most three, plus some recolouring on the way up. Bounded, small repair work on every update is why most standard libraries choose red-black trees.

Where They Run

Java's TreeMap and TreeSet are red-black trees, and so are the tree bins inside Java's HashMap: once one bucket grows past eight entries in a table of at least 64 buckets, the bucket turns its list into a small red-black tree, so a flood of colliding keys (Chapter 5) costs log n per lookup instead of n. C++'s std::map and std::set are red-black trees in all three major standard libraries: GCC's, LLVM's and Microsoft's. The Linux kernel keeps runnable tasks in a red-black tree ordered by a key computed from each task's virtual time, which Chapter 10 returns to, and uses the same tree for many other indexes.

Python ships no balanced tree in its standard library. A dict keeps insertion order, not key order. The popular third-party sortedcontainers package is not a tree at all: it keeps a list of sorted lists, because contiguous lists of about a thousand items each are kinder to the cache than a node per key, for the reasons Chapter 4 gives.

The Cost in a System You Run

The guarantee is paid in memory and in misses. Each node carries its key, two child pointers and a colour or a height, all in its own allocation, so a million-key ordered index in a language like Java or C++ spends tens of megabytes on pointers and bookkeeping before counting the keys. Each of the 20 to 40 levels of a lookup is a pointer hop to wherever that node was allocated, and each hop can be a cache miss of about 100 nanoseconds.

A balanced binary tree is the right answer when the input order is hostile or unknown and updates are frequent: an in-memory index taking inserts and deletes all day, a scheduler, a timer list that needs ordered traversal. It is the wrong answer when data is read far more often than written, where a sorted array searched by halving (Chapter 7) is denser and faster, and when data lives on disk, where the B-tree at the end of this chapter replaces 20 page reads with three.