Skip List Level-Height & Search-Cost Distribution

Skip List Parameters

Promotion probability p 0.50

Elements N 200

Max levels cap 16

Ready — build a list to begin.

Live Statistics

Empirical avg height

–

Theoretical 1/(1−p)

–

Max level reached

–

log(1/p) N

–

Empirical search cost

–

Theoretical estimate

–

How it works

A skip list gives every node a random height by flipping a biased coin: it starts at level 1, and is promoted one level higher with probability p, repeating until a flip fails (capped at a maximum). This makes the height geometrically distributed:

P(height = k) = p^(k−1) · (1 − p)
E[height]     = 1 / (1 − p)
Expected count of nodes reaching level k  ≈  N · p^(k−1)

That exponential decay is exactly what the bars show: each lane holds roughly a p-fraction of the nodes below it, so the "express lanes" get exponentially sparser near the top — the same shape as a balanced tree's levels, produced by chance instead of by rebalancing.

Because search starts at the top (sparsest) lane and only drops down when it overshoots, Pugh's 1990 analysis shows the expected number of key comparisons to find any element is:

E[comparisons] ≈ log(1/p)(N) / p

p slider — the promotion probability; higher p means taller lists and more index overhead but shorter average lanes to fall through.
N slider — how many keys are inserted (sorted 0..N−1) into the list.
Rebuild — redraws every node's height from fresh coin flips, so you can see the histogram vary trial to trial around its expectation.
Run search trials — performs real top-down skip-list searches for random keys against the built structure and averages the actual comparison count, which you can compare directly to the theoretical estimate above.

Real-world relevance: this exact mechanism backs Redis sorted sets, LevelDB/RocksDB memtables and Lucene's term dictionaries — a randomized alternative to AVL/red-black rebalancing that gets O(log n) expected operations from probability instead of invariants.

Empirical lane occupancy Theoretical N·p^(k−1)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.