Balance by Coin Flip
In short: the last two lessons kept a tree balanced by bookkeeping — a balance factor, four rotation cases, a parent-child colour rule. A treap gets O(log n) height a different way: give every node a random priority when it's inserted, and keep the highest priority at the top of every subtree, like a heap — using the exact same rotations from lesson 1, just triggered by a coin flip instead of a balance check. A skip list reaches the same O(log n) search cost by building shorter "express lane" linked lists above the full list, one promotion coin flip per insert, so a search drops down a level every time it would overshoot. Both trade bookkeeping for randomness, and both guarantee O(log n) on average, not in the worst case — an unlucky run of coin flips can still produce a chain.
A matchmaking queue sorted by rating
A matchmaking service indexes waiting players by skill rating so it can quickly find "closest rating available." Players queue and leave in an order nobody controls — sometimes a burst of similarly-rated players joins at once, which is exactly the pattern that degrades a plain BST. A treap keeps the index short without checking a balance factor on every insert:
Height 5 for 8 ratings, inserted in the exact ascending order that gave lesson 1's plain BST a height of 8. Nothing checked a balance factor — the shape came entirely from which node happened to draw the highest priority. A genuinely unlucky sequence of coin flips could still produce a chain, but across many inserts that's as unlikely as flipping 8 heads in a row.
Bubbling a new root to the top
Here's a small example, drawn by hand, of what one insert's rotations
actually look like. Insert 5, 2, 8, 1 into an empty treap with seed 42,
then insert 9:
A treap after inserting 5, 2, 8, 1 with seed 42. Priorities, drawn in that order, are 0.6394, 0.025, 0.275, 0.2232 — 5 is on top only because it drew the highest priority so far.
Every node carries the random priority it drew on insert. A treap keeps the HIGHEST priority on top of each subtree, like a max-heap. Binary tree, 4 nodes, height 3.
An in-memory session index, searched often
A server keeps active sessions in a sorted structure so it can answer "does this token exist?" fast. A skip list builds several linked lists over the same sorted data: the bottom list has every session, and each list above it has roughly half as many, picked by a coin flip at insert time — an express lane.
The mistake people actually make: writing the search to only ever walk
next[0], the bottom lane. That's a correct linked list, but it throws away
every express lane — search degrades straight back to O(n). The whole point
is walking the top lane first and only dropping down when the next stop
would overshoot.
What it costs
| structure | search / insert | why | worst case |
|---|---|---|---|
| treap | O(log n) expected | priorities are drawn uniformly at random, so no key order is "bad" | O(n), an unlucky run of priorities |
| skip list | O(log n) expected | each level has about half the nodes of the one below, by a fair coin flip | O(n), an unlucky run of promotions |
| AVL / red-black (lessons 1–2) | O(log n) guaranteed | bookkeeping fixes every violation immediately | never degrades |
The trade: treaps and skip lists are simpler to implement correctly (no four-case rotation table, no recolouring rules) and support ranges and concurrent access well, in exchange for a worst case that bookkeeping-based trees don't have.
Quick practice
def would_rotate(parent_priority, child_priority):
return child_priority > parent_priority
print(would_rotate(0.8, 0.3), would_rotate(0.3, 0.8))This prints 16 (a full linear scan) instead of 5. Rewrite `hops_to_find` to walk the levels from `self.level - 1` down to `0`, the same loop shape as `search`, counting a hop for every `cur = cur.next[i]` at ANY level.
🎯 Your turn
Build treap_insert_sequence(values, seed): insert values one at a time
into a treap, drawing each new node's priority from random.Random(seed)
(created once, one draw per insert, in order), and rebalance with rotations
whenever a child's priority beats its parent's. Return {"inorder": [...], "height": ..., "priorities": [...]}, with priorities rounded to 4 decimal
places in the order they were drawn.
treap_insert_sequence([1, 2, 3, 4, 5, 6, 7, 8], 42)→{"inorder": [1, 2, 3, 4, 5, 6, 7, 8], "height": 5, "priorities": [0.6394, 0.025, 0.275, 0.2232, 0.7365, 0.6767, 0.8922, 0.0869]}
Hint: reuse rotate_left/rotate_right from lesson 1 unchanged. Insert
by key like a plain BST, then on the way back up compare the child's
priority to its parent's and rotate if the child wins.
Press ▶ Run, try the Live App chip, then ✓ Check.