The priority nobody supplied

The tree that is a list measured the binary search tree’s failure and did not fix it. The failure is worth restating in one line because everything here is a response to it: insert keys in sorted order and every node gets one child, so the structure whose reputation is $O(\log n)$ performs a linear scan, on the most ordinary arrival order there is.

The usual repair is to balance. Detect that one subtree is taller than the other, rotate to correct it, and prove that the maintained invariant implies a height bound. AVL trees measure heights; red-black trees maintain a colour invariant; both are correct, both are proved, and both require getting a case analysis right that most people who can describe the idea cannot write from memory.

A treap does not do any of that. It gives every key a second key, drawn at random, and keeps the tree ordered by the first and heap-ordered by the second. There is no imbalance detection anywhere in it.

Two orders at once #

A treap is a binary search tree in the keys and a max-heap in the priorities, simultaneously. Those two requirements sound like they might conflict and they do not: for any set of (key, priority) pairs with distinct priorities there is exactly one tree satisfying both, and it is easy to describe. The root is the pair with the highest priority. Everything with a smaller key goes left, everything with a larger key goes right, and each side is built the same way recursively.

The uniqueness is the whole trick and it is worth pausing on, because it is what makes the insertion order stop mattering. The final shape is a function of the set of pairs. It does not depend on the order they arrived in, because the description above never mentions an order.

Insertion is short. Walk down as in an ordinary binary search tree and attach the new node as a leaf, which satisfies the key order and probably violates the heap order. Then rotate the new node upward while its priority exceeds its parent’s. A rotation preserves the key order — that is what a rotation is for — so the loop is repairing one property without breaking the other, and it stops as soon as the heap order holds.

There is no case analysis. There is one loop with one condition in it.

What sorted insertion does to each #

The measurement is the same input on both structures, at four sizes.

The binary search tree’s height is exactly $n - 1$ at every size, which is not an approximation — sorted insertion produces a right spine and nothing else, so the height is the number of keys after the first. The comparison count is exactly $\binom{n}{2}$ for the same reason.

The treap’s height at $n = 4{,}096$ is 26, against $\lfloor \log_2 n \rfloor = 12$. That factor of just over two is the expected behaviour: the expected height of a treap on $n$ random priorities is about $4.31\ln n$, which at 4,096 is 35.8, and 26 is a comfortable build. The comparison count is 32,750, or eight per key.

The rotations are the whole of the work, and there are n of them #

The number of rotations is the quantity that says what a treap costs relative to a plain tree, and the table above has an unexpected regularity in it: 59 rotations for 64 keys, 251 for 256, 1,020 for 1,024, 4,088 for 4,096. That is almost exactly one rotation per key.

On sorted insertion that is easy to see. Every arriving key is the largest so far, so it attaches as the rightmost leaf and then climbs until it meets a higher priority. The expected number of steps in that climb is bounded by a constant — the arriving priority has to beat each ancestor in turn, and beating $j$ in a row has probability $1/(j+1)!$-ish — so the total is $\Theta(n)$ and the constant is under one.

This is the honest comparison against a red-black tree, which also does $O(1)$ amortised rotations per insertion. The treap does not win on rotation count. It wins on there being one loop rather than a case analysis, and it pays for that with the second key.

The shape is the shape a random order would have given #

The sentence that makes a treap more than a trick is this one: the tree a treap builds from any insertion order is distributed exactly as an ordinary binary search tree built from a uniformly random insertion order.

The argument is one line, given the uniqueness above. The final shape depends only on the set of (key, priority) pairs. The pair with the highest priority is the root. If the priorities are independent and uniform, the highest one is equally likely to belong to any of the $n$ keys — so the root is a uniformly random key, and the same holds recursively in each subtree. That is precisely the process that generates a random binary search tree.

So everything known about random binary search trees transfers, including the constant: expected depth $2\ln n \approx 1.39\log_2 n$, expected height $4.31\ln n \approx 3.0 \log_2 n$. And the measurement can check the transfer directly, by building an ordinary BST from random keys and a treap from sorted keys and comparing:

The treap on the worst possible input is slightly shallower than the plain tree on a good one. Those two numbers are draws from the same distribution and the difference between them is noise, which is exactly the claim.

Why not simply shuffle the input #

If the shape a treap produces is the shape a random insertion order would have produced, an obvious question is why not shuffle the keys and use an ordinary tree. It is a fair question and the answer is the reason treaps exist rather than being a curiosity.

Shuffling requires having all the keys before inserting any of them. A tree that is built once from a known set can indeed be shuffled, and for that case the plain tree with a shuffle is simpler and cheaper. But the interesting use of a search tree is one that is inserted into and deleted from over its lifetime, by a program that does not know what is coming. There is no batch to shuffle. The keys arrive when they arrive, frequently in an order correlated with something — timestamps, identifiers, sorted output from an earlier stage — and that correlation is exactly the failure mode.

A treap needs no batch. It randomises at the point of insertion, one key at a time, and the guarantee holds after every operation rather than only at the end of a build. That is the same distinction as between an average case and an expected case, applied to when the randomness is available.

Deletion makes the point sharper still. Deleting from an ordinary binary search tree by the standard two-child rule — promote the in-order successor — is known to skew the tree over long sequences of interleaved insertions and deletions, and no amount of shuffling the original input helps, because the damage accumulates afterwards. A treap deletes by rotating the doomed node down until it is a leaf and cutting it off, which leaves the remaining set of (key, priority) pairs untouched — and the shape of a treap is a function of that set alone. So the tree after a deletion is the tree that set would have produced from scratch. The invariant survives the operation rather than degrading under it.

Across builds, because one build is an anecdote #

Everything above is one seed. A treap’s height is a random variable in the same way a skip list’s is, so the useful statement is about the distribution.

Two hundred treaps over the same 2,048 sorted keys, one seed each:

• Height ranged from 20 to 29, mean 23.89, against $\log_2 2048 = 11$ and the theoretical $4.31\ln n \approx 32.8$.
• Mean node depth — the quantity a lookup actually pays — had a relative standard deviation of 5.29%, around a mean of 12.48.

The pattern is the one the previous essay established. The extreme — the height — varies by 45% across builds. The average — what a lookup costs — varies by 5%. The structure is volatile in the quantity that is cheap and steady in the quantity that is paid for, and that is the property that makes an expected-case bound worth having.

The same silhouette, three more draws #

The shape is the priorities and the priorities are drawn, so the honest way to show that is to draw them again.

And the last of the three changes the size rather than the draw, which is the direction the logarithm is supposed to show up in.

The failure this essay nearly shipped #

Every other input kind the site keeps behaves the way the argument predicts, and one of them did not, for a reason that turned out to be the most useful thing measured here.

At $n = 4{,}096$, treap heights on the site’s five input kinds: sorted 26, reversed 26, nearly sorted 26, few distinct values 78, random 3,849.

Three thousand eight hundred and forty-nine, on a structure whose whole claim is that no input can do that — and on the easy input, the one where an ordinary binary search tree measures 28 and needs no help at all. The treap was 137 times worse than the thing it replaces, on the input it was not needed for.

The cause is not in the treap. The site’s random input comes from INPUTS.random(n, 909), which reads a seeded xorshift32 stream; the treap’s priorities came from Coins(909), which reads the same stream from the same starting state. So the $i$-th key and the $i$-th priority were the same thirty-two bits scaled two different ways. Printed side by side:

The priority was the key. And a treap whose priorities are monotone in its keys is not a treap in any useful sense: the heap order and the search order now agree, so the highest priority is the largest key, which becomes the root with nothing to its right, and the structure is a spine.

Two things about this are worth carrying away.

The independence of the keys from the coins is an assumption, and it is one a program has to arrange. Every analysis in this essay says “priorities drawn independently at random”. Nothing in the code enforces it, nothing in the type system suggests it, and the natural thing to do in a test — seed everything from one number so the run reproduces — breaks it exactly. The figures now draw their keys from one seed and their priorities from another, and both are printed in the caption strip for that reason.

The failure is silent. The tree was still a correct search tree. Every lookup returned the right answer, every key came out of an in-order walk in order, and no assertion about correctness would have fired. The only visible symptom was a number in a figure, and the only reason it was seen is that the figure’s own assertion demanded the height stay under $5\log_2 n$ and refused to draw when it did not. That is the argument for figures that check themselves in one sentence.

The remaining input is worth a line too. Few distinct values gives a treap of height 78 against 26 on the others, because 4,096 keys drawn from eight values means long runs of equal keys, and equal keys all go to the same side. That is not a randomisation failure — the plain tree measures 525 on the same input — but it is a reminder that a treap’s guarantee is about distinct keys, and duplicates degrade it in the same way they degrade the floor when the values repeat.

What the repair costs #

Three costs, all measurable, and worth listing because “randomisation makes the problem go away” is not free.

Space. A priority per node. Thirty-two bits if it is a full word, which on a tree of small keys can be a meaningful fraction of the node — an integer key with two child pointers is 20 bytes, and a 4-byte priority makes it 24. A red-black tree needs one bit, which usually fits in the low bit of a pointer and costs nothing. That is the clearest place a treap loses.

Randomness. Thirty-two bits per key drawn from the generator, measured, fitted against $n$ with a spread of 1.000 — because it is exactly 32 per key with no variance at all. A skip list needs two. Both are $\Theta(n)$ and the constant differs by a factor of sixteen, which is the sort of thing the notation drops and the randomness counter does not.

The guarantee. A red-black tree’s height is at most $2\log_2(n+1)$, proved, for every input. A treap’s height is a random variable whose mean is about $3\log_2 n$ and which has no bound. On the measurement above it never exceeded 29 in two hundred builds at $n = 2{,}048$, where a red-black tree is guaranteed under 22. The treap is usually worse than the red-black guarantee and never catastrophically worse, and if the application has a hard latency ceiling that difference is the one that decides.

What it buys is the thing the table at the top of this essay measures: a structure that survives sorted insertion, built from one loop, with no invariant to state and no configuration to get wrong.

Thirty-two bits is a choice, and it is not a constant #

Two of the three costs above are quoted as thirty-two bits a key, and the number is worth interrogating, because the treap does not use a priority’s value at all — only its rank against the other priorities. What the width has to buy is distinctness, and distinctness has a size.

The uniqueness argument this whole essay rests on requires the priorities to be distinct: two equal priorities and the shape stops being a function of the set. With $n$ keys and $b$-bit priorities the expected number of collisions is about $n^2/2^{b+1}$, so keeping it under one needs

$$b > 2\log_2 n.$$

At the sizes measured here that is comfortable: 4,096 keys need 24 bits, and thirty-two gives an expected 0.002 collisions. At 65,536 keys the expectation is 0.5, and at a million it is 116 — so a thirty-two-bit priority is under-provisioned past about sixty-five thousand keys, which is not a large tree.

The failure is gentle rather than dramatic, which is why nobody notices it. A hundred tied pairs in a million-key treap perturb a hundred local shapes and leave the height essentially where it was; the structure stays a correct search tree and its depths stay where the distribution says. What breaks is the statement — the shape is no longer a function of the set alone, so the argument that a deletion returns the tree that set would have built stops being exactly true. A quiet weakening of a proof rather than of a program.

The more interesting consequence is what it does to the randomness accounting. Thirty-two bits a key against a skip list’s two is quoted as a factor of sixteen and filed as a constant the notation drops. It is not a constant. A skip list’s two bits are two bits at every $n$ — a geometric level draw has mean two flips whatever the structure holds — while a treap’s width has to track $2\log_2 n$ to keep its own premise true.

So the honest comparison is $\Theta(n\log n)$ bits against $\Theta(n)$, and the ratio grows: twelve at four thousand keys, twenty at a million, twenty-four at a billion. The factor of sixteen is what one fixed word width looks like at one size, and reading it as the exchange rate between the two structures is exactly the error counting the coin flips exists to catch — a counter reporting a per-key figure that is really a per-key-times-something figure with the something held still.

Which leaves the practical guidance in a better place than thirty-two bits. Size the priority at $2\log_2 n$ plus a margin, from the largest $n$ the tree is expected to reach: twenty bits for a thousand keys, forty for a million. Below sixty-five thousand keys a thirty-two-bit word is generous and could be trimmed to a sixteen-bit field at a few thousand keys, which halves the space cost this essay names as the treap’s clearest loss against a red-black tree. Above it, thirty-two is the wrong number in the direction nothing reports, and the height is a distribution’s warning applies to the priorities as much as to the shape they produce: a quantity that only matters through its extremes is a quantity whose mean says nothing about whether it is large enough.

The one it does not fix #

A treap removes the input’s ability to choose the tree’s shape. It does not remove an adversary’s, and the distinction is the same one that runs through this whole phase.

The priorities come from a seeded generator. If the seed is known, the priorities are known, and the tree that any sequence of keys will produce is computable in advance — so an adversary can order the insertions to produce whatever shape they like, including the spine. That is not a hypothetical about treaps in particular; it is the general fact that a published seed is a published function, and it applies to every structure in this field.

What survives is the claim about inputs, which is the claim that was made: for keys arriving in any order chosen without reference to the priorities — that is, for the data an ordinary program encounters — the treap’s shape is drawn from the random-insertion distribution, and the arrival order has no effect on it whatever. Sorted, reversed, nearly sorted, adversarial against a different seed: all the same. That is a strictly stronger statement than “a BST is fine on random data”, it is the difference between an average-case and an expected-case guarantee, and it is bought with thirty-two bits per node and one loop.