跳表

  |  

摘要: 跳表的设计与实现

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


$0 跳表

背景

与哈希表、平衡树、Trie类似,跳表也可以看成是一种自带索引的数据结构(索引结构)。即根据给定的 key,可以快速查到它所在节点的位置。哈希表,平衡树,Trie 也都有这种根据 key 快速找到节点位置的特性。

作为对比,数组,链表就没有这种根据 key 快速找到其所在节点的特性,只能线性扫描去找。(栈,队列,堆这三种数据结构,节点的组织方式依然是数组或链表,本质不变)。

数组和链表都可以通过借助索引结构给节点建立索引的方式,实现给定 key 快速找到对应节点的需求。建立索引时候,最常用的索引结构是哈希表(哈希索引),平衡树(树形索引)。

跳表可以理解为用多层的链表给链表建了多层的索引,其中最底层的链表是存 key 的数据结构,其余各层链表是给底层链表的 key 提供索引的索引结构,这种索引方式比较特殊,不好归类,所以它自己单独算一类索引。

原理

对于树形索引,如果使用 BST,当遇到相对有序的输入时,树将变得很深,退化成链表。为例解决这个问题,出现了平衡树的各种强制平衡的算法,并且有很好的性能。

跳表是平衡树的一种代替,相当于我知道如果不做强制平衡,BST 最终会退化成链表。那我一开始就让你退化成链表,这样我也不用费劲做强制平衡了,取而代之地,用随机数来提供一种概率性的平衡。

在最坏情况下跳表的性能会很差,但是最坏情况从概率上讲极难达到,并且由于用了随机数,无法举出可以达到最坏情况的数据。这一点和随机化快排一样。

跳表的优势

作为替代,跳表相比平衡树的优势:

  • 实现简单
  • 时间复杂度相同,但是常数更小
  • 空间性能更好

算法

理想跳表

跳表的数据量为 n。第一层跳表就是一个将这 n 个数据连接起来的单链表,每个节点有数据字段记录 key 和一个前向指针指向下一个节点。

第 2 层,它的前向指针指向它往后数两个节点。这样的话第二层最多有 $\lceil n/2 \rceil + 1$ 个节点。

每提高一层,该层的前向指针前进的节点数均为前一层前进节点数的二倍,节点数为前一层的一半。

为了表示这种层数信息,可以在链表节点上加一个 level 字段,表示该节点的层数,最底层为 level = 1。如果节点的 level 等于 2,则该节点有两个前向指针,第一个为指向下一节点的指针,另一个是指向往后数 2 个节点的指针。

类似地,如果节点的 level 等于 i,则该节点有 i 个前向指针,分别指向从该点往前数 $2^{0}, 2^{1}, …, 2^{i-1}$ 个节点。类似于倍增法的思想。

节点定义

1
2
3
4
5
6
7
8
9
10
11
struct SLNode
{
int key;
int level;
vector<SLNode*> forwards;
SLNode(int k, int l):key(k),level(l)
{
forwards = vector<SLNode*>(level);
}
SLNode(){}
};

节点定义是按照理想跳表来的。level 表示节点所属层级,持有的前向指针数量就是层级数。

对于理想跳表,最底层链表中各个节点的位置决定了它的层级,在创建节点的时候就可以明确算出来,这个层级可以随机地取,引入随机因素。

当节点层级随机取的时候,对于层级 i,其第 i 层前向指针 forwords[i - 1] 不一定要往前数 $2^{i-1}$ 个节点,而是指向 i 之后的任意节点,具体是哪个取决于随机因素。

初始化

创建虚拟头结点 head,持有所有层级的前向指针,并都置为 nullptr; 此时链表为空。

取最大层级 MAX_LEVEL 为 $log_{1/P}N$,其中 P 为创建节点分配层级时向上爬升层级的概率,N 为数据量。

例如当数据量为 $2^{16}$,p 等于 1/2,MAX_LEVEL 取 16 比较合适。

初始化随机数引擎 dre 和分布 dr

1
2
3
4
5
6
7
8
MySkiplist(int max_level, double p) {
MAX_LEVEL = max_level;
P = p;
head = new SLNode(-1, MAX_LEVEL);
int seed = rand();
dre = std::default_random_engine(seed);
dr = std::uniform_real_distribution<double>(0.0, 1.0);
}

随机取层级

插入新节点是,需要在一定范围内([1, MAX_LEVEL])随机给一个该节点的层级。

初始层级为 1,然后给定一个概率 P,在当前层级,都可以 P 概率向上爬,直到某一层向上爬失败返回。这样给出的层级是与节点个数无关的

这里的 PMAX_LEVEL 均为初始化跳表时指定的。

1
2
3
4
5
6
7
int get_random_level()
{
int level = 1;
while(this -> dr(this -> dre) < this -> P && level < this -> MAX_LEVEL)
++level;
return level;
}

查找 bool search(int target)

从最左节点的开始,不断向右前进,前进时优先走层级较高的前向指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool search(int target) {
SLNode *iter = head;
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
--level;
}
// 此时 iter 为小于 target 的最大的节点
if(!(iter -> forwards)[0])
return false;
iter = (iter -> forwards)[0];
if(iter -> key == target)
return true;
else
return false;
}

插入 void add(int target)

先对 target 走一遍搜索过程,小于 target 的最大的节点,在该节点后面插入新节点。

搜索过程记录一个指针数组 updateupdate[i] := 搜索路径中第 i 层的最右节点

插入的节点层级为 level,在底层插入节点,然后向上逐层更新指针,直至第 level 层更新完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void add(int target) {
SLNode *iter = head;
vector<SLNode*> update(MAX_LEVEL);
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
update[level] = iter;
--level;
}
// 此时 iter 为小于 target 的最大的节点
int new_level = get_random_level();
SLNode *node = new SLNode(target, new_level);
for(int l = 0; l < new_level; ++l)
{
(node -> forwards)[l] = (update[l] -> forwards)[l];
(update[l] -> forwards)[l] = node;
}
}

删除 bool erase(int target)

先对 target 走一遍搜索过程,小于 target 的最大的节点,在该节点后面插入新节点。

搜索过程记录一个指针数组 updateupdate[i] := 搜索路径中第 i 层的最右节点

以上过程与插入一样。

如果 iter 在最底层的下一节点为空或者大于 target,说明没有 target,直接返回 false。

否则删除该节点,然后自底向上更新各个层级的指针。

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
26
27
bool erase(int target) {
SLNode *iter = head;
vector<SLNode*> update(MAX_LEVEL);
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
update[level] = iter;
--level;
}
// 此时 iter 为小于 target 的最大的节点
if(!(iter -> forwards)[0])
return false;
if((iter -> forwards)[0] -> key != target)
return false;
int new_level = (iter -> forwards)[0] -> level;
SLNode *tmp = (iter -> forwards)[0];
for(int l = 0; l < new_level; ++l)
{
(update[l] -> forwards)[l] = (tmp -> forwards)[l];
(tmp -> forwards)[l] = nullptr;
}
delete tmp;
tmp = nullptr;
return true;
}

算法分析

参考论文原文。

完整代码 (模板)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
struct SLNode
{
int key;
int level;
vector<SLNode*> forwards;
SLNode(int k, int l):key(k),level(l)
{
forwards = vector<SLNode*>(level);
}
SLNode(){}
};

class MySkiplist {
public:
MySkiplist(int max_level, double p) {
MAX_LEVEL = max_level;
P = p;
head = new SLNode(-1, MAX_LEVEL);
int seed = rand();
dre = std::default_random_engine(seed);
dr = std::uniform_real_distribution<double>(0.0, 1.0);
}

~MySkiplist()
{
SLNode *iter = head;
while(iter)
{
SLNode *tmp = iter;
iter = (iter -> forwards)[0];
delete tmp;
tmp = nullptr;
}
head = nullptr;
}

bool search(int target) {
SLNode *iter = head;
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
--level;
}
// 此时 iter 为小于 target 的最大的节点
if(!(iter -> forwards)[0])
return false;
iter = (iter -> forwards)[0];
if(iter -> key == target)
return true;
else
return false;
}

void add(int target) {
SLNode *iter = head;
vector<SLNode*> update(MAX_LEVEL);
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
update[level] = iter;
--level;
}
// 此时 iter 为小于 target 的最大的节点
int new_level = get_random_level();
SLNode *node = new SLNode(target, new_level);
for(int l = 0; l < new_level; ++l)
{
(node -> forwards)[l] = (update[l] -> forwards)[l];
(update[l] -> forwards)[l] = node;
}
}

bool erase(int target) {
SLNode *iter = head;
vector<SLNode*> update(MAX_LEVEL);
int level = MAX_LEVEL - 1;
while(level >= 0)
{
while((iter -> forwards)[level] && (iter -> forwards)[level] -> key < target)
iter = (iter -> forwards)[level];
update[level] = iter;
--level;
}
// 此时 iter 为小于 target 的最大的节点
if(!(iter -> forwards)[0])
return false;
if((iter -> forwards)[0] -> key != target)
return false;
int new_level = (iter -> forwards)[0] -> level;
SLNode *tmp = (iter -> forwards)[0];
for(int l = 0; l < new_level; ++l)
{
(update[l] -> forwards)[l] = (tmp -> forwards)[l];
(tmp -> forwards)[l] = nullptr;
}
delete tmp;
tmp = nullptr;
return true;
}

private:
SLNode *head;
int MAX_LEVEL;
double P;
std::default_random_engine dre;
std::uniform_real_distribution<double> dr;

int get_random_level()
{
int level = 1;
while(dr(dre) < P && level < MAX_LEVEL)
++level;
return level;
}
};

题目与代码测试:1206. 设计跳表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Skiplist {
public:
Skiplist() {
skiplist = new MySkiplist(15, 0.5);
}

bool search(int target) {
bool ans = skiplist -> search(target);
return ans;
}

void add(int num) {
skiplist -> add(num);
}

bool erase(int num) {
bool ans = skiplist -> erase(num);
return ans;
}

private:
MySkiplist *skiplist;
};

$2 Follow up

以上的分析和代码是对跳表原始论文的复现。进阶版的有两种主流的企业级的实现, Redis 的 zset 和 JDK 的 ConcurrentSkipListMap

$3 论文原文

《Skip Lists: A Probabilistic Alternative to Balanced Trees》

skiplist


Share