Data-Structure

跳表 ( Skiplist ) 的数据结构实现

数据结构的学习与实现

Posted by Nicodechal on 2019-10-02

序

最近看 Redis 的相关书籍时，提到 Redis 中的有序集合是使用跳表 ( Skiplist ) 这种数据结构实现的。Skiplist 可以的实现在 O(logn)O(logn) 内完成数据的添加，查询和删除。从复杂度上看，跳表和红黑树的性能相当，但跳表相比于红黑树更易实现。

关于跳表的相关概念这里不再赘述，直接考虑如何使用代码实现。本文使用 C++ 对跳表进行实现。

数据结构实现

跳表节点 Node 设计

首先，定义跳表节点的结构如下：

1
2
3
4
5
6
7
class Node
{
public:
  int v; // 该节点的值
  vector<Node *> n; // 每层指向该层下一个节点的指针
  Node(int v, int l) : v(v), n(l) {}
};

跳表可以看做是一个有多层的链表结构，因此相对于普通的链表，指向下一个节点的指针需要变为一个指针数组，用于指向不同层的下一节点。

下面会使用一个空节点来作为跳表的根节点 root，这样就不需要判断是否是头结点了，方便代码实现。

1
Node* root = new Node(-1, 0);

跳表的实现

首先定义需要实现的方法，主要有三个方法，分别用来实现查询，添加和删除：

1
2
3
bool search(int target);
void add(int target);
bool erase(int target)

如果将跳表理解成多层的链表，那么相对于普通的链表，查询，添加或删除元素时，就需要分别对每一层都进行操作。

在每一层上的操作和普通链表相同，所以可以写一个函数进行单层的搜索：

1
2
3
4
5
6
7
8
9
10
// 从 *r* 节点开始，搜索第 *l* 层，搜索目标为 *t*
Node *search_level(Node *r, int l, int t)
{
  auto cur = r;
  while (cur->n[l] && cur->n[l]->v < t)
  {
    cur = cur->n[l];
  }
  return cur;
}

该函数就是简单的在一层 l 中搜索目标 t，r 为开始搜索的节点，这个参数是为了方便从一层的任意节点开始搜索。该函数返回的节点为本层中 最大的小于 t 的节点，所以有两种情况：

  1. 返回节点的在本层的下一个节点的值就是 t
  2. 返回节点在本层没有下一个节点 ( 即该层所有节点值都小于 t )

也就是说，如果值为 t 的节点存在，那返回的节点就是 t 值节点的前一个节点，这样做的原因是为了在删除和添加时使用的方便，因为对于删除操作，需要知道每一层上待删除节点的前一个节点，将待删除节点从本层删除；添加节点时，也需要知道每层比目标值小的节点，用于将节点插入。

另外，由于跳表是一个有序链表，所以如果在一层 l 搜索结束，在 l - 1 层只要在上一次的到的节点开始继续向下查找即可，不需要从头查询。最后的查询轨迹类似于“阶梯形”。

下面实现从最高层开始在跳表中查询目标值的方法，这里直接使用 头结点的指针数组 ( root->n ) 的 长度 ( root->n.size() ) 保存当前跳表的层数 ( 层数大于 0，层编号从 0 开始 )。最终返回每一层的目标值的前一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<Node *> find_prev_nodes(int t)
{
  int l = root->n.size();
  vector<Node *> list(l); // 保存每层的目标值的前一个节点

  auto cur = root;
  while (--l >= 0)
  {
    // 在每一层搜索，更新 cur 使得下一层搜索直接从本节点开始搜索。
    cur = search_level(cur, l, t); 
    list[l] = cur;
  }

  return list;
}

跳表的查询

关于跳表的查询，在之前介绍的内容的基础上比较容易实现：过程类似上面的 find_prev_nodes 函数，只要中间只要碰到目标值 ( 即当前节点的下一个节点值为目标值 ) 即可返回 true，否则返回 false。为了实现代码复用，这里考虑直接使用上面的方法实现 ( 上面方法之所以那样写，是为了增加删除方便，避免了再次查找每层前一个节点带来的复杂度 )。

于是现在要考虑，如何在已知 一个节点在每层的 小于它本身的值最大的节点 时，知道跳表中是否存在目标值?

由于跳表的结构特点，跳表的 0 层可以看做是一个普通的链表，因此，如果一个值存在，则一定在 0 层可以找到。基于此，可以实现跳表的查询：

1
2
3
4
5
6
bool search(int target)
{
  auto l = find_prev_nodes(target);
  // 判断第 0 层节点的下一个节点值是不是目标值，是则返回 `true`
  return l[0]->n[0] && l[0]->n[0]->v == target; 
}

跳表的添加

跳表添加可以基于普通链表的添加来实现，但需要考虑同时在多层添加节点的情况。

在多少层添加节点取决于概率事件，首先，将节点加入到第 0 层，然后，抛硬币，如果是正面则再把节点加入上一层，然后再次抛硬币，直到出现反面或者达到最高层数停止。计算层数的代码如下：

1
2
3
4
5
6
7
8
9
int get_level()
{
  const int MAX_LEVEL = 32;
  int level = 1; // 这里表示至少要添加到第 0 层，即层数是 1。
  // 如果层数小于最大层数或者一次概率事件返回 `true` 则继续加入上一层
  while (level <= MAX_LEVEL && rand() % 100 < 50)
    level++;
  return level;
}

这里先求出总的层数在插入，和边算边插入一样。下面看下插入的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void add(int target)
{
  // 使用上面的函数得到该节点的高度
  auto n = new Node(target, get_level());
  // 更新跳表的高度
  if (n->n.size() > root->n.size())
  {
    root->n.resize(n->n.size());
  }
  // 计算该节点的每层前节点
  auto l = find_prev_nodes(target);
  // 这里循环的高度为**插入节点的高度**
  for (int i = 0; i < n->n.size(); i++)
  {
    // 常规的节点插入链表
    n->n[i] = l[i]->n[i];
    l[i]->n[i] = n;
  }
}

跳表的删除

由于我们已经为了删除设计了寻找目标节点在每层的前一个节点的函数，因此，只要可以确定表中有目标节点，就可以方便的进行删除。

在每一层中，删除节点的操作和普通链表一样，即，让前一个节点的指针指向删除节点的下一个节点，删除节点的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool erase(int target)
{
  // 前节点列表
  auto l = find_prev_nodes(target); 
  // 这里判断节点是否存在
  if (l[0]->n[0] && l[0]->n[0]->v != target)
    return false;

  // 存在，cur就是。
  auto cur = l[0]->n[0];

  // 从**删除节点的最高层**开始删除，再往上层没有这个节点
  for (int i = cur->n.size() - 1; i >= 0; i--)
  {
    // 常规的链表删除
    l[i]->n[i] = cur->n[i];
    // 由于 root 需要记录最高层数，所以如果删除后 root->n[i]
    // 为 NULL 则降低 root 的指针数组高度。
    if (!root->n[i])
      root->n.pop_back();
  }

  delete cur;
  return true;
}

这里注意，由于删除只会影响节点存在的层 ( 如果一个节点在 l 层，那么所有小于 l 的层也会有该节点 )，所以，循环从删除节点的最高层开始。循环中，除了进行普通的链表删除，还需要考虑 root 的指针数组长度 ( 代表了跳表的层数 )。

如果一个节点删除后，root 的在该层的下一个节点为 NULL 说明，

  1. 该层只剩下本节点。
  2. 当前删除的层为最高层。如果不是最高层，删完 root->n[i] 不会是 NULL，也不会只剩下本节点 ( 至少有一个节点在第 i 层，不然本节点就是最高层 )

因此，如果 root 的下个节点为 NULL，就需要降低跳表的高度。

小结

本文使用 C++ 实现了基本的跳表数据结构，还有改进的空间，但通过该数据结构的编写可以了解跳表的相关特点和技术。实现中比较重要的技术总结如下：

  1. 使用空的 root 节点并用其记录最高层数，这样可以方便的完成其他操作不需要额外的判断。
  2. 得到每层刚好小于目标值的节点列表可以很好地减少实现的困难。
  3. 直接为节点指定起始层数可以使得代码更清晰，每次只要根据节点的层数就可以知道节点影响的范围。
  4. 直接在第 0 层进行节点是否存在的判断，方便快捷易实现。
FEATURED TAGS
Data-Structure
FRIENDS