skiplist跳跃表

基本情况

  • 对于有序链表,查找、插入、删除的时间复杂度皆为O(n),不适用于频繁的上述操作
  • 其他适合于上述操作的数据结构各有优劣,比如平衡二叉查找树,比较花费空间,但查询效率可以保证
  • 跳跃表实现比较简单,结合随机特性,可以保证查找、插入与删除的操作的平均时间复杂度低于O(n)

跳跃表的结点

  • 每个结点包含键(key)与值(value)
  • 每个结点可包含多个指向其他结点的指针,至少包含一个,至多包含n个,n为跳跃表的最大层数

跳跃表的结构

  • 除了普通结点之外,还包含头结点和尾结点,并且跳跃表的总层数为n
  • 每一层都包含头尾结点
  • 如果结点位于第k层,那么它必定位于第k-1层,第k-1层的结点数必定不少于第k层
  • 每个结点均位于第1层,后面每一层的结点数越来越少,但是除了首尾结点之外,其他结点必定保持有序
  • 跳跃表包含随机性,随机性指的是每个结点所在的层数是在它被加入跳跃表时随机生成的,这个特性可用于保证各个操作的平均时间复杂度低于O(n)

跳跃表主要操作及复杂度分析

插入操作

过程描述

  1. 设置当前结点为头结点,当前层数为第n层
  2. 随机生成一个整数k,满足1<=k<=n,表示即将插入的结点所在的总层数
  3. 对比要插入的key与当前结点的下一结点的key(指当前的层的下一个结点,下同),如果比下一结点的key小,则转步骤4,如果比下一结点的key大,则转步骤5,如果等于下一结点的key,说明该key已存在,直接替换下一结点的value并结束本次操作
  4. 接步骤3,说明要插入的位置必定在当前结点与下一结点之间,如果k大于等于当前层数,则记录当前结点,最后插入新结点的时候需要用到该信息,如果当前层数不是第1层,那么当前层数减1,返回步骤3继续,否则转步骤6
  5. 接步骤3,说明要插入的位置必定在下一结点之后,因此将当前结点指向下一结点,返回步骤3继续
  6. 将当前结点加入第1-k层,每一层插入的位置已在步骤4中记录,操作结束

复杂度分析

  1. 最坏情况下,每一层都包含所有结点,那么如果要插入的位置是尾结点之前,则时间复杂度是O(n)
  2. 由于每个点的层数的随机性,假设完全随机分布,那么大致可以这样理解:第1层包含n个结点,每个结点有50%的概率出现在第2层,则第2层可能的结点数是n/2,第n层可能的结点数是第n-1层的一半
  3. 查找位置的过程中,层数越大,则每次比较之后跳过的结点数越多,平均下来看,最终执行插入操作之前遍历的结点数肯定小于总的结点数,而插入结点所需要变动指针的层数k的期望值是n/2,因此总的复杂度必定低于O(n)

查找操作

过程描述

  1. 设置当前结点为头结点,当前层数为第n层
  2. 对比要查找的key与当前结点的下一结点的key,如果比下一结点的key小,则转步骤4,如果比下一结点的key大,则转步骤4,如果等于下一结点的key,直接返回下一结点的value并结束本次操作
  3. 接步骤2,说明要查找的key的位置必定在当前结点与下一结点之间,如果当前层数不是第1层,那么当前层数减1,返回步骤3继续,否则说明该key不存在跳跃表中,返回对应信息
  4. 接步骤2,说明要查找的key的位置必定在下一结点之后,因此将当前结点指向下一结点,返回步骤2继续

复杂度分析

  • 查找过程的操作与插入过程类似,只是不需要变更跳跃表的结点指针,因此其复杂度一样低于O(n)

删除操作

过程描述

  1. 设置当前结点为头结点,当前层数为第n层
  2. 对比要插入的key与当前结点的下一结点的key,如果比下一结点的key小,则转步骤3,如果比下一结点的key大,则转步骤4,如果等于下一结点的key,则将当前结点在本层的指针指向下一结点的下一结点
  3. 接步骤2,说明要删除的位置必定在当前结点与下一结点之间,如果当前层数不是第1层,那么当前层数减1,返回步骤2继续,否则结束本次操作
  4. 接步骤2,说明要删除的位置必定在下一结点之后,因此将当前结点指向下一结点,返回步骤2继续
  5. 如果需要手动释放结点占用的空间或返回被删除的结点的value,则需要在步骤2记录对应的结点,并在遍历结束之后删除它

复杂度分析

  • 删除过程与插入过程类似,只是把对应的指针操作相反,其复杂度一样低于O(n)

跳跃表的python实现

结点类

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
"""
结点类
"""
class Node(object):
# 构造函数
def __init__(self, key, value):
if type(key) != KEY_TYPE:
raise TypeError
self.key = key
self.value = value
self.forwardNodes = {}
self.numForward = 0
# 设置某一层的前向结点
def setForwardNode(self, level, node):
if not isinstance(node, Node):
raise TypeError
if type(level) != int:
raise TypeError
if level < 0:
raise ValueError
self.forwardNodes[level] = node
self.numForward = len(self.forwardNodes)
# 获取某一层的前向结点
def getForwardNode(self, level):
if type(level) != int:
raise TypeError
if level < 0:
raise ValueError
if level not in self.forwardNodes.keys():
raise KeyError
return self.forwardNodes[level]
# 打印结点信息
def dump(self):
print('key: %s' % str(self.key))
print('value: %s' % str(self.value))
print('forward nodes: %s' % str(self.forwardNodes))
print('num forward: %s' % str(self.numForward))
# 获取前向结点数
def numForward(self):
return self.numForward
# 获取结点的键
def getKey(self):
return self.key
# 获取结点的值
def getValue(self):
return self.value
# 设置结点的值
def setValue(self, value):
self.value = value

跳跃表类

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
"""
跳跃表类
"""
class SkipList(object):
# 构造函数
def __init__(self, level = MAX_LEVEL):
if type(level) != int:
print(type(level))
raise TypeError
if level < 1:
raise ValueError
self.level = int(level)
self.nil = Node(-1, -1)
self.head = Node(0, 0)
for i in xrange(self.level):
self.head.setForwardNode(i + 1, self.nil)
# 插入结点时获取随机层数
def genRandomLevel(self):
return random.randint(1, self.level)
# 插入新的结点
def insert(self, key, value):
node = Node(key, value)
tmpLevel = self.genRandomLevel()
tmpNode = self.head
backwardNodes = {}
while tmpLevel >= 1:
forwardNode = tmpNode.getForwardNode(tmpLevel)
if forwardNode == self.nil:
backwardNodes[tmpLevel] = tmpNode
tmpLevel -= 1
continue
if forwardNode.getKey() < key:
tmpNode = forwardNode
continue
elif forwardNode.getKey() > key:
backwardNodes[tmpLevel] = tmpNode
tmpLevel -= 1
continue
# 键已存在,直接替换结点的值即可
forwardNode.setValue(value)
return
for level in backwardNodes.keys():
node.setForwardNode(level, backwardNodes[level].getForwardNode(level))
backwardNodes[level].setForwardNode(level, node)
# 搜索某个键对应的值
def search(self, key):
if type(key) != KEY_TYPE:
raise TypeError
tmpLevel = self.level
tmpNode = self.head
while tmpLevel >= 1:
forwardNode = tmpNode.getForwardNode(tmpLevel)
if forwardNode == self.nil:
tmpLevel -= 1
continue
if forwardNode.getKey() < key:
tmpNode = forwardNode
continue
elif forwardNode.getKey() > key:
tmpLevel -= 1
continue
# 找到对应结点则直接返回它的值
return forwardNode.getValue()
# 找不到对应结点,返回None
return None
# 删除键对应的结点
def delete(self, key):
if type(key) != KEY_TYPE:
raise TypeError
tmpLevel = self.level
tmpNode = self.head
node = None
while tmpLevel >= 1:
forwardNode = tmpNode.getForwardNode(tmpLevel)
if forwardNode == self.nil:
tmpLevel -= 1
continue
if forwardNode.getKey() < key:
tmpNode = forwardNode
continue
elif forwardNode.getKey() > key:
tmpLevel -= 1
continue
# 结点在某一层存在指针,调整该层的指针
tmpNode.setForwardNode(tmpLevel, forwardNode.getForwardNode(tmpLevel))
node = forwardNode
value = forwardNode.getValue()
# 键对应的结点存在,则删除之,并返回它的值
if node is not None:
value = node.getValue()
del(node)
return value
# 找不到对应的结点,抛出异常
raise KeyError
# 打印跳跃表
def dump(self):
tmpLevel = self.level
tmpNode = self.head
line = ''
while tmpLevel >= 1:
forwardNode = tmpNode.getForwardNode(tmpLevel)
if forwardNode != self.nil:
line += '(%s, %s) -> ' % (forwardNode.getKey(), forwardNode.getValue())
tmpNode = forwardNode
continue
print('level %d: (head) -> %s (tail)' % (tmpLevel, line))
tmpNode = self.head
tmpLevel -= 1
line = ''
简单测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if __name__ == '__main__':
skipList = SkipList()
keys = list(range(0, 10))
for key in keys:
skipList.insert(key, key)
for key in keys:
skipList.insert(key, key)
skipList.dump()
print("delete 3:", skipList.delete(3))
skipList.dump()
print("delete 8:", skipList.delete(8))
skipList.dump()
keys = list(range(0, 11))
for key in keys:
print('search key %d' % key)
print(skipList.search(key))