浅谈玄学数据结构：跳表
Aleph1022
2018-10-20 11:19:29
## 前言
### 为啥 Redis 使用跳表而不是使用红黑树？
> 1. SkipList 的复杂度和红黑树一样，而且实现起来更简单。
>
> 2. 在并发环境下 SkipList 有另外一个优势，红黑树在插入和删除的时候可能需要做一些保持平衡的操作，这样的操作可能会涉及到整个树的其他部分，而 SkipList 的操作显然更加局部性一些，所以需要盯住的节点更少，因此在这样的情况下性能好一些。
上文引用自：[知乎 - 为啥 redis 使用跳表(skiplist)而不是使用 red-black？ - 于康的回答](https://www.zhihu.com/question/20202931/answer/16086538)
## 正文
如果你要在一个有序的序列中查找元素 $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$ 的概率逐渐增长。
就像这样：
```cpp
inline int rand_level()
{
int ret = 1;
while(rand() % 2 && ret < MAX_LEVEL)
++ret;
return ret;
}
```
其中 $\texttt{MAX\_LEVEL}$ 是我们指定的一个层数上限，如果使用非指针版，定义这样一个常量会方便许多，更能节省空间。如果是指针版，可以不加限制地任由它增长。
我们来看看存储结点的结构体：
```cpp
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})$ 级。
分配新结点：
```cpp
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;
}
```
回收结点：
```cpp
inline void free_node(int p)
{
st[++top] = p;
}
```
初始化：
```cpp
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$，我们应从最高层开始查找，逐渐往下：
```cpp
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];
}
```
注意这个代码并没有判断不存在这个元素的情况。
插入操作的思路是，同样从顶层开始，逐层找到每层需要插入的位置，再生成层数并插入：
```cpp
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;
}
}
```
删除操作几乎与插入对称：
```cpp
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](http://codevs.cn/problem/1230/)。
> 给出 $n$ 个正整数，然后有 $m$ 个询问，每个询问一个整数，询问该整数是否在 $n$ 个正整数中出现过。
虽然是 Hash 入门题，但是 set 可过。所以我们也可以尝试用跳表来写。
代码：
```cpp
#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](https://www.luogu.org/problemnew/show/P2286)。
此题的思路就是，每次找它的前驱与后继中与它差更小的那个。
但是有一个细节：就是要区分人与宠物。所以在其为空的时候我们记录第一个插入的值的类型，此后遇到同类型的就插入，否则就进行领养操作。
`set` 版代码：
```cpp
#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` 的迭代器 `--` 的操作有两个方法：
- 改成双向
- 查找时直接找 `--` 的结果
最终代码：
```cpp
#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);
}
```
## 拓展
考虑在跳表的每一个结点上，维护**同一层**内该结点与后一个结点差了多少个数，这样就可以维护一棵名次树了。
然鹅笔者太鸽就不写了，~~不如去写平衡树~~。
## 参考资料
- 任何能被百度到的跳表的资料。
- [hzwer.com - 「BZOJ1208」[HNOI2004] 宠物收养所](http://hzwer.com/1311.html)