跳跃表数据结构与算法分析

跳跃表[1,2,3]是一种用于在大多数应用程序中取代平衡树的概率数据结构。跳跃表拥有与平衡树相同的期望时间上界，并且更简单、更快、是用更少的空间。在查找与列表的线性操作上，比平衡树更快，并且更简单。

概率平衡也可以被用在基于树的数据结构[4]上，例如树堆（Treap）。与平衡二叉树相同，跳跃表也实现了以下两种操作

1. 通过搜索引用[5]，可以保证从任意元素开始，搜索到在列表中间隔为 的元素的任意期望时间是
2. 实现线性表的常规操作（例如将元素插入到列表第k个元素后面）

这几种操作在平衡树中也可以实现，但是在跳跃表中实现起来更简单而且非常的快，并且通常情况下很难在平衡树中直接实现（树的线索化可以实现与链表相同的效果，但是这使得实现变得更加复杂[6]）

最简单的支持查找的数据结构可能就是链表。Figure.1是一个简单的链表。在链表中执行一次查找的时间正比于必须考查的节点个数，这个个数最多是 。

Figure.2表示一个链表，在该链表中，每个一个节点就有一个附加的指针指向它在表中的前两个位置上的节点。正因为这个前向指针，在最坏情况下最多考查 个节点。

Figure.3将这种想法扩展，每个序数是4的倍数的节点都有一个指针指向下一个序数为4的倍数的节点。只有 个节点被考查。

这种跳跃幅度的一般情况如Figure.4所示。每个 节点就有一个指针指向下一个 节点，前向指针的间隔最大为 。可以证明总的指针最大不会超过 （见空间复杂度分析），但现在在一次查找中最多考查 个节点。这意味着一次查找中总的时间消耗为 ，也就是说在这种数据结构中的查找基本等同于二分查找（binary search）。

在这种数据结构中，每个元素都由一个节点表示。每个节点都有一个高度（height）或级别（level），表示节点所拥有的前向指针数量。每个节点的第 个前向指针指向下一个级别为 或更高的节点。

在前面描述的数据结构中，每个节点的级别都是与元素数量有关的，当插入或删除时需要对数据结构进行调整来满足这样的约束，这是很呆板且低效的。为此，可以将每个 节点就有一个指针指向下一个 节点的限制去掉，当新元素插入时为每个新节点分配一个随机的级别而不用考虑数据结构的元素数量。

虽然无法通过元素数量来确定每个节点的级别，但是通过考查Figure.1到Figure.4中的节点分布规律不难发现，随着级别的增加，当前级别的节点数量成比例减少。在Figure.1到Figure.4中，这个比例是 ，也就是说只有 个节点的级别是 ，随机选择节点的级别的概率分布遵循 。所以Figure.5也可以认为是这种数据结构的一个实例。

到此为止，已经得到了所有让链表支持快速查找的充要条件，而这种形式的数据结构就是跳跃表。接下来将会使用更正规的方式来定义跳跃表

1. 所有元素在跳跃表中都是由一个节点表示。
2. 每个节点都有一个高度或级别，有时候也可以称之为阶（step），节点的级别是一个与元素总数无关的随机数。规定NULL的级别是 。
3. 每个级别为 的节点都有 个前向指针，且第 个前向指针指向下一个级别为 或更高的节点。
4. 每个节点的级别都不会超过一个明确的常量MaxLevel。整个跳跃表的级别是所有节点的级别的最高值。如果跳跃表是空的，那么跳跃表的级别就是 。
5. 存在一个头节点head，它的级别是MaxLevel，所有高于跳跃表的级别的前向指针都指向NULL。

稍后将会提到，节点的查找过程是在头节点从最高级别的指针开始，沿着这个级别一直走，直到找到大于正在寻找的节点的下一个节点（或者是NULL），在此过程中除了头节点外并没有使用到每个节点的级别，因此每个节点无需存储节点的级别。

在跳跃表中，级别为 的前向指针与原始的链表结构中next指针的作用完全相同，因此跳跃表支持所有链表支持的算法。

对应到高级语言中的结构定义如下所示（后续所有代码示例都将使用C语言描述）

#define SKIP_LIST_KEY_TYPE     int#define SKIP_LIST_VALUE_TYPE   int#define SKIP_LIST_MAX_LEVEL    32#define SKIP_LIST_P            0.5
struct Node {  SKIP_LIST_KEY_TYPE    key;  SKIP_LIST_VALUE_TYPE  value;  struct Node          *forwards[]; // flexible array member};
struct SkipList {  struct Node *head;  int          level;};
struct Node *CreateNode(int level) {  struct Node *node;  assert(level > 0);  node = malloc(sizeof(struct Node) + sizeof(struct Node *) * level);  return node;}
struct SkipList *CreateSkipList() {  struct SkipList *list;  struct Node     *head;  int              i;
  list = malloc(sizeof(struct SkipList));  head = CreateNode(SKIP_LIST_MAX_LEVEL);  for (i = 0; i < SKIP_LIST_MAX_LEVEL; i++) {    head->forwards[i] = NULL;  }  list->head = head;  list->level = 1;
  return list;}

搜索

在跳跃表中进行搜索的过程，是通过Z字形遍历所有没有超过要寻找的目标元素的前向指针来完成的。在当前级别没有可以移动的前向指针时，将会移动到下一级别进行搜索。直到在级别为 的时候且没有可以移动的前向指针时停止搜索，此时直接指向的节点（级别为 的前向指针）就是包含目标元素的节点（如果目标元素在列表中的话）。在Figure.6中展示了在跳跃表中搜索元素 的过程。

整个过程的示例代码如下所示，因为高级语言中的数组下标从0开始，因此forwards[0]表示节点的级别为 的前向指针，依此类推

struct Node *SkipListSearch(struct SkipList *list, SKIP_LIST_KEY_TYPE target) {  struct Node *current;  int          i;
  current = list->head;  for (i = list->level - 1; i >= 0; i--) {    while (current->forwards[i] && current->forwards[i]->key < target) {      current = current->forwards[i];    }  }
  current = current->forwards[0];  if (current->key == target) {    return current;  } else {    return NULL;  }}

插入和删除

在插入和删除节点的过程中，需要执行和搜索相同的逻辑。在搜索的基础上，需要维护一个名为update的向量，它维护的是搜索过程中跳跃表每个级别上遍历到的最右侧的值，表示插入或删除的节点的左侧直接直接指向它的节点，用于在插入或删除后调整节点所在所有级别的前向指针（与朴素的链表节点插入或删除的过程相同）。

当新插入节点的级别超过当前跳跃表的级别时，需要增加跳跃表的级别并将update向量中对应级别的节点修改为head节点。

Figure.7和Figure.8展示了在跳跃表中插入元素 的过程。首先，在Figure.7中执行与搜索相同的查询过程，在每个级别遍历到的最后一个元素在对应层级的前向指针被标记为灰色，表示稍后将会对齐进行调整。接下来在Figure.8中，在元素为 的节点后插入元素 ，元素 对应的节点的级别是 ，这比跳跃表当前级别要高，因此需要增加跳跃表的级别到 ，并将head节点对应级别的前向指针标记为灰色。Figure.8中所有虚线部分都表示调整后的效果。

Figure.8 Insert element 16 and adjust forward pointers

struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) {  struct Node *update[SKIP_LIST_MAX_LEVEL];  struct Node *current;  int          i;  int          level;
  current = list->head;  for (i = list->level - 1; i >= 0; i--) {    while (current->forwards[i] && current->forwards[i]->key < target) {      current = current->forwards[i];    }    update[i] = current;  }
  current = current->forwards[0];  if (current->key == target) {    current->value = value;    return current;  }
  level = SkipListRandomLevel();  if (level > list->level) {    for (i = list->level; i < level; i++) {      update[i] = list->header;    }  }
  current = CreateNode(level);  current->key = key;  current->value = value;
  for (i = 0; i < level; i++) {    current->forwards[i] = update[i]->forwards[i];    update[i]->forwards[i] = current;  }
  return current;}

Figure.9和Figure.10展示了在跳跃表中删除元素 的过程。首先，在Figure.9中执行与搜索相同的查询过程，在每个级别遍历到的最后一个元素在对应层级的前向指针被标记为灰色，表示稍后将会对齐进行调整。接下来在Figure.10中，首先通过调整前向指针将元素 对应的节点从跳跃表中卸载，因为元素 对应的节点是级别最高的节点，因此将其从跳跃表中移除后需要调整跳跃表的级别。Figure.10中所有虚线部分都表示调整后的效果。

Figure.10 Delete element 19 and adjust forward pointers

struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) {  struct Node *update[SKIP_LIST_MAX_LEVEL];  struct Node *current;  int          i;
  current = list->head;  for (i = list->level - 1; i >= 0; i--) {    while (current->forwards[i] && current->forwards[i]->key < key) {      current = current->forwards[i];    }    update[i] = current;  }
  current = current->forwards[0];  if (current && current->key == key) {    for (i = 0; i < list->level; i++) {      if (update[i]->forwards[i] == current) {        update[i]->forwards[i] = current->forwards[i];      } else {        break;      }    }
    while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) {      list->level--;    }  }
  return current;}

生成随机级别

在前面提到过，随机选择节点的级别的概率分布遵循概率为 的指数分布，也就是说第 层的节点数量是第 层的一半。为了避免使用魔法值，定义一个分数 代表节点同时带有第 层前向指针和第 层前向指针的概率（在之前的讨论中， ）。节点的级别可以使用如下方法随机生成，在这个算法中节点的级别可以在不依赖跳跃表元素数量的前提下生成

int SkipListRandomLevel() {  int level;  level = 1;  while (random() < RAND_MAX * SKIP_LIST_P && level <= SKIP_LIST_MAX_LEVEL) {    level++;  }  return level;}

以下表格为按上面算法执行 次后，所生成的随机级别的分布情况。

MaxLevel的选择

在Figure.4中曾给出过对于10个元素的跳跃表最理想的分布情况，其中5个节点的级别是1，3个节点的级别是2，1个节点的级别是3，1个节点的级别是4。

这引申出一个问题：既然相同元素数量下，跳跃表的级别不同会有不同的性能，那么跳跃表的级别为多少才合适？

经过分析得出，跳跃表在级别 上期望的节点数量是 ，当 时这是成立的[1]。在此可以定义 来代表 。

由于级别可以安全地限定在 ，可以选择 （ 是跳跃表中元素数量的上限）。如果 ，那么 就可以安全地包含最多 个元素。

空间复杂度分析

前面提到过，分数 代表节点同时带有第 层前向指针和第 层前向指针的概率，而每个节点的级别最少是 ，因此级别为 的前向指针数为 。定义 表示所有前向指针的总量，由等比数列求和公式可得

对 求极限，有

易证，这是一个关于 的单调递增函数，因此 的值越大，跳跃表中前向指针的总数越多。因为 是已知的常数，所以说跳跃表的空间复杂度是 。

时间复杂度分析

非形式化分析

延续前面的定义，分数 代表节点同时带有第 层前向指针和第 层前向指针的概率，也就是说相邻两个级别为 的节点中间期望有 个级别为 的节点。

而通过考查Figure.6搜索路径，不难发现，在级别 的搜索永远不会触达级别大于 的节点（因为级别大于 的节点已经在级别 的搜索中被否决），因此可以认为在理想情况下每一层最多只需要访问 个节点。

由搜索是通过Z字形遍历所有没有超过要寻找的目标元素的前向指针来完成的，因此搜索总是需要经过 层。所以期望的访问次数是 ，因为 ，所以期望的访问次数是 ，因为 是可以确定的常数，因此跳跃表的搜索、插入和删除的时间复杂度都是

形式化分析

定义1. ：定义 和 是两个非负的无关的随机变量（通常来说， 和 表示算法 和 的执行时间）。定义 当且仅当对于任意 ， 在 中出现的概率总是小于 在 中出现的概率时为真。更加形式化的定义

延续分数 代表节点同时带有第 层前向指针和第 层前向指针的概率的定义，考虑反方向分析搜索路径。

搜索的路径总是小于必须执行的比较的次数的。首先需要考查从级别 （在搜索到元素前遍历的最后一个节点）爬升到级别 所需要反向跟踪的指针数量。虽然在搜索时可以确定每个节点的级别都是已知且确定的，在这里仍认为只有当整个搜索路径都被反向追踪后才能被确定，并且在爬升到级别 之前都不会接触到head节点。

在爬升过程中任何特定的点，都认为是在元素 的第 个前向指针，并且不知道元素 左侧所有元素的级别或元素 的级别，但是可以知道元素 的级别至少是 。元素 的级别大于 的概率是 ，可以通过考虑视认为这个反向爬升的过程是一系列由成功的爬升到更高级别或失败地向左移动的随机独立实验。在爬升到级别 过程中，向左移动的次数等于在连续随机试验中第 次成功前的失败的次数，这符合负二项分布。期望的向上移动次数一定是 。因此可以得到无限列表中爬升到 的代价

的选择

得到搜索代价为 后，可以分析 的选择对 的影响。为了更好的分析 对搜索时间的影响，需要对 进行等价变换

不难看出，对于任意确定的 ， 都是确定的，因此只需要分析 的变化趋势就可以。为了更好的进行对比，以 为基础值进行标准化，Figure.11就是随着 的变化，搜索时间的变化趋势，其中 的点是搜索时间最好的点，但是二的整数次幂可以更好地进行随机级别的生成。

而前面分析空间复杂度时也确定了 ，空间用量随着 减小而降低，因此 是优于 的，这也是Redis中使用 而不是 的一个原因。

快速随机访问

在跳跃表中通过前向引用实现了 时间复杂度的搜索、插入与删除算法，但是对于随机访问数组中第 个元素操作仍需要 时间。通过观察Figure.7中的Z字形搜索路径，不难发现，从头节点到某个节点的路径中所有前向指针的跨度的和，就是这个节点在跳跃表中的位置。那么通过在前向指针中维护当前节点到目标节点的跨度，就可以保证随机访问的时间复杂度也是 。

首先，需要对数据结构重新进行定义，在前向指针中增加跨度相关的记录，并将其初始设置为0。此外，可以认为NULL在跳跃表中的位置永远是跳跃表的长度（从0开始），因此需要在跳跃表中记录总长度。

本节中的代码参考自Redis的跳跃表实现[8], 为了与前面的代码风格保持一致，进行了适当的修改

#define SKIP_LIST_KEY_TYPE     int#define SKIP_LIST_VALUE_TYPE   int#define SKIP_LIST_MAX_LEVEL    32#define SKIP_LIST_P            0.5
struct Node; // forward definition
struct Forward {  struct Node *forward;  int          span;}
struct Node {  SKIP_LIST_KEY_TYPE    key;  SKIP_LIST_VALUE_TYPE  value;  struct Forward        forwards[]; // flexible array member};
struct SkipList {  struct Node *head;  int          level;  int          length;};
struct Node *CreateNode(int level) {  struct Node *node;  assert(level > 0);  node = malloc(sizeof(struct Node) + sizeof(struct Forward) * level);  return node;}
struct SkipList *CreateSkipList() {  struct SkipList *list;  struct Node     *head;  int              i;
  list = malloc(sizeof(struct SkipList));  head = CreateNode(SKIP_LIST_MAX_LEVEL);  for (i = 0; i < SKIP_LIST_MAX_LEVEL; i++) {    head->forwards[i].forward = NULL;    head->forwards[i].span = 0;  }
  list->head = head;  list->level = 1;
  return list;}

接下来需要修改插入和删除操作，来保证在跳跃表修改后跨度的数据完整性。

需要注意的是，在插入过程中需要使用indices记录在每个层级遍历到的最后一个元素的位置，这样通过做简单的减法操作就可以知道每个层级遍历到的最后一个元素到新插入节点的跨度。

struct Node *SkipListInsert(struct SkipList *list, SKIP_LIST_KEY_TYPE key, SKIP_LIST_VALUE_TYPE value) {  struct Node *update[SKIP_LIST_MAX_LEVEL];  struct Node *current;  int          indices[SKIP_LIST_MAX_LEVEL];  int          i;  int          level;
  current = list->head;  for (i = list->level - 1; i >= 0; i--) {    if (i == list->level - 1) {      indices[i] = 0;    } else {      indices[i] = indices[i + 1];    }        while (current->forwards[i].forward && current->forwards[i].forward->key < target) {      indices[i] += current->forwards[i].span;      current = current->forwards[i].forward;    }    update[i] = current;  }
  current = current->forwards[0].forward;  if (current->key == target) {    current->value = value;    return current;  }
  level = SkipListRandomLevel();  if (level > list->level) {    for (i = list->level; i < level; i++) {      indices[i] = 0;      update[i] = list->header;      update[i]->forwards[i].span = list->length;    }  }
  current = CreateNode(level);  current->key = key;  current->value = value;
  for (i = 0; i < level; i++) {    current->forwards[i].forward = update[i]->forwards[i].forward;    update[i]->forwards[i].forward = current;    current->forwards[i].span = update[i]->forwards[i].span - (indices[0] - indices[i]);    update[i]->forwards[i].span = (indices[0] - indices[i]) + 1;  }
  list.length++;
  return current;}

struct Node *SkipListDelete(struct SkipList *list, SKIP_LIST_KEY_TYPE key) {  struct Node *update[SKIP_LIST_MAX_LEVEL];  struct Node *current;  int          i;
  current = list->head;  for (i = list->level - 1; i >= 0; i--) {    while (current->forwards[i].forward && current->forwards[i].forward->key < key) {      current = current->forwards[i].forward;    }    update[i] = current;  }
  current = current->forwards[0].forward;  if (current && current->key == key) {    for (i = 0; i < list->level; i++) {      if (update[i]->forwards[i].forward == current) {        update[i]->forwards[i].forward = current->forwards[i];        update[i]->forwards[i].span += current->forwards[i].span - 1;      } else {        break;      }    }
    while (list->level > 1 && list->head->forwards[list->level - 1] == NULL) {      list->level--;    }  }
  return current;}

当实现了快速随机访问之后，通过简单的指针操作即可实现区间查询功能。

参考文献

1. Pugh, W. (1989). A skip list cookbook. Tech. Rep. CS-TR-2286.1, Dept. of Computer Science, Univ. of Maryland, College Park, MD [July 1989]
2. Pugh, W. (1989). Skip lists: A probabilistic alternative to balanced trees. Lecture Notes in Computer Science, 437–449. https://doi.org/10.1007/3-540-51542-9_36
3. Weiss, M. A. (1996). Data Structures and Algorithm Analysis in C (2nd Edition) (2nd ed.). Pearson.
4. Aragon, Cecilia & Seidel, Raimund. (1989). Randomized Search Trees. 540-545. 10.1109/SFCS.1989.63531.
5. Wikipedia contributors. (2022b, November 22). Finger search. Wikipedia. https://en.wikipedia.org/wiki/Finger_search
6. Wikipedia contributors. (2022a, October 24). Threaded binary tree. Wikipedia. https://en.wikipedia.org/wiki/Threaded_binary_tree
7. Wikipedia contributors. (2023, January 4). Negative binomial distribution. Wikipedia. https://en.wikipedia.org/wiki/Negative_binomial_distribution
8. Redis contributors. Redis ordered set implementation. GitHub. https://github.com/redis/redis