The encyclopedia · Engineering & Operations · Technical decision · 1989–1990
Skip lists used coin flips instead of rotations to stay balanced
William Pugh's skip list assigns each node a level with a coin flip, getting expected log(n) operations with far simpler code than a balanced tree.
University of Maryland
the move
Ordered structures built as balanced trees must re-balance after each update, which means rotations, recolouring and careful invariants - all of it easy to get wrong and awkward to parallelise.
Skip lists swap that machinery for a probabilistic rule. Each node is given a level drawn from a steeply falling distribution, so most are low, a minority are high, and a search can jump over long stretches of lower levels before dropping down.
Because levels are random, the expected number of nodes per level is geometric and search, insert and delete all land in expectation at O(log n). The code is short, and no bookkeeping has to be performed after the fact.
why it works
- Random levels give the height bound without re-balancing code.
- Local, lock-friendly operations make it easy to parallelise.
- Simplicity means fewer invariants to maintain and get wrong.
what transfers
When deterministic re-balancing is the expensive, error-prone part, replace it with honest randomness: local, simple operations give the same expected performance as a hand-maintained invariant.
what came after
Skip lists became a standard alternative to trees in libraries and databases, most famously Redis's sorted sets, where the simplicity aids concurrency and predictable performance.
references
spotted an error? The archive wants to know.