深夜学算法之SkipList：让链表飞
1. 前言
上次写Python操作LevelDB时提到过，有机会要实现下SkipList。摘录下wiki介绍：
跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟二叉查找树。
我们知道对于有序链表，查找的时间复杂度为O(n)，尽管真正的插入与删除操作节点复杂度只有O(1)，但都需要先查找到节点的位置，可以说是查找拉低了有序链表的性能。
简单地讲，SkipList采用“空间换时间”的思想，除了原始链表外还保存一些“跳跃”的链表，达到加速查找的效果。
我的实现：https://github.com/liquidconv/DSAF
2. 感性认识SkipList
bottom-up与top-down，我个人倾向后者。所以在给出SkipList里具体定义与算法前，先从问题出发，研究一下SkipList的设计思路。
来看一个有序链表(这里H表示链表头部，T表示链表尾部，不是有效节点)：
1.png
假设我们要查找7，只能老老实实地按照1->2->3->…的顺序走，忍受O(n)的效率；但如果是数组的话，可以使用二分查找达到O(lgn)。
可以在链表中使用二分查找吗？
不可以，因为二分查找需要用到中间位置的节点，而链表不能随机访问。
——那么就把中间位置的节点单独保存吧。
2.png
原来的链表写成了三个链表，记从下到上的编号为0、1、2，可以发现0号链表就是原始链表，1号链表是原始链表四等分点，2号链表是原始链表的二等分点。
我们再来查找7，初始搜索范围为(H, T)：
- 在2号链表中与4比较，7>4，更新搜索范围为(4, T)
- 在1号链表中与6比较，7>6，更新搜索范围为(6, T)
- 在0号链表中与7比较，7=7，查找成功。
形象化地说，SkipList就是额外保存了二分查找的中间信息。不过SkipList中含有随机化，生成的结构不会像上面那样完美，来看实际生成的一个SkipList：
3.png
之后会详细讨论随机化的问题，现在先承上启下地梳理下信息：
- SkipList结合了链表和二分查找的思想
- 将原始链表和一些通过“跳跃”生成的链表组成层
- 第0层是原始链表，越上层“跳跃”的步距越大，链表元素越少
- 上层链表是下层链表的子序列
- 查找时从顶层向下，不断缩小搜索范围
最后，可以利用“链”的性质，减少存储空间：
4.png
3. 实现SkipList
这里写的SkipList是非常naive的，有许多可优化之处。
3.1 定义
首先定义SkipList中的节点：
typedef struct SkipListNode {
int key;
void *data;
int level;
SkipListNode **next_nodes;
} SkipListNode;key是键，data是值，与标准链表中的节点一样；区别在“链”的部分，level表示节点在第几层中，next_nodes是每层上的后继节点——比如上面那个例子里的节点4，在第2层是T，在第1层是6，在第0层是5。
然后来定义SkipList：
class SkipList {
public:
SkipList(int max_level);
~SkipList(void);
void insertNode(int key, void *data);
void deleteNode(int key);
void *getData(int key);
void displayList(void);
private:
int MAX_LEVEL;
int RandomLevel(void);
SkipListNode *head;
SkipListNode *tail;
};接口的含义还是很清楚的。构造SkipList时给定最大层数(其实是可以让层数动态增长的)，displayList用于打印整个SkipList。
这里假设key是不重复的，所以insertNode实现了插入与修改，deleteNode实现了删除，getData实现了查找。
3.2 构造与析构
首先来看构造函数SkipList(int max_level)：
SkipList::SkipList(int max_level) {
MAX_LEVEL = max_level > 0? max_level : 1;
head = new SkipListNode;
tail = new SkipListNode;
head->next_nodes = new SkipListNode *[MAX_LEVEL];
for(int i = 0; i < MAX_LEVEL; ++i)
head->next_nodes[i] = tail;
}首先确定SkipList的最大层数MAX_LEVEL，然后生成head与tail节点，head节点显然必须是一个MAX_LEVEL层的节点，让head在每一层上的后继节点都是tail。
用图片来表示SkipLsit(3)的话，就是：
5.png
析构函数~SkipList(void)也很简单：
SkipList::~SkipList(void) {
SkipListNode *curr = nullptr;
while(head->next_nodes[0] != tail) {
curr = head->next_nodes[0];
head->next_nodes[0] = curr->next_nodes[0];
delete curr->next_nodes;
delete curr;
}
delete head->next_nodes;
delete head;
delete tail;
}第0层的链表是原始链表，上层链表的节点都来自第0层，所以可以利用这个性质，沿着第0层链表释放节点，注意除了释放SkipListNode还要释放里面的next_nodes。
3.3 插入、删除与查找
SkipList的插入、删除与查找一脉相承，理解插入后删除与查找都很简单。但在给出插入算法的代码前，先让我们想想insertNode里需要做哪些工作：
- 标准有序链表插入前需要定位，通常是确定新节点的前驱节点；SkipList中一个节点至多是MAX_LEVEL层的，需要插入到MAX_LEVEL个有序链表里，所以要确定每层的前驱节点
- 构造新节点，生成小于MAX_LEVEL的随机数k，作为新节点的层数
- 将新节点插入到第0层到第(k-1)层的链表中
概括起来还是三步走：找前驱，做节点，插入链表。
第一步，找前驱：
SkipListNode *update[MAX_LEVEL];
SkipListNode *curr = head;
for(int i = MAX_LEVEL - 1; i >= 0; --i) {
if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)
update[i] = curr;
else {
while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)
curr = curr->next_nodes[i];
update[i] = curr;
}
}update是前驱节点数组，curr用来迭代，初始值为head。for循环的大结构是自顶向下遍历每层，找到该层上新节点的前驱节点。
重点在于if-else结构，我们来看第i层。curr只有后继节点不是tail，而且curr第i层后继节点的key比新节点key小的时候才会更新，所以curr满足性质：
curr的后继节点是tail，或者curr->key比key小。
假如curr的后继节点是tail，或者curr的key比新节点的key小，curr的后继节点比新节点的key大的话，新节点的插入位置都正好在curr后面，也就是curr是新节点在第i层的前驱节点。
否则就需要在第i层链表上向后移动curr，直到curr的后继节点是tail，或者curr的后继节点的key大于新节点的key，也就是回到之前的情形。
假设要在下面的SkipList里插入5，来看update数组的计算过程：
6.png
- i = 2 curr进入循环时为head，第1层后继节点为curr->next_nodes[2] curr->next_nodes[2]不是tail，而且key = 4 < 5 进入else部分，更新curr为4号节点 update[2] = 4号节点
- i = 1，搜索范围为(4, tail) curr进入循环时为4号节点，第1层后继节点为curr->next_nodes[1] curr->next_nodes[1]不是tail但key = 6 > 5 进入if部分，不更新curr update[1] = 4号节点
- i = 0，搜索范围为(4, 6) curr进入循环时为4号节点，后继节点为6号节点 进入if部分，不更新curr update[0] = 4号节点
继续之前搜索范围的说法，搜索的过程可以看做搜索范围（curr, curr->next_nodes[i]）的收紧。初始时为(head, tail)，每层的while循环里收紧下界，curr递增，在逐层下降的for循环里收紧上界，curr->next_nodes[i]递减。
这里为了清晰删除了保证key不重复的代码，后面有完整版。
第二步，做节点
int level = RandomLevel();
SkipListNode *temp = new SkipListNode;
temp->key = key;
temp->data = data;
temp->level = level;
temp->next_nodes = new SkipListNode *[level + 1];内容非常简单，RandomLevel()之后讨论随机化时再说，总之就是产生一个0到MAX_LEVEL - 1之间的随机数。唯一的坑就是生成next_nodes是要用（level+1）而不是level，考虑level = 0的情形就明白了。
第三步，插入链表
for(int i = 0; i <= level; ++i) {
temp->next_nodes[i] = update[i]->next_nodes[i];
update[i]->next_nodes[i] = temp;
}来看完整的insertNode(int key, void *data):
void SkipList::insertNode(int key, void *data) {
SkipListNode *update[MAX_LEVEL];
SkipListNode *curr = head;
// 寻找每一层上待插入节点之前的节点
for(int i = MAX_LEVEL - 1; i >= 0; --i) {
if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)
update[i] = curr;
else {
while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)
curr = curr->next_nodes[i];
if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key) {
curr->next_nodes[i]->data = data;
return;
}
update[i] = curr;
}
}
// 生成待插入节点
int level = RandomLevel();
SkipListNode *temp = new SkipListNode;
temp->key = key;
temp->data = data;
temp->level = level;
temp->next_nodes = new SkipListNode *[level + 1];
// 在每层上的链表中插入节点
for(int i = 0; i <= level; ++i) {
temp->next_nodes[i] = update[i]->next_nodes[i];
update[i]->next_nodes[i] = temp;
}
}删除与插入完全是对称的，直接来看代码：
void SkipList::deleteNode(int key) {
SkipListNode *update[MAX_LEVEL];
SkipListNode *curr = head;
// 寻找每一层上待删除节点之前的节点
for(int i = MAX_LEVEL - 1; i >= 0; --i) {
if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)
update[i] = nullptr;
else {
while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)
curr = curr->next_nodes[i];
if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key)
update[i] = curr;
else
update[i] = nullptr;
}
}
SkipListNode *temp = nullptr;
// 在每层上的链表中删除节点
for(int i = 0; i < MAX_LEVEL; ++i) {
if(update[i]) {
temp = update[i]->next_nodes[i];
update[i]->next_nodes[i] = temp->next_nodes[i];
}
}
// 最终释放节点
if(temp) {
delete temp->next_nodes;
delete temp;
}
}同样先查找前驱数组，由于节点不一定在某层中出现，找不到时就把前驱节点标记为nullptr，在该节点出现的层的链表里删除该节点，最终释放节点。
查找就更加简单了，从上到下遍历，找到就返回：
void *SkipList::getData(int key) {
SkipListNode* curr = head;
for(int i = MAX_LEVEL - 1; i >= 0; --i) {
if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)
continue;
else {
while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)
curr = curr->next_nodes[i];
if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key)
return curr->next_nodes[i]->data;
}
}
return nullptr;
}3.4 随机化
SkipList是一种概率算法，非常依赖于生成的随机数。这里不能用rand() % MAX_LEVEL的简单做法，而要用满足p=1/2几何分布的随机数。
来看RandomLevel()的代码：
int SkipList::RandomLevel(void) {
int level = 0;
while(rand() % 2 && level < MAX_LEVEL - 1)
++level;
return level;
}这里不做太多的数学分析，只做直观解释。考虑MAX_LEVEL = 4的情形，可能的返回值为0、1、2、3，显然出现概率分别为：
P(0) = (1/2)^0 * (1/2) = 1/2 P(1) = (1/2)^1 * (1/2) = 1/4 P(2) = (1/2)^2 * (1/2) = 1/8 P(3) = 1 - P(0) - P(1) - P(2) = 1/8
假设有16个元素的话，可以预计第0层有16个元素，第1层约有16 - 8 = 8个元素，第2层约有16 - 8 - 4 = 4个元素，第3层约有16 - 8 -4 -2 = 2个元素，从底向上每层元素数量大约减少一半。
SkipList层数合适时自顶向下搜索，理想情况下每下降一层，搜索范围减小一半，达到类似二分查找的效果，效率为O(lgn)；最坏情况下也只是curr从head移动到tail，效率为O(n)。
我的实现里最大层数是通过MAX_LEVEL静态指定的，也可以让最大层数动态增长——RandomLevel里不设置最大值，插入节点时得到的level比当前SkipList层数大时就在顶上再加一层，删除节点时如果只有这个节点在高层就去掉高层。
4. 参考资料
- Skip list： https://en.wikipedia.org/wiki/Skip_list
- skiplist 跳表详解及其编程实现 http://www.tuicool.com/articles/J7rQRb