Skip List

A randomized ordered structure of layered linked lists giving expected logarithmic search, insert, and delete.

Probabilistic balancing

A skip list stores elements in a sorted linked list, then adds express lanes above it: each higher level links a random subset of the nodes below, typically each node promoted with probability 1/2. Searching drops down levels, skipping large gaps at the top and refining below, giving expected O(log n) search without the rotations that balanced trees require.

Operations

Kronos motion — classical

To search, start at the top-left and move right while the next key is smaller than the target, dropping a level when it would overshoot. Insertion finds the position at each level, then links the new node into a random number of levels chosen by coin flips. Deletion unlinks the node from every level it appears in. Expected cost is O(log n) for all three.

Level assignment

python

import random

def random_level(max_level, p=0.5):
    lvl = 1
    while random.random() < p and lvl < max_level:
        lvl += 1
    return lvl

Why choose it

Simpler to implement than red-black or AVL trees, with no rebalancing cases.
Naturally supports range scans by following the bottom list.
Lock-free and concurrent variants are practical, which is why it backs several in-memory databases and Java's ConcurrentSkipListMap.
Expected bounds are logarithmic; the worst case is linear but astronomically unlikely.

Comparison

Skip lists trade the deterministic guarantees of balanced trees for simplicity and good concurrency. Like a treap, they rely on randomization for balance, but they use layered lists rather than a single tree, which makes concurrent updates easier to reason about.