Skip List Lane Diagram & Search-Cost Distribution (2D)

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

Every node's height comes from flipping a biased coin: start at level 1, promote one level higher with probability p, repeat until a flip fails (capped at a maximum). Height is 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)

This 2D view draws the skip list itself — the classic textbook "lane diagram": each row is a level, each dot is a real node placed at its sorted key position, and every horizontal segment is a real forward pointer chased directly out of the built structure (not a redraw approximation). The panel below is the level-occupancy histogram against the theoretical N·p^(k−1) curve. Press "Run search trials" to see an actual top-down search animate across the lanes — starting at the sparsest top lane, moving right while the next key is smaller, dropping down a level whenever it isn't.

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

p slider — the promotion probability; higher p means taller lists and denser upper lanes.
N slider — how many sorted keys (0..N−1) are inserted into the list.
Rebuild — redraws every node's height from fresh coin flips.
Run search trials — runs 300 real top-down searches and animates one of them as a highlighted path across the diagram.

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.

Skip-list lanes (real pointers) Theoretical N·p^(k−1) curve Animated search path