跳表详解
跳表（Skip List） 是一种动态数据结构，最早由 William Pugh 于 1990 年提出。它通过在有序链表的基础上引入多级索引结构，使得在有序链表中可以快速进行查找、插入和删除操作。跳表的平均时间复杂度为 O(log n)，在最坏情况下为 O(n)。
1. 跳表结构
跳表的核心思想是通过建立多级“跳跃”索引来减少遍历节点的数量。我们可以把跳表想象成一个多层的链表结构：
- 最底层是一个普通的有序链表，保存所有元素。
- 第二层是对最底层链表的一部分节点建立的索引，索引跨度为 2。
- 第三层对第二层再建立索引，索引跨度为 4，以此类推。
这种多级索引结构使得查找、插入和删除操作都能够通过从上往下跳跃，逐步缩小查找范围。
2. 跳表的时间复杂度
-
查找：在每一层索引中，从左到右进行顺序查找，如果找到合适区间，再下降到下一层继续查找，最终找到目标元素。平均时间复杂度为
O(log n)。 - 插入：在找到插入位置后，按照一定概率，更新插入元素的多级索引。
- 删除：删除操作也是先找到目标元素，然后删除元素及其相关的索引。
3. 使用场景
跳表适用于以下场景：
- 动态有序集合：当需要快速地进行插入、删除和查找操作，并且数据需要保持有序时，跳表是非常好的选择。
-
分布式系统中的有序集合：比如 Redis 的
Sorted Set（有序集合）底层就使用了跳表，跳表能够为有序数据提供高效的插入、删除、和查找。 - 内存数据库、缓存：在内存数据库或缓存中，如果需要经常进行查找和范围查询操作，跳表的性能表现良好，且比树结构更简单。
4. 示例代码
下面是用 Python 实现的跳表结构，示例中包括跳表的插入、查找、删除功能：
import random
class Node:
def __init__(self, value=None, level=0):
self.value = value
self.forward = [None] * (level + 1) # 创建一个 forward 列表，表示该节点的“前进”指针
class SkipList:
MAX_LEVEL = 16 # 最大索引层数
P = 0.5 # 随机生成层数的概率
def __init__(self):
self.level = 0 # 当前的索引层数
self.header = Node(None, self.MAX_LEVEL) # 跳表的头节点
def random_level(self):
level = 0
while random.random() < self.P and level < self.MAX_LEVEL:
level += 1
return level
def insert(self, value):
update = [None] * (self.MAX_LEVEL + 1) # 记录每层的待插入位置
current = self.header
# 找到插入位置
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].value < value:
current = current.forward[i]
update[i] = current # 记录该层的最后一个小于待插入值的节点
# 插入新的节点
level = self.random_level() # 随机生成新节点的层数
if level > self.level:
for i in range(self.level + 1, level + 1):
update[i] = self.header # 新增层索引，指向头节点
self.level = level
new_node = Node(value, level)
for i in range(level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def search(self, value):
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].value < value:
current = current.forward[i]
current = current.forward[0]
if current and current.value == value:
return True
return False
def delete(self, value):
update = [None] * (self.MAX_LEVEL + 1)
current = self.header
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].value < value:
current = current.forward[i]
update[i] = current
current = current.forward[0]
if current and current.value == value:
for i in range(self.level + 1):
if update[i].forward[i] != current:
break
update[i].forward[i] = current.forward[i]
# 如果删除的是最大层节点，减少层数
while self.level > 0 and self.header.forward[self.level] is None:
self.level -= 1
# 测试跳表
if __name__ == "__main__":
skiplist = SkipList()
# 插入一些数据
for num in [3, 6, 7, 9, 12, 19, 17]:
skiplist.insert(num)
# 查找数据
print(skiplist.search(7)) # 输出 True
print(skiplist.search(15)) # 输出 False
# 删除数据
skiplist.delete(6)
print(skiplist.search(6)) # 输出 False
5. 总结
- 优点：跳表是一种易于实现的数据结构，平均性能与平衡树相当，但实现相对简单，并且在分布式系统中表现出色。
-
应用场景：跳表非常适合用于需要频繁查找和插入的有序数据场景，尤其是像 Redis 中的
Sorted Set这样的数据结构。
