高效查找利器：Python跳表（Skip List）从零实现详解

跳表由多层链表组成：

• 最底层包含所有元素，按顺序排列；
• 上层是“快速通道”，只包含部分元素；
• 查找时从最高层开始，逐层向下“跳跃”逼近目标。

为什么使用跳表？

相比红黑树等平衡树结构，跳表具有以下优势：

• 代码实现更简单；
• 天然支持并发操作（如 Redis 的 ZSET 就使用跳表）；
• 平均时间复杂度为 O(log n)，与平衡树相当。

Python 跳表实现步骤

我们将分三步构建跳表：

1. 定义节点（Node）结构；
2. 实现随机层级生成函数；
3. 编写跳表核心方法：插入、查找、删除。

1. 定义跳表节点

每个节点包含值（value）和指向右侧节点的指针列表（forward）：

import randomclass Node:    def __init__(self, value, level):        self.value = value        # forward[i] 表示第 i 层指向的下一个节点        self.forward = [None] * (level + 1)

2. 跳表类骨架

设定最大层数（MAX_LEVEL）和概率因子（P = 0.5）：

class SkipList:    MAX_LEVEL = 16  # 最大层数    P = 0.5         # 晋升概率    def __init__(self):        # 创建头节点（不存实际数据）        self.head = Node(None, self.MAX_LEVEL)        self.level = 0  # 当前实际层数

3. 随机生成节点层数

新节点以 50% 概率晋升到更高层：

def _random_level(self):    level = 0    while random.random() < self.P and level < self.MAX_LEVEL:        level += 1    return level

4. 查找操作

从最高层开始，逐层向右或向下移动：

def search(self, value):    current = self.head    # 从最高层往下遍历    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]    return current is not None and current.value == value

5. 插入操作

先找到插入位置，再更新各层指针：

def insert(self, value):    # 用于记录每层的前驱节点    update = [None] * (self.MAX_LEVEL + 1)    current = self.head    # 从最高层开始查找插入位置    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:        return    # 随机生成新节点层数    new_level = self._random_level()    if new_level > self.level:        for i in range(self.level + 1, new_level + 1):            update[i] = self.head        self.level = new_level    # 创建新节点    new_node = Node(value, new_level)    # 更新各层指针    for i in range(new_level + 1):        new_node.forward[i] = update[i].forward[i]        update[i].forward[i] = new_node

6. 删除操作（简要实现）

def delete(self, value):    update = [None] * (self.MAX_LEVEL + 1)    current = self.head    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.head.forward[self.level] is None:            self.level -= 1

完整测试示例

# 测试跳表sl = SkipList()sl.insert(3)sl.insert(10)sl.insert(1)sl.insert(7)print(sl.search(10))  # Trueprint(sl.search(5))   # Falsesl.delete(10)print(sl.search(10))  # False

总结

通过本教程，你已经掌握了 Python跳表实现 的完整过程。跳表作为一种高效的有序集合跳表结构，在实际工程中（如 Redis、LevelDB）被广泛应用。其核心在于利用随机化构建多层索引，实现 高效查找跳表 的 O(log n) 性能。

建议你动手敲一遍代码，加深理解。跳表虽不如红黑树“高大上”，但胜在简洁优雅，是学习高级数据结构的绝佳起点！