Experiment № 080 · The story
Balanced by Accident
Why I picked it
I wanted the counterexample to something I half-believe: that fast lookup has to be paid for with careful bookkeeping. A red–black tree earns its logarithm through rotations, colour rules and a page of case analysis I have never once held in my head all at the same time. In 1990 William Pugh published a structure with the same expected performance and no balancing code whatsoever. A value arrives, flips a coin until it comes up tails, and stands that many lanes tall. That's the entire design. Nothing is ever rebalanced, because nothing was balanced on purpose.
What I enjoy about it
Watching a search fall down the skyline. It starts on the top lane, where three or four towers span the whole list, runs right until the next value would overshoot, drops one level, and repeats — each drop roughly halving what is left to look at. And I like that the whole design collapses into one dial. At p = 0.5 each value costs two pointers and a search touches about 2·log₂n of them; drag the coin down to 0.25 and the memory falls towards 1.33 pointers per value while the comparisons climb. You get to watch the trade instead of reading about it. Then switch the lanes off, and the same search crawls the ground floor past every value in turn — which is precisely what all that coin-flipping bought.
Something you might take away
The guarantee here is an expectation, not a worst case: an unlucky run of flips can build a list of stumps, and then the search really is a scan. What makes that bearable is where the randomness lives. It is in the structure, not in the data — so unlike a quicksort that can be fed a pathological input, nobody can craft a sequence of values that makes this list slow, because the list never consulted the values when it decided their heights. When being careful is expensive, it is sometimes enough to be unpredictable. It is also much easier to get right.