第 76 课：跳表 (Skip List)

课程：数据结构与算法模块：高级数据结构难度：高级标签：skip-list, probabilistic, level, search 上一课：A* 搜索算法 下一课：伸展树

1. 学习目标

完成本课学习后，你将能够：

理解跳表的基本结构和设计原理，明白它如何通过概率方法达到类似平衡树的效果。
实现一个跳表的核心操作：查找、插入和删除。
将跳表与平衡二叉搜索树（如红黑树、AVL树）进行比较，分析其优劣。
分析跳表各操作的平均时间复杂度。

2. 核心概念

想象一下，你在一个很长的有序链表里查找一个元素。最坏的情况，你需要从头遍历到尾，时间复杂度是 O(n)。这显然太慢了。

跳表 (Skip List) 的想法非常巧妙，它的核心思想是 “空间换时间” 和 “概率平衡”。我们可以给这个链表加几层“索引”。

通俗比喻：把链表想象成一栋楼的一层，查找元素就像在一楼找一个房间，需要一个一个门牌号地看过去。

第一层索引（二楼）：每隔一个房间，就设一个“楼梯口”（节点）。这样，从二楼可以“跳”过一楼的一个房间。
第二层索引（三楼）：每隔两个房间（在二楼的基础上），再设一个“楼梯口”。从三楼可以“跳”过更多的一楼房间。
更高层索引：以此类推，直到顶层索引可能只有几个关键节点。

查找时，我们从最高层开始，快速向右移动（跳跃），直到下一个节点大于目标值，然后下降一层，继续向右查找，直到在最底层找到目标元素或确定其不存在。这个过程就像乘电梯和走楼梯结合，大大减少了比较次数。

平衡的关键：跳表不像红黑树那样需要严格的旋转操作来维持平衡。它通过一个随机过程来决定每个新插入的节点应该出现在多少层索引上。通常，我们会以一定的概率（例如 1/2 或 1/4）来决定节点是否“晋升”到上一层。

3. 代码示例

下面是一个简化版的 Python 跳表实现，包含核心操作。

import random

class Node:
    def __init__(self, key, level):
        self.key = key
        # forward 是一个列表，存储指向各层下一个节点的指针
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level, p):
        self.MAXLVL = max_level  # 最大层数
        self.P = p               # 晋升概率，例如 0.5
        self.header = self._create_node(self.MAXLVL, -1)  # 头节点，key为-1作为哨兵
        self.level = 0           # 当前跳表实际的最高层数

    def _create_node(self, lvl, key):
        """创建一个新节点"""
        n = Node(key, lvl)
        return n

    def random_level(self):
        """随机决定一个节点的层数"""
        lvl = 0
        # 以概率 P 递增层数，但不超过最大层数
        while random.random() < self.P and lvl < self.MAXLVL:
            lvl += 1
        return lvl

    def insert(self, key):
        """插入一个键"""
        # update 存储每一层需要更新的前驱节点
        update = [None] * (self.MAXLVL + 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 is None or current.key != key:
            # 为新节点随机生成层数
            rlevel = self.random_level()

            # 如果新层数大于当前跳表层数，更新 update 列表和当前层数
            if rlevel > self.level:
                for i in range(self.level + 1, rlevel + 1):
                    update[i] = self.header
                self.level = rlevel

            # 创建新节点
            new_node = self._create_node(rlevel, key)

            # 逐层插入，更新前驱节点的 forward 指针
            for i in range(rlevel + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

            print(f"成功插入元素: {key}")

    def search(self, 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]
        if current and current.key == key:
            print(f"找到元素: {key}")
            return True
        else:
            print(f"未找到元素: {key}")
            return False

    def delete(self, key):
        """删除一个键"""
        update = [None] * (self.MAXLVL + 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]

        # 如果找到目标节点
        if current is not None and current.key == key:
            # 从最底层开始，逐层更新前驱节点的 forward 指针
            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

            print(f"成功删除元素: {key}")
            return True
        else:
            print(f"删除失败，元素不存在: {key}")
            return False

# --- 测试代码 ---
if __name__ == "__main__":
    # 创建一个最大4层，晋升概率为0.5的跳表
    skiplist = SkipList(4, 0.5)

    # 插入一些元素
    skiplist.insert(3)
    skiplist.insert(6)
    skiplist.insert(7)
    skiplist.insert(9)
    skiplist.insert(12)
    skiplist.insert(19)
    skiplist.insert(17)
    skiplist.insert(26)
    skiplist.insert(21)
    skiplist.insert(25)

    print("\n--- 开始查找 ---")
    skiplist.search(19)
    skiplist.search(15)

    print("\n--- 开始删除 ---")
    skiplist.delete(19)
    skiplist.search(19) # 应该找不到了

4. 实践练习

练习题 1：可视化你的跳表 为上面的 SkipList 类添加一个 display() 方法，能够以一种直观的方式打印出跳表的每一层结构。预期输出类似：

层0: [HEAD] -> 3 -> 6 -> 7 -> 9 -> ...
层1: [HEAD] -> 6 -> 17 -> 26
层2: [HEAD] -> 17
...

练习题 2：实现范围查询 为跳表添加一个 range_search(low, high) 方法，返回所有在 [low, high] 闭区间内的元素列表。利用跳表的有序性来高效实现。

练习题 3：性能对比（进阶） 编写一个简单的性能测试脚本，分别使用 Python 的 list (排序后二分查找) 和本课实现的 SkipList，对大量的随机插入、查找和删除操作进行计时比较。思考：在什么数据规模下，跳表的优势会开始显现？

5. 常见错误

层级更新错误：在插入或删除后，忘记更新跳表的当前最大层数 (self.level)，这会导致后续操作访问无效的高层索引。

# 错误示例：删除后忘记降低层级
while (self.level > 0 and self.header.forward[self.level] is None):
    self.level -= 1  # 这行代码至关重要，不能省略

指针更新顺序错误：在插入新节点时，必须按照从高层到低层的顺序更新指针，否则会破坏链表结构。

# 正确顺序：从高层(rlevel)到低层(0)
for i in range(rlevel + 1):
    new_node.forward[i] = update[i].forward[i]  # 1. 新节点指向原后继
    update[i].forward[i] = new_node              # 2. 前驱指向新节点

随机层级实现不当：random_level() 方法如果返回的层级总是很低，跳表会退化成普通链表。概率 p 的选择（常用 0.5 或 0.25）和最大层数的设定需要根据数据量权衡。
边界条件处理：查找、删除不存在的元素时，没有检查 current is None，可能导致 AttributeError。

6. 小结

本节课我们学习了跳表，一种高效的概率型数据结构。让我们回顾关键要点：

结构：跳表通过多层有序链表（索引）来加速查找，底层存储全部数据，上层是底层的“快速通道”。
平衡机制：不同于严格平衡的树结构，跳表通过随机化决定节点的层数，以期望达到概率意义上的平衡，实现简单。
时间复杂度：
- 查找、插入、删除：平均 O(log n)。
- 最坏情况：O(n) (当随机过程不理想时，但概率极低)。
空间复杂度：O(n)，平均需要 O(n) 个额外指针来构建索引层。
优势：实现相对简单、并发友好（无复杂的树旋转）、在实践中常具有优异的性能。Redis 的有序集合 (ZSET) 的底层实现之一就是跳表。
劣势：空间消耗大于普通链表；性能依赖于随机数生成器的质量。

跳表是理解“如何用简单结构和随机化思想构建高效系统”的绝佳范例。在下一课，我们将学习另一种自调整的二叉搜索树——伸展树。

练习编辑器

rust