Binary search trees

A hash table answers "is this key present" in constant time and cannot answer "what is the next key after it" at all, because scattering the keys was the whole point.

Getting order back means giving up the scattering, and the structure that does it is a tree. The pieces are already familiar: binary search halves an interval, and a linked node points at other nodes instead of sitting next to them. A binary search tree is the two ideas combined, and the combination buys something neither had alone, which is insertion and deletion in logarithmic time on an ordered collection.

The ordering property

A binary search tree is a set of nodes, each holding a key and pointers to a left child, a right child, or nothing. One node is the root. The defining condition is local and applies at every node $x$ :

Every key in the left subtree of $x$ is less than $x$ 's key, and every key in the right subtree is greater.

That says subtree, not child. It is not enough for the left child to be smaller: every descendant to the left must be, all the way down. The condition holding at every node is what makes the tree searchable, because it is exactly what lets a comparison at $x$ eliminate an entire subtree.

The tree carries no array, no contiguity and no index arithmetic. Its shape is not determined by its contents: the same set of keys can be stored in many different trees, all of them valid, and which one you get depends entirely on the order the keys arrived in. That fact is where the whole lesson ends up.

Searching

To find key $k$ , start at the root. If $k$ equals the node's key, stop. If $k$ is smaller, go left; if larger, go right. If the pointer to follow is null, $k$ is not present.

Each comparison discards one subtree, exactly as each comparison in binary search discarded half an interval. The difference is that binary search discarded half by construction, whereas here the size of the discarded subtree is whatever the tree's shape makes it. The number of comparisons is the depth of the node found, plus one, and the worst case over all keys is the height of the tree: the number of edges on the longest root-to-leaf path.

Insertion follows the same walk. Search for the key; when the walk falls off the bottom of the tree, attach a new node there. The new key is a leaf, and no existing node moves. This is the property that arrays could not offer: inserting into a sorted array costs $Θ (n)$ to shift, while inserting here costs one walk and one pointer write.

Example. Insert 41, 23, 67, 12, 35, 55, 88, 29 into an empty tree, in that order. What is the height, and what does an average successful search cost?

41 becomes the root. 23 goes left of it, 67 right. 12 goes left of 23, and 35 right of 23. 55 goes left of 67, 88 right of 67. Finally 29 compares less than 41, greater than 23, less than 35, and becomes the left child of 35. The depths are 41 at 0; 23 and 67 at 1; 12, 35, 55 and 88 at 2; 29 at 3. The height is 3. The depths sum to 13, so the average depth is $13 / 8 = 1.625$ and an average successful search costs $2.625$ comparisons.

Now you. Insert the same eight keys in ascending order: 12, 23, 29, 35, 41, 55, 67, 88. What is the height now?

Answer

Every key is larger than everything already in the tree, so every insertion walks to the rightmost node and attaches on its right. The result is a single chain of eight nodes descending to the right, with height 7. The depths sum to $0 + 1 + \dots + 7 = 28$ , so the average search costs 4.5 comparisons rather than 2.625. The same eight keys, the same structure, and a search that costs 71 per cent more.

The keys come back out sorted

Take the tree and walk it as follows: recursively visit the left subtree, then emit this node's key, then recursively visit the right subtree. This is the in-order traversal, and it emits the keys in ascending order.

The reason is the ordering property applied once. At any node, everything in the left subtree is smaller than the node and everything in the right subtree is larger, so left, node, right is the correct relative order for those three groups. The recursion makes it true within each group. The walk visits every node once and does constant work at each, so it costs $Θ (n)$ .

Running an in-order walk on the tree from the example gives 12, 23, 29, 35, 41, 55, 67, 88. It also gives a sorting algorithm: insert $n$ keys into a tree and walk it. That is exactly the shape of quicksort, and not by analogy. Quicksort's first pivot is the root, the two partitions are the two subtrees, and the total comparison count of quicksort equals the sum of the depths of the resulting tree. The formula $2 (n + 1) H_{n} - 4 n$ derived for quicksort's average is therefore also the expected sum of depths of a tree built from a random permutation, and for $n = 8$ it gives 16.9 against the 13 the particular example produced.

The in-order walk answers the questions the hash table could not. The smallest key is found by following left pointers from the root until they run out; the largest by following right pointers. The successor of a node with a right subtree is the smallest key in that subtree, and if there is no right subtree it is the lowest ancestor from which the node is in the left subtree. Every key between two bounds can be listed by an in-order walk that prunes subtrees lying entirely outside the range. All of these cost the height, or the height plus the number of keys reported.

Deletion, in three cases

Deletion is the only operation that is not a straight walk, because removing a node from the middle of a tree leaves its children with no parent. There are three cases, distinguished by how many children the doomed node has.

A leaf is removed by setting its parent's pointer to null. Nothing else changes.

A node with one child is removed by connecting its parent directly to that child. The child's whole subtree keeps the same relationship to everything above it, because it was already entirely on the correct side of the deleted node.

A node with two children cannot be spliced out, because its parent has only one pointer to spare. Instead, do not remove the node at all: overwrite its key with the key that may legally sit in that position, then remove the node that key came from. There are exactly two such keys, the node's predecessor (the largest in the left subtree) and its successor (the smallest in the right subtree), because either sits between the two subtrees in sorted order. The successor is conventional. Crucially, the successor is the leftmost node of the right subtree, so it has no left child, and removing it is case one or case two.

Example. Delete 23 from the tree built earlier, whose relevant part is 23 with left child 12 and right child 35, and 35 with left child 29.

Node 23 has two children, so find its successor: the smallest key in its right subtree, which is the leftmost node under 35, namely 29. Copy 29 into the node that held 23, then delete the original 29, which is a leaf. The result has 29 where 23 was, with left child 12 and right child 35, and 35 now childless. An in-order walk gives 12, 29, 35, 41, 55, 67, 88, still sorted.

Now you. From the original tree, delete the root, 41.

Answer

41 has two children, 23 and 67. Its successor is the smallest key in the right subtree, which is the leftmost node under 67: that is 55, which has no children. Copy 55 into the root and delete the leaf 55. The root is now 55, with left child 23 (unchanged, with 12 and 35 below it) and right child 67, which now has only the child 88. Note that the height is unchanged at 3, but a different choice of key to promote would have given a different shape, which is why deletion strategies affect balance over time.

Every operation, search, insert, delete, minimum, successor and range query, costs the height of the tree. So the entire performance of the structure reduces to one question: how tall is it?

Height is everything, and it depends on arrival order

A binary tree with $n$ nodes has height at least $⌈ \log_{2} (n + 1) ⌉ - 1$ , since a tree of height $h$ holds at most $2^{h + 1} - 1$ nodes. A perfectly balanced tree of a million keys has height 19, and every operation costs about 20 comparisons: the same as binary search, but now with insertion and deletion at the same price.

At the other extreme, keys inserted in ascending order produce the chain seen above, height $n - 1$ . The tree is a linked list with a wasted pointer per node, search is $Θ (n)$ , and an average successful search on a million sorted keys costs 500,000 comparisons instead of 20. That is a factor of 25,000, and it comes from nothing but the order the keys arrived in.

In between is the random case, and it is much closer to the good end. If the $n$ keys arrive in a uniformly random order, the expected depth of a node is $2 \ln n$ roughly, which is $1.386 \log_{2} n$ : the quicksort constant again, for the reason given above. The expected height, meaning the deepest path rather than the average one, is about $4.311 \ln n$ , a result due to Bruce Reed in 2003.

Example. For a million keys, compare the expected search cost of a random binary search tree with a perfectly balanced one, and with the sorted-input case.

$\log_{2} 10^{6} = 19.93$ , so a perfectly balanced tree costs about 20 comparisons. A random tree costs $2 \ln 10^{6} = 27.6$ on average, about 39 per cent more, and its expected height is $4.311 \times 13.82 = 54$ , so even the worst key in a random tree is found in about 54 comparisons. Sorted input costs 500,000 on average. The gap that matters is not between random and balanced, which is a constant factor, but between either of those and the degenerate case, which is a change of complexity class.

Now you. Repeat for a billion keys.

Answer

$\log_{2} 10^{9} = 29.90$ , so balanced costs about 30. Random costs $2 \ln 10^{9} = 41.4$ on average, with an expected height of $4.311 \times 20.72 = 89$ . Sorted input costs 500 million. Ten times more keys added ten comparisons to the balanced and random cases and added 499.5 million to the degenerate one.

Why the bad case is the normal case

It would be comfortable to treat height $n$ as a curiosity that random data avoids. It is not, and this is the part worth taking seriously.

Real keys arrive in order far more often than chance would suggest. Records are read out of a database with an ORDER BY, timestamps arrive as time passes, identifiers are assigned by an incrementing counter, files are processed in the order a directory listing returned them, and a tree rebuilt from a sorted export degenerates completely. Sorted or nearly sorted input is not an adversarial case; it is the default shape of data that came from anywhere organised.

There is also no averaging over deletions to fall back on. The random-tree analysis assumes insertions of a random permutation into an initially empty tree. Once deletions are mixed in, and particularly once the always-take-the-successor rule is used, the shape drifts: repeated insert-delete cycles leave a tree measurably taller than the random model predicts, an effect first noticed by Gary Knott in 1975 and still not fully characterised.

And an attacker who can choose insertion order can force the linear case deliberately, the same vulnerability the previous lesson described for hash tables, with the same consequence for any service that builds a tree from user-supplied keys.

So the unbalanced binary search tree is not a structure to ship. What it is, is the right data layout with no mechanism to defend it. The next lesson supplies the mechanism: a constant-time local restructuring called a rotation, applied on the way back up from each insertion and deletion under a rule that keeps the height within a small constant factor of $\log_{2} n$ , in the worst case rather than on average, on every input including the sorted one.