15.2. 跳表（Skip Lists）¶
15.2.1. 跳表¶
本模块介绍了一种基于概率的搜索结构，称为 跳表 。与 BST 类似，跳表也被设计用于克服基于数组和链表的基本局限性：搜索或更新操作都需要线性时间。跳表是 概率数据结构 的一个例子，因为它在某些决策上是随机的。
跳表提供了 BST 及相关树结构的替代方案。 BST 的主要问题是它可能很容易变得不平衡。 2-3 树 无论数据值的插入顺序如何都保证保持平衡，但实现起来相当复杂。 AVL 树 和 伸展树 也保证提供良好的性能，但与 BST 相比需要额外的复杂度作为代价。跳表比已知的平衡树结构更容易实现。跳表不能保证提供良好的性能（这里良好性能定义为最坏情况下 \(\Theta(\log n)\) 的查找、插入和删除时间），但将以极高的概率提供良好的性能（不像 BST 很有可能表现不佳）。因此，它是实现难度与性能之间的良好折衷。
我们可以继续以这种方式向选定的结点添加指针 --- 给每第四个结点一个第三个指针，给每个第八个结点一个第四个指针，依此类推—直到我们达到终极形态：对于 \(n\) 个结点的链表，第一个和中间结点的 \(\log n\) 个指针。要查找，从最底层的指针行开始，尽可能远地前进，一次跳过许多结点。然后，根据需要向上移动到越来越短的步长。通过这种安排，最坏情况下的访问次数是 \(\Theta(\log n)\)。
我们将在每个跳表结点中存储一个名为 forward 的数组存放指针。位置 forward[0] 存储第 0 层指针， forward[1] 存储第 1 层指针，依此类推。它还用一个键值对（KVPair）存储结点的键和记录。 SkipNode 类如下：
class SkipNode {
private KVPair rec;
private SkipNode[] forward;
public Object element() {
return rec.value();
}
public Comparable key() {
return rec.key();
}
public SkipNode(Comparable key, Object elem, int level) {
rec = new KVPair(key, elem);
forward = new SkipNode[level + 1];
for (int i = 0; i < level; i++) {
forward[i] = null;
}
}
public String toString() {
return rec.toString();
}
}
class SkipNode<K extends Comparable<K>, E> {
private KVPair<K, E> rec;
private SkipNode<K, E>[] forward;
public E element() {
return rec.value();
}
public K key() {
return rec.key();
}
@SuppressWarnings("unchecked")
public SkipNode(K key, E elem, int level) {
rec = new KVPair<K, E>(key, elem);
forward = new SkipNode[level + 1];
for (int i = 0; i < level; i++)
forward[i] = null;
}
public String toString() {
return rec.toString();
}
}
跳表对象包含数据成员 level ，它存储当前跳表中任何结点的最高层。跳表存储一个名为 head 的表头结点，其中有 level+1 个指针，表头层初始为 0，而对空链表层设置为 -1。 SkipList 类的开头如下：
class SkipList implements Dictionary {
private SkipNode head;
private int level;
private int size;
static private Random ran = new Random(); // Hold the Random class object
public SkipList() {
head = new SkipNode(null, null, 0);
level = -1;
size = 0;
}
class SkipList<K extends Comparable<K>, E> implements Dictionary<K, E> {
private SkipNode<K, E> head;
private int level;
private int size;
static private Random ran = new Random(); // Hold the Random class object
public SkipList() {
head = new SkipNode<K, E>(null, null, 0);
level = -1;
size = 0;
}
find 函数的工作方式如下。
// Return the (first) matching matching element if one exists, null otherwise
public Object find(Comparable key) {
SkipNode x = head; // Dummy header node
for (int i = level; i >= 0; i--) { // For each level...
while ((x.forward[i] != null) && (x.forward[i].key().compareTo(key) < 0)) { // go forward
x = x.forward[i]; // Go one last step
}
}
x = x.forward[0]; // Move to actual record, if it exists
if ((x != null) && (x.key().compareTo(key) == 0)) { return x.element(); } // Got it
else { return null; } // Its not there
}
// Return the (first) matching matching element if one exists, null otherwise
public E find(K key) {
SkipNode<K, E> x = head; // Dummy header node
for (int i = level; i >= 0; i--) // For each level...
while ((x.forward[i] != null) && (x.forward[i].key().compareTo(key) < 0)) // go forward
x = x.forward[i]; // Go one last step
x = x.forward[0]; // Move to actual record, if it exists
if ((x != null) && (x.key().compareTo(key) == 0)) return x.element(); // Got it
else return null; // Its not there
}
理想的跳表是这样组织的：（如果不计算表头结点的话）一半的结点只有一个指针，四分之一有两个，八分之一有三个，依此类推。理想情况下，距离应该是等距的；实际上这是一个 "完全平衡"的跳表。在正常的插入和删除过程中维持这种平衡代价很高。跳表的关键在于我们根本不担心这些。每当插入一个结点时，我们给它指定一层（即一定数量的指针）。指定是随机的，使用几何分布，结点有一个指针的概率为 50%，有两个指针的概率为 25%，依此类推。下面的函数根据这样的分布确定层。
// Pick a level using a geometric distribution
int randomLevel() {
int lev;
for (lev = 0; Math.abs(ran.nextInt()) % 2 == 0; lev++) { // ran is random generator
; // Do nothing
}
return lev;
}
// Pick a level using a geometric distribution
int randomLevel() {
int lev;
for (lev = 0; Math.abs(ran.nextInt()) % 2 == 0; lev++) // ran is random generator
; // Do nothing
return lev;
}
一旦确定了结点的合适层，下一步就是找到应插入结点的位置，并在其所有层适当地链接进去。下面是在跳表中插入新值的实现，随后是该过程的可视化演示。注意，我们在遍历跳表的过程中构建了一个 update 数组，这样我们可以更新那些将位于被插入结点之前的结点的指针。
/** Insert a key, element pair into the skip list */
public void insert(Comparable key, Object elem) {
int newLevel = randomLevel(); // New node's level
if (newLevel > level) { // If new node is deeper
adjustHead(newLevel); // adjust the header
}
// Track end of level
SkipNode[] update = new SkipNode[level + 1];
SkipNode x = head; // Start at header node
for (int i = level; i >= 0; i--) { // Find insert position
while ((x.forward[i] != null) && (x.forward[i].key().compareTo(key) < 0)) {
x = x.forward[i];
}
update[i] = x; // Track end at level i
}
x = new SkipNode(key, elem, newLevel);
for (int i = 0; i <= newLevel; i++) { // Splice into list
x.forward[i] = update[i].forward[i]; // Who x points to
update[i].forward[i] = x; // Who points to x
}
size++; // Increment dictionary size
}
private void adjustHead(int newLevel) {
SkipNode temp = head;
head = new SkipNode(null, null, newLevel);
for (int i = 0; i <= level; i++) {
head.forward[i] = temp.forward[i];
}
level = newLevel;
}
/** Insert a key, element pair into the skip list */
public void insert(K key, E elem) {
int newLevel = randomLevel(); // New node's level
if (newLevel > level) // If new node is deeper
adjustHead(newLevel); // adjust the header
// Track end of level
SkipNode<K, E>[] update = new SkipNode[level + 1];
SkipNode<K, E> x = head; // Start at header node
for (int i = level; i >= 0; i--) { // Find insert position
while ((x.forward[i] != null) && (x.forward[i].key().compareTo(key) < 0))
x = x.forward[i];
update[i] = x; // Track end at level i
}
x = new SkipNode<K, E>(key, elem, newLevel);
for (int i = 0; i <= newLevel; i++) { // Splice into list
x.forward[i] = update[i].forward[i]; // Who x points to
update[i].forward[i] = x; // Who points to x
}
size++; // Increment dictionary size
}
private void adjustHead(int newLevel) {
SkipNode<K, E> temp = head;
head = new SkipNode<K, E>(null, null, newLevel);
for (int i = 0; i <= level; i++)
head.forward[i] = temp.forward[i];
level = newLevel;
}
remove 函数与插入类似，因为 update 数组也是作为查找要删除的记录的一部分构建的。然后，update 数组指定的那些结点会调整它们的前向指针，使其绕过被删除的结点。
一个新插入的结点可能由 randomLevel 生成很高的层，也可能生成很低的层。有可能跳表中的许多结点拥有很多指针，导致不必要的插入开销，并在查找时产生糟糕（即 \(\Theta(n)\)）的性能，因为不会被跳过太多结点。相反，太多结点可能具有较低的层。在最坏情况下，所有结点都在第 0 层，相当于一个普通的链表。如果是这样，查找将再次需要 \(\Theta(n)\) 的时间。然而，性能糟糕的概率相当低。连续十个结点都在第 0 层的概率只有 1024 分之一。诸如跳表这样的概率数据结构的座右铭是 "不要担心，要开心"。我们简单地接受 randomLevel 的结果，并期望概率最终会偏向我们。这种方法的优点是算法简单，同时平均情况下所有操作只需要 \(\Theta(\log n)\) 的时间。对于大小为 \(n\) 的跳表，期望的内存用量是 \(2n\)。这是因为一个第 \(l\) 层的结点需要 \(l+1\) 个前向指针，但概率为 \((1/2)^{(l+1)}\)。所以跳表期望有 \(\sum_{l=0}^{l=\infty} (l+1)/2^{(l+1)}\) 个指针，即 2。因此，BST 和跳表所需的指针数量期望是相同的。
在实践中，跳表可能比存储相同数据的 BST 获得更好的性能。 BST 可能因数据插入的顺序而性能糟糕。例如，如果 \(n\) 个结点按其键值的升序插入 BST，那么 BST 将看起来像一个链表，最深的结点深度为 \(n-1\)。如果在 BST 的生命周期内插入的数据可以是随机有序的，那么插入和查找操作成本的概率分布将与跳表类似。 BST 的问题在于这种随机化事实上并不会发生，而是 BST 受实际输入和查找顺序的约束。
相比之下，跳表的性能不依赖于值插入链表的顺序。从某种意义上说，当选择结点深度时，数据会作为跳表概率行为的一部分自动 "随机化"。随着跳表中结点数量的增加，遇到最坏情况的可能性按几何级数递减。因此，跳表说明了理论最坏情况（在这种情况下，每次跳表操作为 \(\Theta(n)\)）与迅速增加的 \(\Theta(\log n)\) 的平均情况性能概率之间的张力，这正是概率数据结构的特征。
