跳表简介

跳表概述

这里我们讨论一种精巧的数据结构：跳表（skiplist），它具有多种应用。使用跳表，我们可以实现一个列表（List），其中 get(i)、set(i, x)、add(i, x) 和 remove(i) 操作的时间复杂度均为 $O(\log n)$。我们还可以实现一个有序集合（SSet），其中所有操作的期望时间复杂度均为 $O(\log n)$。

跳表的高效性依赖于其对随机化的运用。当向跳表中插入一个新元素时，跳表通过随机抛硬币的方式来决定该元素的高度。跳表的性能以期望运行时间和路径长度来衡量，这种期望是基于跳表所使用的随机抛硬币过程得出的。在实际实现中，跳表所用的随机抛硬币过程通过伪随机数生成器（或伪随机位生成器）来模拟。

跳表结构

从概念上讲，跳表是一系列单链表 $L_0, \cdots, L_h$ 的序列。每个链表 $L_r$ 包含 $L_{r−1}$ 中的一部分元素。我们从包含 $n$ 个元素的初始链表 $L_0$ 开始，然后从 $L_0$ 构造 $L_1$，再从 $L_1$ 构造 $L_2$，依此类推。链表 $L_r$ 中的元素是通过对 $L_{r−1}$ 中的每个元素 $x$ 进行一次抛硬币实验得到的：如果结果为正面，则将 $x$ 加入 $L_r$。这个过程持续进行，直到某一层 $L_r$ 为空为止。下图展示了一个包含七个元素的跳表示例：

对于跳表中的某个元素 $x$，我们称其高度为最大的 $r$ 值，使得 $x$ 出现在 $L_r$ 中。例如，仅出现在 $L_0$ 中的元素高度为 0。如果我们稍加思考就会发现，元素 $x$ 的高度实际上对应如下实验：反复抛硬币，直到出现反面为止。那么正面出现了多少次？答案并不意外：节点的期望高度为 1。（我们期望抛两次才能得到反面，但最后一次不计入。）跳表的高度即为其最高节点的高度。

每一层链表的头部都有一个特殊的节点，称为哨兵节点（sentinel），它作为链表的虚拟头节点。跳表的关键性质在于：从 $L_h$ 的哨兵节点到 $L_0$ 中的任意节点之间都存在一条较短的路径，称为搜索路径。记住如何构造某个节点 $u$ 的搜索路径非常简单（见下图）：从跳表的左上角（即 $L_h$ 的哨兵节点）出发，始终向右移动，除非这样会越过目标节点 $u$，此时应向下进入下一层链表。

更精确地说，为了构造 $L_0$ 中节点 $u$ 的搜索路径，我们从 $L_h$ 的哨兵节点 $w$ 开始。接着检查 w.next。如果 w.next 所指向的节点在 $L_0$ 中位于 $u$ 之前，则令 w = w.next；否则，向下移动到 $L_{h−1}$ 中 $w$ 的位置，并继续搜索。如此循环，直到到达 $u$ 在 $L_0$ 中的前驱节点为止。

下面这个结论（我们将在后续证明）表明，搜索路径非常短：

引理：对于 $L_0$ 中任意节点 $u$，其搜索路径的期望长度至多为 $2 \log n + O(1) = O(\log n)$。

为了节省空间，跳表的一种高效实现方式是定义节点 $u$ 包含一个数据值 $x$ 和一个指针数组 next，其中 u.next[i] 指向 $u$ 在链表 $L_i$ 中的后继节点。这种方式使得数据 $x$ 只被引用一次，即使 $x$ 出现在多个链表中也是如此。

1class SkiplistList(BaseList):
2    class Node(object):
3        """跳表中的一个节点"""
4        def __init__(self, x, h):
5            self.x = x
6            self.next = new_array(h+1)
7            self.length = numpy.ones(h+1, dtype=int)
8
9        def height(self):
10            return len(self.next) - 1

跳表有两种主要应用场景。在这两种应用中，$L_0$ 都存储了核心结构（一组元素的列表或一个有序元素集合）。这两种结构之间的主要区别在于搜索路径的导航方式，特别是它们如何判断搜索路径应该向下进入 $L_{r−1}$，还是在当前层 $L_r$ 中向右移动。