跳表（Skip List）原理与实现

跳表是一种基于有序链表的高效数据结构，它通过添加多级索引来加速查找过程，使得平均时间复杂度达到O(log n)，同时保持了链表结构的简单性。跳表由William Pugh于1990年提出，常用于实现有序集合和键值存储。

1. 基本结构设计

• 跳表由多层有序链表组成，最底层（第0层）包含所有元素
• 每一层都是下一层的"快速通道"，高层节点稀疏分布
• 每个节点包含：
  • 存储的值（或键值对）
  • 指向同一层下一个节点的指针数组
  • 节点高度（层数），通过随机算法确定

2. 节点高度随机化算法

• 新节点的高度通过抛硬币方式决定：
  • 从高度1开始
  • 反复抛硬币，若为正面则高度+1
  • 直到出现反面为止
• 设置最大高度限制（通常为log₂n的倍数）
• 这种随机化保证了高层节点的均匀分布

3. 查找操作实现
查找值为target的节点：

1. 从最高层头节点开始
2. 在当前层向右遍历，直到下一个节点值≥target
3. 如果当前节点值等于target，查找成功
4. 否则下降一层，重复步骤2-3
5. 到达最底层仍未找到则失败

示例：查找值6

• 第3层：1→NULL（下降）
• 第2层：1→4→NULL（下降）
• 第1层：1→4→7（6<7，下降）
• 第0层：4→5→6（找到）

4. 插入操作实现
插入新值value：

1. 查找插入点：记录每层需要更新的前驱节点
2. 随机生成新节点高度
3. 创建新节点，初始化各层指针
4. 从下到上更新指针：
   • 新节点的next指向前驱节点的next
   • 前驱节点的next指向新节点

5. 删除操作实现
删除值value：

1. 查找目标节点，记录每层前驱节点
2. 从最高层开始，更新前驱节点的next指针
3. 释放被删除节点的内存
4. 可选：调整跳表高度（如果删除的是最高层节点）

6. 复杂度分析

• 空间复杂度：O(n)，索引节点总数约为n/2 + n/4 + ... ≈ n
• 时间复杂度：
  • 查找/插入/删除：O(log n)平均情况
  • 最坏情况：O(n)，但概率极低

7. 实际应用优化

• 设置最大层数限制（如32层）
• 使用概率p控制层数增长（通常p=1/2）
• 实现迭代器支持范围查询
• 添加线程安全机制（读写锁）

跳表通过简单的随机化方法实现了接近平衡树的性能，同时代码实现更简洁，被广泛应用于Redis、LevelDB等知名系统中。