Skip Lists as a Randomized Balanced-BST Replacement

What This Concept Is

A skip list keeps a sorted bottom list and increasingly sparse sorted levels. Each node's height is sampled by repeated independent promotion with probability p between zero and one. Search moves right without overshooting, then down. It still has invariants: every upper level is an ordered sublist of the lower one, pointers have valid heights and updates preserve all affected links.

Why It Matters Here

This distinguishes internal randomization from an assumption that input keys arrive randomly. It also makes the probability space part of the complexity guarantee: expected logarithmic search is not a deterministic per-operation latency bound.

Concrete Examples

With p=1/2, a node appears at level j with probability 2^-j when the bottom is level 0. Expected nodes at level j are n/2^j; expected pointers per node sum to 1+1/2+1/4+...=2. Thus expected storage is O(n). Backward analysis of a search path gives constant expected horizontal work per level and O(log(n+1)) expected search work. These are bounds, not an exact universal cost formula for every p or implementation.

Suppose bottom keys are [2,5,8,12], next level [2,8], highest [8]. To search for 10, move to 8 where possible, descend, then stop before 12. Insertion records the predecessor at each participating level and splices the new node into those links. Deletion must unlink every occurrence of the node, not only its bottom-level link.

If all nodes receive height zero, search can inspect n nodes. For independently sampled heights, a union bound gives Pr(any height >= L) <= n*p^L. That controls maximum tower height; it is not by itself a complete search-time tail bound. A fixed maximum height chosen too small can invalidate intended scaling behavior as n grows.

Common Confusion / Misconceptions

An adversary that observes random choices and adaptively selects operations needs a model beyond a fixed sequence independent of those choices. A fixed seed reproduces a test, not a probabilistic theorem. Layered pointers do not make concurrency automatically safe; synchronization and memory reclamation are separate topics.

How To Use It

State p, height limits, duplicate-key policy and the randomness model. Trace pointer updates with supplied heights before randomizing. Compare mixed operations to an ordered-map oracle. Report distributions over independent seeds and worst observed work separately from the expected bound. Skip-list implementation is an explicit depth option after the AVL core.

Check Yourself

What invariant remains despite randomized shape? Why does a height tail bound not immediately prove a search-time tail bound? Which randomness does the expectation average over?

Mini Drill or Application

For n=1024 and p=1/2, bound the probability that any node reaches level 20. Feedback: at most 1024/2^20=1/1024 by a union bound. Explain why this says nothing deterministic about a particular seed.

Read This Only If Stuck

Pat Morin, Open Data Structures: Skiplists develops the search-path analysis. Use CLRS for comparison with deterministic balancing.