Binary Search Trees

A binary search tree keeps every key smaller than a node in that node's left subtree and every larger key in its right subtree. Each comparison on the way down therefore discards everything on one side, and a lookup among a million keys takes about 20 comparisons, when the tree is balanced. Everything in this topic turns on that condition.

The ordering rule buys what a hash table cannot give: keys in order, ranges, and the nearest key below or above a value. It also has a failure mode that every engineer eventually feeds it. Insert the keys in sorted order and the tree becomes a linked list, with every cost of one.

The Ordering Rule

For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. The rule holds for whole subtrees, not only between a parent and its two children, and that is what lets one comparison discard an entire subtree. When a lookup for 60 finds 50 at the root and goes right, it has ruled out 30, 20 and 40 without reading them, because the rule promises that nothing on the left can be larger than 50.

Lookup and Insert

A lookup starts at the root, compares, goes left or right, and stops either at the key or at an empty child, which means the key is absent. An insert is a lookup that fails: the new key goes exactly where the search fell off the tree, as a new leaf. Nothing else moves.

Both operations make one comparison per level they pass through, so the price of every operation is the height of the tree. A tree of 20 levels answers in at most 20 comparisons whether it holds a thousand keys or a million. A tree of a million levels answers in up to a million.

Delete

Deleting a leaf removes it. Deleting a node with one child puts that child in its place, and the ordering rule still holds, because the child's whole subtree was already on the correct side of the parent above.

The third case is where hand-written trees go wrong. A node with two children cannot be cut out, because its parent has room for only one of them. Instead it is replaced by its in-order successor, the smallest key in its right subtree: go right once, then left until there is no left child. That key is larger than everything on the left and smaller than everything else on the right, so it can take the deleted node's place without breaking the rule. It is copied up, and then removed from where it was, which is always the easy case, because the smallest key in a subtree has no left child.

What Order Buys

An in-order walk, from the previous topic, yields every key in sorted order. The minimum is the leftmost node and the maximum the rightmost. A range such as every year after 1970 up to and including 1980 is one descent to the first year above 1970 and then a walk that stops after 1980, so it costs the height plus the number of keys in the range. "The largest key not above x", the question behind rounding a timestamp down to the last recorded event, is one descent.

None of these questions can be answered by a hash table, the structure of Chapter 5, because a hash deliberately scatters neighbouring keys across the table. Every one of them costs a hash table a full scan. That is why ordered maps exist beside dictionaries in every standard library that has them, and why a database offers an ordered index at all.

Sorted Input Makes a List

Insert 1, 2, 3 and onward in order. Each new key is larger than everything already in the tree, so it becomes the right child of the previous key, and the tree grows as a diagonal line with no left children at all. A million sorted inserts build a chain a million levels deep, and every lookup scans it like a linked list.

Random order is kind to the plain tree. The textbook figure for a randomly built tree is an average depth of about 1.39 times the base-2 logarithm of n, near 28 for a million keys. Measured on Python 3.15 by inserting a million shuffled keys, the average lookup took 25.7 comparisons and the deepest key sat 51 levels down: two and a half times the ideal, but nowhere near a million.

Real data arrives sorted far more often than random. Timestamps, auto-increment ids and a sorted export all arrive in order, and partly sorted data grows long chains. The chain also breaks code, not only speed: a recursive insert on Python 3.15 fed sorted keys raised RecursionError on the 999th key, because each insert recursed once per level of a chain that was already 998 levels long.

Memory, Misses and Input Order

Even balanced, a pointer-based tree pays for its shape in memory. Every key is a separately allocated node, the heap allocation of Chapter 4, and every level of a descent follows a pointer to wherever the allocator put the next node. That makes each of the 20 levels over a million keys a potential cache miss at about 100 nanoseconds, about 2 microseconds of waiting per lookup, where a hash table pays one or two misses.

Unbalanced, the tree is a correctness risk disguised as a performance one. The input order that breaks it is chosen by whoever feeds it: a sort order in an export, a sequence of ids, or someone who has read the same textbook and sends keys in order on purpose. Production code therefore never uses the plain binary search tree. It uses the balanced trees of the next topic in memory, or the B-trees at the end of this chapter on disk.