Skip lists used coin flips instead of rotations to stay balanced

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.

Let coin flips, not rotations, keep balance

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.

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.

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.