Proofs: Skip list

The expected cost of a skip list search is O(log n) full

This proof shows: expected-time, space.

Fix a set of $n \ge 1$ keys and a key $k$. The levels $\ell(x)$ of the nodes are independent, with $\Pr[\ell(x) \ge i] = p^{i-1}$ for $1 \le i \le M$ and a constant $0 < p < 1$. Ignore the cap $M$ first; it only makes levels smaller. The cost of a search is the number of moves: the moves to the right in line L3 and the moves down in line L2. Insert and delete do one search and then $O(\ell(z))$ or $O(\ell(x))$ more work, and $\mathbb{E}[\ell(x)] = 1/(1-p)$, so it is enough to bound the search.

Space. The node $x$ has $\ell(x)$ pointers, and $\mathbb{E}[\ell(x)] = \sum_{i \ge 1} \Pr[\ell(x) \ge i] = \sum_{i \ge 1} p^{i-1} = 1/(1-p)$. So the expected number of pointers is $n/(1-p)$.

Number of levels. Let $N_i$ be the number of nodes with level $\ge i$, so $\mathbb{E}[N_i] = n p^{i-1}$. The top level $S.level$ is at most $L + \sum_{i > L} [N_i \ge 1]$ for each $L$, and $[N_i \ge 1] \le N_i$.

The backward walk. Reverse the search path: start at the node where the search ends at level 1, and walk back to the header at level $S.level$. At a node $y$ on level $i$ of the path, the previous step of the search was either a move down into level $i$ at $y$, which happens exactly when $\ell(y) > i$ or $y$ is the header, or a move right into $y$ along level $i$. For $y$ a node, the backward walk at $y$ has seen only the fact that $\ell(y) \ge i$ (and facts about other nodes), so, by independence, $\Pr[\ell(y) > i \mid \text{the walk so far}] = p$. So each backward step is a move up with probability at least $p$ (exactly $p$ at a node, 1 at the header), independent of the past.

Climbing to level $L$. Let $L = \lceil \log_{1/p} n \rceil$, so $p^{L} \le 1/n$ and $n p^{L-1} \le 1/p$. The backward steps taken while the walk is below level $L$ are dominated by the number of trials needed to get $L - 1$ successes, each trial a success with probability $p$. This number has expectation $(L - 1)/p$.

The levels from $L$ up. On level $i \ge L$, the moves to the right are at most $N_i$, since each visits a different node of level $\ge i$. The moves down from levels above $L$ are at most the number of levels above $L$, which is at most $\sum_{i > L} N_i$. So the expected number of steps at levels $\ge L$ is at most

Total. The expected cost of a search is at most

for constant $p$. For $p = 1/2$ this is $2 \lg n + 8$. The cap $M$ can only lower the levels; if $M \ge L$, the bound on the climb holds unchanged, and the steps at levels $\ge L$ are bounded as before. $\blacksquare$

Remarks. The bound holds for each set of keys and each query, because the only randomness is in the levels. With $p = 1/4$ the bound is $4 \log_4 n + 32/3 = 2 \lg n + O(1)$, the same leading term as $p = 1/2$, with $4/3$ instead of $2$ pointers per node on average.

Skip list operations keep the level lists sorted and return the right answers full

This proof shows: correctness, invariant, termination.

Write $\mathcal{L}_i$ for the list obtained by following $forward[i]$ from the header, and $N_{\ge i}$ for the set of nodes with $\ell(x) \ge i$. The invariant is (S1) $\mathcal{L}_1$ is strictly increasing and contains each node; (S2) for each $i$, $\mathcal{L}_i$ is $N_{\ge i}$ in increasing key order; (S3) $S.level = \max(1, \max_x \ell(x))$ and $S.header.forward[i] = $ NIL for $i > S.level$. (S1) is (S2) for $i = 1$. Treat the header as a node with key $-\infty$ and level $M$.

Lemma 1 (search). Assume (S1) to (S3). When the loop of line L2 finishes level $i$ (after line L3 for that $i$), $x = update[i]$ is the last element of $\{\text{header}\} \cup \{y \in N_{\ge i} : y.key < k\}$ in key order.

Proof. By downward induction on $i$. Before level $S.level$, $x$ is the header, which is in every list. Before level $i < S.level$, $x$ is the node of the claim for $i + 1$, which is in $N_{\ge i+1} \subseteq N_{\ge i}$ (or is the header), so it is on $\mathcal{L}_i$ by (S2). Line L3 moves right along $\mathcal{L}_i$ while the next key is less than $k$. Since $\mathcal{L}_i$ is sorted, it stops at the last node of $\mathcal{L}_i$ with key $< k$, provided that $x$ starts at or before it, which holds because $x.key < k$. The walk ends because the list is finite. $\square$

Search. By Lemma 1 for $i = 1$ and (S1), $update[1]$ is the last node with key $< k$, so $x = update[1].forward[1]$ in line L4 is the first node with key $\ge k$, or NIL. Key $k$ is present if and only if this node exists and has key $k$, which is the test of line L5. The search writes no field of the structure.

Insert. If $k$ is present, line L7 changes one value and nothing else, so the invariant holds. Otherwise let $z$ be the new node with level $\lambda$. For $i \le \min(\lambda, S.level)$, $update[i]$ is the last node of $\mathcal{L}_i$ with key $< k$ by Lemma 1; for $S.level < i \le \lambda$, line L9 sets $update[i]$ to the header, which is the last element of $\mathcal{L}_i = (\text{header})$ since that list is empty by (S3). Lines L12 and L13 put $z$ between $update[i]$ and its old successor in $\mathcal{L}_i$, whose key is $> k$ (it is $\ge k$ by the choice of $update[i]$, and $k$ is absent). So $\mathcal{L}_i$ stays sorted and becomes $N_{\ge i} \cup \{z\}$ for $i \le \lambda$. For $i > \lambda$ the list does not change, and $z \notin N_{\ge i}$. So (S2) holds. Line L9 raises $S.level$ to $\lambda$ when needed, so (S3) holds.

Delete. If $k$ is absent, line L15 returns and nothing changes. Otherwise $x$ is the node with key $k$. For $i \le \ell(x)$, $x \in N_{\ge i}$ is on $\mathcal{L}_i$, and its predecessor there is the last node with key $< k$, that is $update[i]$ by Lemma 1, because $\ell(x) \le S.level$. Line L17 unlinks $x$ from $\mathcal{L}_i$. The lists for $i > \ell(x)$ do not hold $x$. So each $\mathcal{L}_i$ becomes $N_{\ge i} \setminus \{x\}$ in order, and (S2) holds. Line L18 lowers $S.level$ while the top list is empty, which restores (S3).

Termination. Each walk of line L3 moves along a finite list, the loops of lines L2, L11 and L16 have at most $M$ rounds, and the loop of line L18 lowers $S.level$, which is at least 1. $\blacksquare$