1. 跳跃表（Skip Lists）¶
1.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)\) 的平均情况性能概率 之间的张力，这正是概率数据结构的特征。
