A search tree's shape is decided by the insertion order, which the structure does not control. A treap gives every key a random priority and keeps heap order on the priorities as well as search order on the keys; the resulting tree is unique, so the insertion order cannot reach it. Twelve keys inserted in sorted order give a plain tree of height 11 and a treap of height 5, and inserting the same keys and priorities in a shuffled order gives the same treap, node for node.
Core ideas
The hard idea is the uniqueness, because everything else follows from it. The other two are where the randomness comes from and what the structure does not have.
A treap holds a key and a priority at each node, is a binary search tree on the keys, and is a min-heap on the priorities. If all the keys and all the priorities are distinct, exactly one such tree exists: the minimum priority must be at the root, the keys below it split by the search property, and the same argument applies recursively. The lab's opening instance has the key with priority 1 at the root, and there is nothing to choose.
Two different insertion orders of the same key–priority pairs must end at the same tree, because there is only one tree they could end at. The panel builds it twice — sorted on the left, a shuffle on the right — and reports the same tree, node for node, while the rotation counts differ, 8 against 11. Different work, identical result.
A treap on keys with priorities in random order is exactly the tree a plain search tree would have if the keys had arrived in the order of those priorities. So its expected depth is the expected depth of a randomly built search tree, which The Shape Problem and Random BSTs measured: 2 ln n asymptotically. Nothing checks a height, nothing checks a balance factor, and the rotations here restore heap order only.
The material
The two invariants, the uniqueness proof, what insertion costs, and the honest status of the depth figure.
Binary Search Trees showed a tree's cost depending on something the structure does not choose: twelve keys arriving in sorted order give a path of height 11, and the same twelve arriving shuffled give a height of 4. Rotations and the AVL Invariant fixed that by adding a rule the structure enforces on every insertion. This lesson fixes it differently — by making the shape depend on coins instead of on the arrival order.
A treap is a binary tree in which each node holds a key and a priority. It satisfies the search property on the keys — every key in a left subtree is smaller, every key in a right subtree is larger — and the heap property on the priorities: every node's priority is smaller than its children's.
For any finite set of pairs with distinct keys and distinct priorities, exactly one treap contains them.
Induct on the number of pairs. With none, the empty tree is the only one. Otherwise the heap property forces the pair with the smallest priority to be at the root: any other node with that pair would have an ancestor of larger priority.
The search property then forces the partition of the remaining pairs: every key smaller than the root's goes into the left subtree and every larger key into the right. Neither subtree has a choice about which pairs it contains.
Each subtree is itself a treap on a strictly smaller set with distinct keys and distinct priorities, so by induction each is unique. The whole tree is therefore unique.
□
The lab does not argue this, it checks it. Both panels are built from the same priority assignment and compared node for node, and the verdict reads the same tree, node for node or words that would refute the claim. Priorities are ranked rather than taken raw so that no two can collide; a tie would leave the shape undetermined and the claim would fail for a reason with nothing to do with treaps.
The keys are 10, 20, …, 120 and the seed assigns priorities 10:6 20:3 30:1 40:10 50:12 60:7 70:2 80:11 90:9 100:5 110:4 120:8. Priority 1 belongs to key 30, so 30 is the root. Inserting in sorted order costs 8 rotations; inserting in a shuffled order costs 11. Both produce a tree of height 5 with mean depth 5/2, and the two trees are identical. A plain search tree on the same sorted order has height 11 and mean depth 11/2.
Height 5 against 11, and mean depth 5/2 against 11/2: the treap is less than half as deep on average, on the input that is worst for a plain tree. And it got there without any rule about heights — the only thing being maintained is heap order on twelve numbers the structure generated itself.
To insert a key, give it a random priority, place it as a leaf by the ordinary search-tree rule, and then rotate it upwards while its priority is smaller than its parent's. A rotation preserves the search property — Rotations and the AVL Invariant proves that, and the in-order sequence is what it preserves — so the search property is never in danger, and the loop stops exactly when heap order is restored.
That is the whole implementation, and it is worth noticing what is absent. No height is stored, no balance factor is computed, no case analysis over four shapes. Deletion is the same idea in reverse: rotate the node down until it is a leaf, then remove it. The panel's rotation counts, 8 and 11 for the two orders, are the only work the structure did beyond the searches.
The depth of a treap is a random variable, and its expectation is the expected depth of a search tree built from a uniformly random insertion order — which is 2 ln n + O(1) for the mean depth, and O(log n) for the height. Both of those are stated on this path: The Shape Problem and Random BSTs states them, Randomised Quicksort derives the recurrence they come from, because a random root and a random pivot are the same object, and no lesson in this library carries the full argument.
So the panel prints 2 ln n in its own row, labelled asymptotic, and it is about 15 per cent wrong about the tree in front of you. At n = 12 it reads 4.970 while the counted mean depth is 2.500 and the counted height is 5. Three numbers, three meanings: one asymptote, one exact mean of integers, one count. Reading them as estimates of each other is the failure mode of this page, and it is why each is labelled where it is printed.
The guarantee is also in expectation and not always. Over seeds 1 to 12 at twelve keys the treap's height came out 5, 6, 4, 5, 5, 6, 6, 5, 5, 4, 6, 5 — never 11, and never 3 either. Move the priority seed and watch it move. An AVL tree's height at twelve keys is bounded by a rule the structure enforces; a treap's is a random variable whose bad cases are unlikely rather than impossible.
That is the trade, and it is the same trade a random pivot makes. The input is arbitrary, possibly chosen by someone who wants the structure to perform badly, and the coins are the structure's own, so no input can be bad for it — only an unlucky draw can, and the draw is not the adversary's to make. Universal Hashing bought the same thing for a hash table with the same manoeuvre.
Interactive
The shape is the one a random insertion order would have built, whatever order you use
Method
Find the root before anything else; the rest of the tree is forced.
Then partition the remaining keys by comparison with it and recurse. This is the uniqueness proof used as an algorithm, and it builds the tree without reference to any insertion order at all.
Swap the two order menus. The rotation counts change and the trees do not. If they ever differed, the priorities would be the thing to check first — a tie breaks uniqueness and nothing else does.
This is the knob that matters. Heights at twelve keys range over 4, 5 and 6 across the first dozen seeds. That spread is the guarantee's actual content: bad shapes are unlikely, not impossible.
The counted height, the exact mean depth as a fraction, and the 2 ln n asymptote. At twelve keys they are 5, 5/2 and 4.970. Only the first two are about this tree, and the panel labels all three.
Keys 10 to 120, priorities from the seed, and the claim that the insertion order cannot be read off the result.
Build the top two levels from the priority row by hand before looking at the drawing: root 30, then 20 on the left and 70 on the right. Nothing about the insertion order entered that reasoning, which is exactly the claim — the priorities determine the tree and the order determines only the rotations.
The rotation counts are the one place the two runs differ, 8 against 11. That is real work and it is the price of the guarantee: a plain tree on the sorted order does no rotations at all and ends up with height 11. Paying eight rotations to halve the depth is the trade, and it is cheaper than the AVL case analysis it replaces.
For a faded rehearsal, set the priority seed to 3 and predict the height before the panel redraws. The supplied first move is this: the seed changes the priorities and therefore the tree, and the first dozen seeds give heights between 4 and 6. Say what the smallest and largest heights a twelve-key treap can possibly have are, and then say why neither extreme showed up in twelve seeds.
You should be able to state both invariants, prove uniqueness by induction on the smallest priority, describe insertion as a leaf placement plus upward rotations, and say which of the panel's depth figures is counted, which is exact and which is an asymptote.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.