浅谈玄学数据结构：跳表

Aleph1022

2018-10-20 11:19:29

算法·理论

前言

为啥 Redis 使用跳表而不是使用红黑树？

  1. SkipList 的复杂度和红黑树一样，而且实现起来更简单。

  2. 在并发环境下 SkipList 有另外一个优势，红黑树在插入和删除的时候可能需要做一些保持平衡的操作，这样的操作可能会涉及到整个树的其他部分，而 SkipList 的操作显然更加局部性一些，所以需要盯住的节点更少，因此在这样的情况下性能好一些。

上文引用自：知乎 - 为啥 redis 使用跳表(skiplist)而不是使用 red-black？ - 于康的回答

正文

如果你要在一个有序的序列中查找元素 k，相信大多数人第一反应都是二分查找。

如果你需要维护一个支持插入操作的有序表，大家又会想到链表。

但是，链表无法随机访问，因此也无法二分。而且在有序的链表中间插入，寻找插入的位置最坏是 O(n) 的。

我们先来看看这张图：

如果要在这里面找 21，过程为 3 \to 6 \to 7 \to 9 \to 12 \to 17 \to 19 \to 21。

我们考虑从中抽出一些节点，建立一层索引作用的链表：

这样的话，找 21 的过程变成 6 \to 9 \to 17 \to 21。

跳表的主要思想就是这样逐渐建立索引，加速查找与插入。

一般来说，如果要做到严格 O(\log{n})，上层结点个数应是下层结点个数的 \dfrac12。但是这样实现会把代码变得十分复杂，就失去了它在 OI 中使用的意义。

此外，我们在实现时，一般在插入时就确定数值的层数，而且层数不能简单的用随机数，而是每次以 \dfrac12 或 \dfrac14 的概率逐渐增长。
就像这样：

inline int rand_level()
{
    int ret = 1;
    while(rand() % 2 && ret < MAX_LEVEL)
        ++ret;
    return ret;
}

其中 \texttt{MAX\_LEVEL} 是我们指定的一个层数上限，如果使用非指针版，定义这样一个常量会方便许多，更能节省空间。如果是指针版，可以不加限制地任由它增长。

我们来看看存储结点的结构体：

struct node
{
    int key,value;
    int next[MAX_LEVEL + 5];
} sl[N + 10];//N 为常量。

next[i] 表示这个结点在第 i 层的下一个结点编号。

我们初始化时，应定义两个虚拟结点 head,tail，表示链表头与链表尾，其实 tail 可以省去，但是为了易于理解，我没有去掉。

笔者个人有一个癖好：就是用一个栈或是队列保存已经被删除的节点，模拟一个内存池，可以节省很多空间，使空间在 O(n \cdot \texttt{MAX\_LEVEL}) 级。

分配新结点：

inline void new_node(int &p,int key,int value = 0)
{
    if(top)
        p = st[top--];
    else
        p = ++node_tot;
    sl[p].key = key;
    sl[p].value = value;
}

回收结点：

inline void free_node(int p)
{
    st[++top] = p;
}

初始化：

inline void init()
{
    new_node(head,-INF),new_node(tail,INF);
    for(register int i = 1;i <= MAX_LEVEL;++i)
        sl[head].next[i] = tail;
}

按照定义，链表头尾应分别为负与正无穷。但是有时候是不需要的，不过为避免某些锅还是打上的好。

考虑在一个已经建好的跳表中查找一个值 key，我们应从最高层开始查找，逐渐往下：

int find(int key)
{
    int p = head;
    for(register int i = MAX_LEVEL;i;--i)
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
    return sl[p].next[1];
}

注意这个代码并没有判断不存在这个元素的情况。

插入操作的思路是，同样从顶层开始，逐层找到每层需要插入的位置，再生成层数并插入：

void insert(int key,int value)
{
    int p = head;
    int update[MAX_LEVEL + 5];
    int k = rand_level();
    for(register int i = MAX_LEVEL;i;--i)
    {
        while(sl[p].next[i] != tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
        update[i] = p;
    }
    int temp;
    new_node(temp,key,value);
    for(register int i = k;i;--i)
    {
        sl[temp].next[i] = sl[update[i]].next[i];
        sl[update[i]].next[i] = temp;
    }
}

删除操作几乎与插入对称：

void erase(int key)
{
    int p = head;
    int update[MAX_LEVEL + 5];
    for(register int i = MAX_LEVEL;i;--i)
    {
        while(sl[p].next[i] != tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
        update[i] = p;
    }
    free_node(sl[p].next[1]);
    for(register int i = MAX_LEVEL;i;--i)
    {
        if(sl[sl[update[i]].next[i]].key == key)
            sl[update[i]].next[i] = sl[sl[update[i]].next[i]].next[i];
    }
}

实战

先来看道水题：CodeVS 1230。

给出 n 个正整数，然后有 m 个询问，每个询问一个整数，询问该整数是否在 n 个正整数中出现过。

虽然是 Hash 入门题，但是 set 可过。所以我们也可以尝试用跳表来写。

代码：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int MAX_LEVEL = 25;
struct node
{
    int key;
    int next[MAX_LEVEL + 5];
} sl[N + 10];
int node_tot,head,tail;
int st[N + 10],top;
inline int rand_level()
{
    int ret = 1;
    while(rand() % 2 && ret <= MAX_LEVEL)
        ++ret;
    return ret;
}
inline void new_node(int &p,int key = 0)
{
    if(top)
        p = st[top--];
    else
        p = ++node_tot;
    sl[p].key = key;
}
inline void free_node(int p)
{
    st[++top] = p;
}
inline void init()
{
    new_node(head),new_node(tail);
    for(register int i = 1;i <= MAX_LEVEL;++i)
        sl[head].next[i] = tail;
}
void insert(int key)
{
    int p = head;
    int update[MAX_LEVEL + 5];
    int k = rand_level();
    for(register int i = MAX_LEVEL;i;--i)
    {
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
        update[i] = p;
    }
    int temp;
    new_node(temp,key);
    for(register int i = k;i;--i)
    {
        sl[temp].next[i] = sl[update[i]].next[i];
        sl[update[i]].next[i] = temp;
    }
}
bool find(int key)
{
    int p = head;
    for(register int i = MAX_LEVEL;i;--i)
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
    if(sl[sl[p].next[1]].key == key)
        return 1;//找到了
    return 0;//没找到
}
int n,m;
int main()
{
    srand(19260817);
    scanf("%d%d",&n,&m);
    int x;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&x),insert(x);
    while(m--)
        scanf("%d",&x),puts(find(x) ? "YES" : "NO");
}

好，现在来看道蓝题：P2286。

此题的思路就是，每次找它的前驱与后继中与它差更小的那个。

但是有一个细节：就是要区分人与宠物。所以在其为空的时候我们记录第一个插入的值的类型，此后遇到同类型的就插入，否则就进行领养操作。

set 版代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <algorithm>
using namespace std;
const int mod = 1e6;
int n,ans;
int type;
set<int> d;
inline void answer(int x)
{
    auto l = --d.lower_bound(x);
    auto r = d.lower_bound(x);
    if(x - *l <= *r - x && *l ^ -0x3f3f3f3f)
    {
        ans = (ans + x - *l) % mod;
        d.erase(l);
    }
    else 
    {
        ans = (ans + *r - x) % mod;
        d.erase(r);
    }
}
int main()
{
    d.insert(0x3f3f3f3f),d.insert(-0x3f3f3f3f);
    int x,y;
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d%d",&x,&y);
        if(d.size() == 2)
            type = x,d.insert(y);
        else if(x == type)
            d.insert(y);
        else
            answer(y);
    }
    printf("%d\n",ans);
}

我们考虑转换为跳表版。但是此时我们还需要维护跳表的结点个数。这个很简单，只需要在新建结点时顺便 ++，回收内存时 --。或者是在插入删除时处理也可。
以及 lower_bound 函数，由于我们存储的不是双向链表，模拟对 set 的迭代器 -- 的操作有两个方法：

最终代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int mod = 1e6;
int n,ans;
int type;
const int MAX_LEVEL = 30;
struct node
{
    int key;
    int next[MAX_LEVEL + 5];
} sl[N + 10];
int node_tot,head,tail,size;
int st[N + 10],top;
inline int rand_level()
{
    int ret = 1;
    while(rand() % 2 && ret < MAX_LEVEL)
        ++ret;
    return ret;
}
inline void new_node(int &p,int key = 0)
{
    if(top)
        p = st[top--];
    else
        p = ++node_tot;
    sl[p].key = key;
    ++size;
}
inline void free_node(int p)
{
    st[++top] = p;
    --size;
}
inline void init()
{
    new_node(head,-0x3f3f3f3f),new_node(tail,0x3f3f3f3f);
    for(register int i = 1;i <= MAX_LEVEL;++i)
        sl[head].next[i] = tail;
}
void insert(int key)
{
    int p = head;
    int update[MAX_LEVEL + 5];
    int k = rand_level();
    for(register int i = MAX_LEVEL;i;--i)
    {
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
        update[i] = p;
    }
    int temp;
    new_node(temp,key);
    for(register int i = k;i;--i)
    {
        sl[temp].next[i] = sl[update[i]].next[i];
        sl[update[i]].next[i] = temp;
    }
}
void erase(int key)
{
    int p = head;
    int update[MAX_LEVEL + 5];
    for(register int i = MAX_LEVEL;i;--i)
    {
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
        update[i] = p;
    }
    free_node(sl[p].next[1]);
    for(register int i = MAX_LEVEL;i;--i)
        if(sl[sl[update[i]].next[i]].key == key)
            sl[update[i]].next[i] = sl[sl[update[i]].next[i]].next[i];
}
int lb(int key)
{
    int p = head;
    for(register int i = MAX_LEVEL;i;--i)
        while(sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key)
            p = sl[p].next[i];
    return p;//相当于对 lower_bound 的结果进行 --
}
inline void answer(int x)
{
    int l = lb(x);
    int r = sl[l].next[1];//相当于对迭代器 ++
    if(sl[l].key ^ -0x3f3f3f3f && x - sl[l].key <= sl[r].key - x)
    {
        ans = (ans + x - sl[l].key) % mod;
        erase(sl[l].key);
    }
    else
    {
        ans = (ans + sl[r].key - x) % mod;
        erase(sl[r].key);
    }
}
int main()
{
    srand(19260817);
    init();
    int x,y;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&x,&y);
        if(size == 2)
            type = x,insert(y);
        else if(x == type)
            insert(y);
        else
            answer(y);
    }
    printf("%d\n",ans);
}

拓展

考虑在跳表的每一个结点上，维护同一层内该结点与后一个结点差了多少个数，这样就可以维护一棵名次树了。
然鹅笔者太鸽就不写了，不如去写平衡树。

参考资料