跳表简明指南 | AI生成和翻译
跳跃表：全面介绍
概述
跳跃表（Skip List）是一种概率性数据结构，能够在平均情况下实现 $O(\log n)$ 的搜索、插入和删除操作复杂度。它由 William Pugh 于 1989 年发明，作为平衡二叉搜索树（如 AVL 树或红黑树）的一种更简单替代方案。
核心概念
跳跃表的基本思想是维护多层链表：
- 底层是一个标准的有序链表，包含所有元素。
- 高层充当“快车道”，跳过底层链表的部分区域，实现更快的遍历。
可以想象一个地铁系统，部分列车在每个站点停靠（底层），而快车仅在主要枢纽站停靠（高层）。要快速到达目的地，你会先乘坐快车，然后换乘普通列车到达具体站点。
结构
跳跃表中的每个节点包含：
- 值（Value）：节点存储的数据。
- 前向指针（Forward Pointers）：指向各层下一个节点的指针数组。
层级
- 节点的层级在插入时随机确定。
- 层级为 $k$ 的节点在 $0, 1, …, k$ 层均有指向下一个节点的指针。
- 整个列表的最大层级通常由元素数量决定（$L = \log_{1/p} N$）。
算法
1. 搜索算法
搜索目标值 $x$：
- 从最高层的头节点开始。
- 在当前层向右移动，只要下一个节点的值小于 $x$。
- 如果下一个节点的值大于 $x$ 或为空，则向下移动一层。
- 重复步骤 2 和 3，直到到达第 0 层。
- 检查第 0 层的下一个节点。如果其值等于 $x$，则搜索成功。
2. 插入算法
插入值 $x$：
- 搜索 $x$ 应插入的位置，并记录每层插入点前的节点（更新栈）。
- 确定层级：随机生成新节点的层级 $L$。通常通过抛硬币（概率 $p = 0.5$）实现。正面则增加层级并继续抛硬币；反面则停止。
- 创建节点：分配一个层级为 $L$ 的新节点。
- 更新指针：在 $0$ 到 $L$ 的每一层，更新前驱节点的前向指针，使其指向新节点，并设置新节点的指针指向后续节点。
3. 删除算法
删除值 $x$：
- 搜索 包含 $x$ 的节点，并记录每层的前驱节点。
- 如果找到，则更新每层前驱节点的前向指针，绕过被删除节点。
- 释放被删除节点的内存。
- 可选：如果最高层变空，则降低列表的最大层级。
复杂度分析
| 操作 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| 搜索 | $O(\log n)$ | $O(n)$ | $O(n)$ |
| 插入 | $O(\log n)$ | $O(n)$ | $O(n)$ |
| 删除 | $O(\log n)$ | $O(n)$ | $O(n)$ |
- 平均情况：通过随机化实现。预期层级数为 $\log_{1/p} n$。
- 最坏情况：当随机层级生成退化为单层结构（如所有节点在第 0 层）时发生，此时退化为简单链表。但这种情况在统计上极不可能出现。
与平衡树的对比
| 特性 | 跳跃表 | 平衡 BST（AVL/红黑树） |
|---|---|---|
| 实现 | 更简单，易于调试 | 复杂，边界情况多 |
| 并发 | 更易实现无锁操作 | 实现无锁操作困难 |
| 性能 | 平均情况可比 | 保证最坏情况性能 |
| 内存 | 稍高（多个指针） | 较低（每个节点固定指针） |
应用场景
- 数据库：LevelDB 和 Redis 使用跳跃表实现内存有序集合。
- 并发系统：Java 的
ConcurrentSkipListMap和ConcurrentSkipListSet。 - 近似计数：用于某些概率算法。
结论
跳跃表为平衡二叉搜索树提供了一种健壮、高效且易于实现的替代方案。虽然依赖概率而非严格平衡规则，但其性能特点使其成为高并发环境和注重实现简洁性的系统的理想选择。
参考文献：