跳表 SkipList：随机化的快速查找

什么是跳表？

跳表（SkipList）是一种基于有序链表的随机化数据结构。它通过在原始链表之上建立多级索引，实现类似二分查找的快速查询效率。跳表由 William Pugh 在 1989 年提出，其设计初衷是作为一种可以替代平衡树的高效数据结构。

与平衡二叉搜索树相比，跳表的实现更简单，且通过随机化来维护平衡，无需复杂的旋转操作。在 Redis 的有序集合、LevelDB 的内存表等系统中，跳表被广泛使用。

核心思想：空间换时间

假设我们有一个有序的单链表，查找某个值的时间复杂度是 O(n)。如果我们每隔一个节点，提取出一个节点作为“索引”，并在原链表上方新建一层“快速通道”，查找时就可以先走索引层，再下沉到原始链表，从而将查找时间减半。依此类推，当索引层数增加到 log₂n 时，查找的时间复杂度将降至 O(log n)。

跳表正是通过随机决定节点是否向上升级的方式，动态构建出类似完美平衡的多级索引结构。

跳表的结构

一个跳表由多层链表组成：

• 最底层（Level 0）：包含所有元素的有序链表。
• 上层（Level i，i ≥ 1）：是 Level i-1 的“快速通道”，节点数量更少，层数越高节点越稀疏。
• 每个节点包含一个 值域 和 一组前进指针（forward pointers），指针数量即节点的“高度”。
• 跳表通常有一个头节点（head），其高度与当前跳表的最高层数一致，各层 forward 指针初始指向 NULL。

Level 2:   head ──→ 7 ─────────→ 21 ──────→ NULL
Level 1:   head ──→ 3 ──→ 7 ──→ 14 ──→ 21 ──→ NULL
Level 0:   head → 1 → 3 → 5 → 7 → 9 → 14 → 21 → NULL

节点的高度（即参与索引的层数）是在插入时由随机算法决定的，通常使用抛硬币模型：有 50% 的概率增加一层，直到失败为止。这种随机化策略使跳表在概率上始终保持平衡。

查找操作

跳表的查找过程与“在多层索引中逐层下降”类似，具体步骤如下：

1. 从头节点的最高层开始，设当前节点 curr = head，当前层 level = 跳表的最高层。
2. 在 level 层中，尽可能向前移动，直到 curr->forward[level]->value 大于或等于目标值。
3. 如果当前层的下一个节点值正好等于目标值，则查找成功，返回节点。
4. 否则，向下一层（level--），重复步骤 2。
5. 遍历到 Level 0 后，如果仍未找到，则元素不存在。

查找代码示意：

Node* search(SkipList* sl, int val) {
    Node* curr = sl->head;
    for (int i = sl->maxLevel; i >= 0; i--) {
        while (curr->forward[i] && curr->forward[i]->value < val)
            curr = curr->forward[i];
    }
    curr = curr->forward[0];
    if (curr && curr->value == val) return curr;
    return NULL;
}

时间复杂度：O(log n) 期望，最坏情况下所有节点被提升至同一高层（概率极低）会退化为 O(n)。

插入操作

插入操作需要同时维护各层的链表有序，并随机生成新节点的高度。

1. 查找插入位置：类似查找过程，但需要记录在每一层遇到的“前驱节点”，以便后续插入时修改指针。准备一个 update 数组，update[i] 存储在 Level i 中新节点应该连接在前驱节点的末尾。
2. 生成随机高度：通过一个随机函数（例如 randomLevel()）决定新节点的层数，通常从 1 开始，每次以概率 p（常见为 0.5）递增，直到随机失败或达到最大限制。
3. 创建新节点：分配一个高度为 newLevel 的节点，设置其值。
4. 修改指针：对于每一层 0 到 newLevel-1，将 newNode->forward[i] 指向 update[i]->forward[i]，再将 update[i]->forward[i] 指向 newNode。
5. 更新跳表最大层数：如果 newLevel 大于当前最大层数，则更新。

随机高度生成伪代码：

int randomLevel() {
    int level = 1;
    while ((rand() & 1) && level < MAX_LEVEL) // p = 0.5
        level++;
    return level;
}

通过这种随机化，一个节点平均高度为 1/(1-p)。当 p=0.5 时，平均高度为 2，保证了索引的平衡性。

插入时间复杂度为 O(log n) 期望。

删除操作

删除操作与插入类似，但不需要生成随机高度：

1. 查找待删除节点的前驱：同样使用 update 数组记录每一层的前驱节点。
2. 检查节点是否存在：从 Level 0 的 update[0]->forward[0] 获取候选节点，如果值匹配，则进行删除。
3. 修改指针：对于该节点参与的每一层 i（0 ≤ i < 节点高度），将 update[i]->forward[i] 设置为 toBeDeleted->forward[i]。
4. 释放节点内存。
5. 调整跳表最高层：如果删除的是最高层的唯一节点，则需要降低 maxLevel。

时间复杂度同样是 O(log n) 期望。

复杂度分析

空间复杂度：假设有 n 个元素，p=0.5，节点平均高度为 2，因此所有 forward 指针总数为约 2n，空间复杂度为 O(n)，常数因子比平衡树略高，但避免了复杂的平衡维护开销。

跳表的性能高度依赖随机函数的均匀性。在实际应用中，通过设置合理的 MAX_LEVEL（例如 32 或 64），可以支撑海量数据，并且多层级结构天然支持范围查询。

跳表与平衡树的对比

跳表以略微增加的内存和概率性的平衡，换取了实现简单和高效的范围查询能力，因此在许多工程中被优先使用。

跳表的应用场景

• Redis 有序集合（Sorted Set）：当元素数量较多或元素长度较大时，Redis 使用跳表作为底层实现，支持 ZADD、ZRANGE 等命令。
• LevelDB / RocksDB 的 MemTable：内存中的临时数据存储使用跳表，保证写入的快速和有序迭代。
• HBase 的 MemStore：类似的应用，利用跳表维护有序数据。
• 算法竞赛与面试：跳表常作为一种需要展示对有序数据结构与随机化理解的手写题。

总结

跳表通过随机化建立多级索引，将链表查找时间复杂度从 O(n) 降低至 O(log n)。它结构直观，插入、删除、查找的逻辑与多层链表操作一致，很适合作为初学者理解空间换时间、随机化平衡思想的绝佳案例。深入理解跳表，也有助于掌握 Redis 等组件的核心原理。