什么是跳表
跳表（Skip List）是一种随机化的数据结构，基于并联的有序链表，其效率可比拟于二叉搜索树（如红黑树、AVL树等）。跳表的平均查找和插入时间复杂度都是O(log n)，但与平衡树相比，跳表的实现更为简单，且常数因子更小。
跳表是对有序链表的一种扩展，通过维护一系列分层的链表，并在每一层中跳过部分元素，从而加快查找速度。跳表上层的链表作为下层链表的\”快速通道\”，使得在查找时可以先在高层链表中进行大步跳跃，再在底层链表中进行精确定位。
为什么需要跳表
传统的有序链表虽然插入和删除操作比较方便（只需要修改指针），但查找操作需要从头开始遍历，时间复杂度为 O(n)。如果链表很长，查找效率会非常低。
平衡树（如 AVL 树、红黑树）可以实现 O(logn) 的查找、插入和删除，但它们的实现比较复杂，需要进行旋转等操作来维护树的平衡。
跳表提供了一种折衷方案：它在实现复杂度上接近链表，但在性能上接近平衡树。
基本原理
基本结构
跳表由多层链表组成，每一层都是一个有序链表，底层包含所有元素，而上层则是下层的子集。具体来说：
- 最底层（Level 0）是一个普通的有序链表，包含所有元素
- 第一层（Level 1）大约包含每两个元素中的一个
- 第二层（Level 2）大约包含每四个元素中的一个
- 依此类推，第i层大约包含每2^i个元素中的一个
节点结构
每个跳表节点包含：
- 值（key）：节点存储的实际数据
- 多个前向指针：指向同层的下一个节点
- 层数（level）：决定节点在哪些层出现
class SkipListNode:
def __init__(self, key, level):
self.key = key
# 创建前向指针数组，长度为level+1
self.forward = [None] * (level + 1)
class SkipList:
def __init__(self, max_level, p):
# 最大层数
self.MAX_LEVEL = max_level
# 用于随机层数的概率参数
self.P = p
# 当前跳表的层数
self.level = 0
# 头节点，key为-1
self.header = SkipListNode(–1, self.MAX_LEVEL)
跳表核心操作
随机层数生成
跳跳表使用类似于抛硬币的方式来决定一个新节点的层数：
这种随机层数生成机制的特点是：
- 每个节点至少在Level 0层出现
- 每一层上的节点数量大约是下一层的一半（当p=0.5时）
- 最底层包含所有节点，向上每层节点数量递减
- 平均来说，大约有1/2的节点会出现在Level 1
- 大约有1/4的节点会出现在Level 2
- 大约有1/8的节点会出现在Level 3
- 以此类推…
def random_level(self):
\”\”\”生成随机层数\”\”\”
level = 0
# 抛硬币决定是否上升层级
while random.random() < self.P and level < self.MAX_LEVEL:
level += 1
return level
搜索操作
跳表的搜索从最高层开始，然后逐层向下：
def search(self, key):
\”\”\”查找指定的key\”\”\”
current = self.header
# 从最高层开始，逐层向下查找
for i in range(self.level, –1, –1):
# 在当前层水平移动，直到找到小于或等于目标值的最大节点
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
# 现在在底层，检查下一个节点是否是目标值
current = current.forward[0]
# 如果下一个节点存在且key相等，则找到目标
if current and current.key == key:
return current
# 没有找到目标
return None
示例
查找值为12的节点的过程。搜索从头节点的最高层开始，逐层向下进行。
步骤一**从最高层开始搜索**：
- 搜索从跳表的最高层（Level 2）的头节点开始。我们要查找值为12的节点。
- 当前位置：Level 2的Head节点
- 目标：找到值为12的节点
步骤二**在最高层水平移动到合适位置**：
- 在Level 2层，Head的next指向值为7的节点。因为7 < 12，所以我们移动到值为7的节点。
- 当前位置：Level 2的节点7
- 判断：7 < 12，可以继续向右移动
步骤三**当前层无法继续前进，降低层级**：
- 在Level 2层，节点7的next指向值为18的节点。因为18 > 12，所以我们无法继续向右移动。此时需要降到Level 1层继续搜索。
- 当前位置：Level 1的节点7
- 判断：在Level 2中，下一个节点值18 > 12，无法继续水平移动，需要降级
步骤四**在中间层继续搜索**：
- 在Level 1层，节点7的next指向值为12的节点。因为12 = 12，我们找到了目标值，但仍然需要降到最底层以确认节点是否存在于最底层。
- 当前位置：Level 1的节点12
- 判断：12 = 12，找到目标值，继续降级到最底层确认
步骤五**在最底层确认结果**：
- 在Level 0（最底层），我们确认值为12的节点确实存在。搜索成功完成。
- 当前位置：Level 0的节点12
- 结果：成功找到目标节点12
搜索路径总结：
搜索操作的时间复杂度为O(log n)，因为我们利用了跳表的分层结构，每一层大约跳过了一半的节点。
插入操作
跳表的插入过程包括：
def insert(self, key):
\”\”\”插入指定的key\”\”\”
# 创建更新数组，用于存储需要更新前向指针的节点
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].key < key:
current = current.forward[i]
# 记录每一层需要更新的节点
update[i] = current
# 移动到下一个节点
current = current.forward[0]
# 检查key是否已存在
if current and current.key == key:
return False # 已存在，插入失败
# 为新节点生成随机层数
random_level = self.random_level()
if random_level > self.level:
# 更新跳表当前最大层数
for i in range(self.level + 1, random_level + 1):
update[i] = self.header
self.level = random_level
# 创建新节点
new_node = SkipListNode(key, random_level)
