Height Bounds and the Cost of a Degenerate Search Tree

A binary search tree answers a membership query by following one path from the root to a node. Each step compares the query key against a stored key and discards one subtree, so the number of comparisons equals the depth of the node that holds the key, plus one. Nothing else in the structure affects lookup cost: not the number of nodes, not the shape of subtrees that are never visited, not the ordering of keys inside those subtrees. A tree of a million nodes whose every path is twenty links long answers a query in at most twenty comparisons. A tree of a thousand nodes arranged as a chain needs up to a thousand.

That single observation is the whole motivation for balancing. The interesting part is that the naive insertion algorithm does not merely have a bad worst case that rarely occurs; it produces that worst case for input that arrives in any sorted order, which is common in practice, and the tree then keeps the damage forever.

The recurrence that defines search cost

Search cost decomposes into two quantities that are often conflated. The first is the cost of a single query, bounded by the height of the tree. The second is the total cost of a batch of queries, which depends on the sum of all depths, called the internal path length.

For a tree with n nodes, let h be the height measured in edges: a tree with one node has height 0. The worst-case number of comparisons for a successful search is h + 1, and for an unsuccessful search it is h + 1 as well if external leaves are counted, since the search falls off the bottom of a longest path. The total comparison count over all n keys is the internal path length plus n. A balanced tree has internal path length Θ(n log n); a chain has Θ(n²).

The two measures diverge sharply for shapes that are shallow on average but deep somewhere. A tree can have most of its nodes at depth 2 and one path of length 40; the batch cost looks fine while the single-query bound is terrible. Because a lookup is an individual operation with a latency the caller observes, the height is the quantity that matters for a search structure, and the invariant a balanced tree maintains is always a bound on height, or on something that implies one.

Sorted input turns the tree into a path

The textbook insertion procedure is four lines: descend by comparison until a null child slot is found, then attach a new leaf there. It has no mechanism that could notice the tree is becoming lopsided, because the only information it uses is the comparison result at each step.

typedef struct node {
    int key;
    struct node *left, *right;
} node;

/* Iterative insert; returns the root, which changes only on the first call. */
node *insert(node *root, int key) {
    node **slot = &root;
    while (*slot != NULL) {
        slot = (key < (*slot)->key) ? &(*slot)->left : &(*slot)->right;
    }
    *slot = calloc(1, sizeof(node));
    (*slot)->key = key;
    return root;
}

Feed this function the keys 1, 2, 3, …, n in order. Each new key is larger than every stored key, so every comparison sends the descent to the right child, and the tree becomes a right-leaning chain of height n − 1. A lookup for the largest key performs n comparisons and follows n pointers. The same code fed a random permutation produces a tree of height Θ(log n); the algorithm is identical, and the difference is entirely in the input order.

Sorted arrival is not an exotic case. Keys generated from a sequence number, a timestamp, an auto-incrementing identifier, or a file read in byte order all arrive sorted. Reversing the input does not help: it produces a left-leaning chain instead. Inserting the median first and then alternating outward would build a balanced tree, but the tree has no way to know the median of keys it has not yet seen.

Deletion makes the asymmetry permanent. Removing the smallest key from a chain leaves a chain. The standard deletion for a node with two children replaces it with its in-order successor, which in a chain is its immediate right child, so the shape persists across arbitrary sequences of insertions and deletions once it has formed. There is no self-correcting pressure in an unbalanced tree.

What a balance invariant must pin down

A balance condition has to do three things at once, and the difficulty is that they pull against each other.

First, it must imply a logarithmic height bound. A condition that merely forbids long chains locally does not compose: a tree in which every node has two children of depths differing by at most one is exactly an AVL tree and has height at most about 1.44 log₂ n, but weaker local conditions admit linear height.

Second, it must be repairable in O(log n) work after a single insertion or deletion. The repair typically consists of rotations along the path back to the root, which is why rotation mechanics are the primitive that every scheme in this cluster shares.

Third, it must be checkable and maintainable without storing unbounded auxiliary state. The three classical answers differ in what they store per node: AVL trees store a height or balance factor, which is a small integer; red-black trees store one bit of colour; weight-balanced trees store a subtree size. Each choice buys a different constant in the height bound and a different cost per update.

The height bounds themselves are worth stating precisely, because the constants are what distinguish the schemes in practice. An AVL tree with n nodes has height at most about 1.4405 log₂(n + 2) − 0.3277 edges. The bound follows from a recurrence on the minimum number of nodes in an AVL tree of height h: such a tree needs N(h) = N(h−1) + N(h−2) + 1 nodes, with N(0) = 1 and N(1) = 2, which is a Fibonacci recurrence, so N(h) = F(h+3) − 1. Inverting it gives the logarithmic bound.

A red-black tree with n nodes has height at most 2 log₂(n + 1). The argument is different: every root-to-leaf path contains the same number of black nodes, call it bh, so the tree has at least 2^bh − 1 internal nodes, and no path can have more than twice as many nodes as it has black ones.

The gap between the two constants is the design trade. Red-black trees permit roughly 40 percent more depth than AVL trees in the worst case, and in exchange they need fewer rotations per update, because their invariant is coarser and tolerates shapes that an AVL tree would have to repair immediately. That trade is examined in red-black colouring as a height proxy.

Depth under random insertion, and why it is not enough

Fed a uniformly random permutation of n distinct keys, the naive tree has expected height about 4.311 ln n, which is roughly 2.99 log₂ n, and the expected internal path length is about 2n ln n, or 1.386 n log₂ n. The expected depth of the node holding a randomly chosen key is about 2 ln n, or about 1.4 times the log₂ n of an optimal tree. These results are asymptotic; the exact expected height of a random binary search tree is a hard quantity, and the 4.311 constant comes from Devroye’s analysis.

The distribution is the problem. Random-permutation insertion gives a good expected height, but the variance is large and the guarantee is probabilistic, so it says nothing about any particular tree. A structure serving latency-sensitive queries cannot quote an average over insertion orders it does not control. Worse, a tree built from random input can be pushed toward a chain by later operations if keys arrive in an order that correlates with time, and the drift is invisible without instrumentation, because the tree still answers queries correctly.

A randomized tree — one that assigns each node a random priority and enforces heap order on those priorities — gives a height bound that holds with high probability regardless of insertion order. A treap built this way is equivalent in distribution to a tree built by random insertion, but the randomness lives in the structure rather than in the input stream, so an adversary who chooses keys cannot force a bad shape. The probability of exceeding c log n decays exponentially in c. This is the argument behind randomized balancing with treaps.

What breaks when height is unbounded

Linear height is not an abstract slowdown; it changes the resource profile of a single query.

Each descent step follows a pointer to a separately allocated node. A pointer chase into a node that is not in cache costs on the order of a hundred cycles on a conventional machine, because the access pattern is effectively random with respect to key distribution. A lookup of depth 20 costs roughly twenty such misses; a lookup of depth 1,000,000 costs roughly a million. The difference is not a constant factor but the viability of the structure.

Stack depth is a second limit. A recursive search on a chain of n nodes uses n stack frames. Each frame of a few dozen bytes exhausts an 8 MiB stack somewhere around a hundred thousand frames, so a chain in the millions overflows a typical thread stack. An iterative descent avoids this, which is why the insertion code above is a loop, but any recursive traversal — in-order enumeration, validation, destruction — inherits the height as its stack bound.

Cache behaviour is a third. A balanced tree of a million nodes has depth near 20, and each level touches a different cache line, so a lookup takes about 20 misses. That is already the dominant cost, which is why packing many keys per node, discussed under B-tree node layouts and branching factors, can beat binary trees despite more comparisons per level.

The invariant as a contract between operations

A balance invariant is a contract with two halves. The static half says which shapes are legal; the dynamic half says every operation maps a legal shape to a legal shape at O(log n) cost.

Presentations emphasize the static half and treat repair as an implementation detail, which obscures why the invariants are chosen as they are. A condition that is easy to state, such as “the two subtree heights differ by at most one”, is also relatively expensive to restore: it holds at one node of a violating pair only after the heights below are known, so a deletion can require a repair at every level of the path back to the root. A slightly weaker condition, such as “no path has more than twice the black-node count of any other”, is restored with a bounded number of local recolourings and at most a constant number of rotations, with the recolouring propagating instead of the restructuring. The weaker invariant buys cheaper repair at the price of a looser height bound, and both remain logarithmic.

The halves also determine the metadata per node, and therefore the memory overhead per key. A height field costs a machine word unless packed into spare bits; a colour costs one bit, usually hidden in the low bit of a child pointer, since node addresses are aligned to at least 4 bytes and often 8. On a 64-bit machine with 8-byte keys, a node with two child pointers, one key, and a packed colour occupies 24 bytes; storing a full height word instead of the packed bit raises that to 32, a third more per node. That axis becomes the deciding one when the tree is embedded in a fixed-size record format.

What no invariant can fix is the cost of the comparison itself. Every scheme here performs one key comparison per level, and for variable-length keys — strings, byte arrays — that comparison can dominate the pointer chase. Structures that address this move the comparison out of the inner loop by comparing a fixed-size prefix first, but within the comparison-per-level family the lever is the branching factor: fewer, wider nodes mean fewer comparisons and fewer pointer chases, which is the argument taken up in B-tree node occupancy and splits.

Where the naive tree is still the right answer

An unbalanced binary search tree is not obsolete. It is the correct choice when the key set is small enough that height cannot matter — a few hundred entries, where even a chain costs a few hundred comparisons and the whole structure fits in cache — or when the keys are known to arrive in an order that yields a good shape and no later operations can spoil it. A tree built once from a sorted array by recursive bisection is perfectly balanced and needs no invariant at all, because it is never modified after construction. Static indexes over immutable data are built this way, and the maintenance machinery described in the rest of this cluster exists to pay for mutability.