Skip list

The bottom level contains every ordered key, while sparser upper levels skip over multiple bottom-level entries. Search moves right without passing the query and drops a level when further horizontal movement would overshoot.

Nodes have different numbers of forward links according to their height. At the bottom, a complete key comparison confirms presence or absence. Reaching the right neighborhood through express links does not itself establish an exact match.

References: [1]

A typical policy repeatedly flips a fair coin for a new node, promoting it on heads and stopping on tails. Expected populations shrink at higher levels without globally rearranging every node after insertion to preserve exact spacing.

Under the independent random-choice model, search, insertion, and deletion take expected O(log n) time with expected O(n) storage. Expectation concerns construction randomness rather than a favorable user insertion order, and individual outcomes can still be worse.

References: [1] [2]

Insertion first searches and records predecessors at each level, then splices the new node into the levels selected by its random height. Deletion locates the same predecessors and unlinks every participating level, not only the bottom position.

Updates reuse local list operations while maintaining levels, boundary sentinels, and consistent forward links. They do not rotate nodes to preserve AVL or red-black invariants. Expected bounds and occasional extremes must be compared separately with deterministic balancing guarantees.

References: [1]