Binary search tree

The USGS catalogue has 19,073 earthquakes of magnitude 5 and above for 2015–2025. Put them into a binary search tree in the order they happened, with time as the key. Each new shock is later than all the previous ones and goes from the root to the right, to the right and to the right again: the tree grows into a stick 19,073 high. Change the key to longitude, and the same events arriving in the same order grow into a bush 36 high. Try magnitude and depth: there is a catch there that textbook examples do not show.

On the chart under the silhouette the height axis is logarithmic. The green dashed line is the height of a perfect tree, ⌈log₂(n + 1)⌉: 15 for the whole catalogue. The grey dotted line is how many comparisons a search costs on average if the keys came in random order; by 19,073 nodes that is 17.9. Shuffled time lies along it: an average depth of 17.31, a height of 33. Time in order goes up the diagonal: an average depth of 9537, and to find the strongest earthquake in the catalogue, the M8.8 off Kamchatka on 29 July 2025, the tree needs 17,977 comparisons, one with each earlier shock and the last with the quake itself. Inserting all the events cost 181,880,128 comparisons.

The idea

Each node keeps a key, and its left branch holds only smaller keys and its right branch only larger ones. A search compares the key sought with the root and goes into one branch, discarding the other entirely, just as binary search discards half the array. Insertion goes the same way and hangs a new leaf where a branch was missing. Every operation costs as many comparisons as the tree is high, and the height is set by the order in which the keys arrived.

A sorted array with binary search makes the same comparisons, but an insertion into the middle shifts the tail. A search tree is binary search frozen into links: instead of “the middle of the range”, each node has ready left and right halves, and a new key takes its place without any shifting. How to plant, find and cut keys, how to walk the tree and how rotations trim it is told in detail, with a garden where you can try all of it, in the course chapter on search trees. Here: what the height depends on, and how the tree behaves on real data.

The order sets the height

If keys arrive in increasing order, each new one is larger than all the previous ones, and the tree is a stick: the k-th key lands at depth k, and inserting all of them costs n(n − 1)/2 comparisons. For the catalogue that is 19,073 · 19,072 / 2 = 181,880,128, exactly what the scene counted. But if the order is random, the tree comes out low, and that can be proved.

That is about 2 ln n ≈ 1.39 log₂ n comparisons, a logarithm with a small factor. The height, the worst search, is larger than the average, but also a logarithm: with high probability about 4.311 ln n for very large n, a result of Luc Devroye from 1986. On the shuffled catalogue the height is 33 against a perfect 15.

The first paragraph of the proof is the same picture as in quicksort with the first element as the pivot: the first key inserted, like the pivot, is compared with all the others and splits them into two independent parts. A tree grown from a sequence and such a sort make the same comparisons, and both have the same bad input, an already ordered one.

The catch in real data

The textbook proviso goes: “if the keys arrive in sorted order”. On real data the tree gets spoiled without that too. Switch the scene to magnitude. The shocks arrive by time, and magnitude does not depend on time, so the order seems random. But the catalogue has only 83 distinct magnitude values, and 4729 shocks are exactly 5.0. Equal keys have to be told apart somehow, and the natural way is by catalogue number, that is, by time. Within the M5.0 group the keys again arrive in increasing order, and 4729 shocks line up in a chain: a height of 4733.

With depth it is even clearer: a height of 8350. 8349 earthquakes in the catalogue have a depth of exactly 10 kilometres. That is not geology: USGS sets this value when there are not enough data to compute the depth, most often because the nearest seismic station is too far away. Almost half the catalogue turned out to be one key, and equal keys with an increasing tiebreaker are sorted input in disguise. Longitude does not do this: a height of 36 against a perfect 15, almost like shuffled time.

Hence three practical rules. Be suspicious of any data that grow by themselves: order numbers, timestamps, auto-increment keys. Check how many distinct values a key really has. And keep equal keys in one node, as a list or a counter, not as a chain of nodes.

Order as a service: the k-th, rank, nearest

For lookup by key alone there is no point in a tree: a hash table finds a key in one or two probes. A tree is needed when order matters. The nearest key no greater than a given one, floor, goes down from the root and remembers the last node whose key was no greater than the one sought. All keys in a range are a walk that does not enter branches outside the range: O(h + k) for k found. And if each node keeps the size of its subtree, the tree also answers questions about positions.

The k-th in order (select): at the root look at the size L of the left subtree. If k ≤ L, the key sought is on the left; if k = L + 1, it is the root itself; otherwise it is on the right, where the (k − L − 1)-th is needed. Rank, how many keys are smaller than a given one, is the same descent in reverse: where the path turns right, the left subtree and the node itself are added to the answer. Sizes are updated on every insertion and deletion along the path from the root, so everything still costs O(h).

Here are 21 earthquakes of magnitude 7.8 and above for 2015–2025. The key is time, and they were inserted from strongest to weakest, as in the bst listing: the 2025 Kamchatka shock went in first, and since it is almost the latest, the whole tree except one node went into its left branch. A height of 8 against a perfect 5. Switch the insertion to “in time order” and you get a stick 21 high. The “Delete the root” button shows Hibbard deletion: the root has two children, and its place is taken by the successor, the leftmost node of the right subtree, that is, the next key in order.

Code

A search tree with subtree sizes: search, insertion, select, rank, floor and Hibbard deletion. In Go insertion goes through a pointer to a link: the variable link points to the field where the new node must be written, the root or the parent's left or right field, and no separate “empty tree” case is needed. The data are the same 21 earthquakes from the catalogue.

21 quakes, inserted strongest first: height 8
the same quakes inserted in time order: height 21
select(11), the median by time: 2018-01-23 M7.9
rank(2020-01-01): 14 of them came before 2020
floor(2023-01-01), the last one before 2023: 2021-08-12 M8.1
after deleting the root: root 2025-09-18, 20 nodes, height 8

Now the catalogue, but for 2025 alone: over all eleven years the stick of 19,073 nodes costs 182 million comparisons, and Python on the site's server would take too long. Five keys, the same as in the scene; switch it to “2025 only” and the numbers match.

2128 earthquakes of 2025
a perfect tree: height 12; a random order: 13.49 on average
key, in order of time     height  avg depth  comparisons
time                        2128    1064.50    2,263,128
magnitude                    550     160.38      339,171
depth                       1030     263.15      557,845
longitude                     26      14.86       29,488
time, shuffled                24      12.83       25,180

What it costs

Memory is O(n), but with overhead: two links per key, plus a counter in a tree with sizes. Each step down follows a link to another place in memory, and everything the article on the linked list says about the cache holds here too. So on small volumes a sorted array with binary search and insertion by shifting the tail is often faster than a tree. A measurement, inserting n keys: a tree on random keys, the same tree on increasing keys, and a sorted array.

The stick grows linearly per key and quadratically in total, and at ten thousand keys in Go it is more than sixty times slower than the same tree on random keys. The sorted array also grows linearly, for shifting the tail, but a shift is one fast memory copy. In Go the tree still wins from three thousand keys on, while in Python a list with bisect beats a tree of objects at every size measured, up to thirty thousand keys. The popular sortedcontainers library does not build trees at all for this reason: it keeps a sorted list in chunks of about a thousand elements and explains the choice by the extra links a tree needs for every element and by a dense list fitting the cache better.

What is done about the height in practice

A bare search tree is hardly ever used where the order of keys is not under control. There are three ways to keep the height logarithmic:

• Balance with rotations. The AVL tree of Georgy Adelson-Velsky and Evgenii Landis (1962) checks after each insertion that the heights of a node's branches differ by at most one and repairs this with rotations; the red-black tree allows a slightly larger lean and rotates less often. Java's TreeMap is built on a red-black tree.
• Make the order random yourself. A treap gives each key a random priority and keeps the shape it would have under a random insertion order, so the theorem above holds for any input. If all keys are known in advance, they can simply be shuffled before insertion.
• Make the tree wide. A B-tree keeps hundreds of keys in a node and stays perfectly level by construction; database indexes rest on it.

The Python and Go standard libraries have no ordered tree. For ordered data they use a sorted array with bisect or sort.Search, and when there are many insertions, third-party libraries or a skip list.

History

The binary search tree was invented around 1960 by several people independently: in 1960 P. F. Windley wrote about it in The Computer Journal, as did Andrew Booth with Andrew Colin. In 1962 Thomas Hibbard analysed in the Journal of the ACM how such trees behave when keys arrive in random order, and proposed the deletion now named after Hibbard. In the same year Adelson-Velsky and Landis published the first tree that keeps its height logarithmic for any order; their story is told in the course chapter.

Problems

In the first problem two keys of an index have swapped places after a failure, and a traversal, not a check of each node, helps find them. In the second you need the height of a tree of 200 thousand keys without building it: honest insertion in a bad order costs 2·10¹⁰ comparisons, and a linked list suggests the answer.