跳跃表（Skip List）

描述
跳跃表是一种概率性的数据结构，用于在有序元素集合中实现高效的查找、插入和删除操作。它通过构建多层索引来加速搜索，每一层都是下一层的“快速通道”。跳跃表的期望时间复杂度为O(log n)，与平衡树相当，但实现更简单。它常用于Redis等系统替代平衡树。

核心思想

1. 多层链表结构：跳跃表由多个层级（Level）的链表组成。底层（Level 0）包含所有元素，每一高层级包含下一层级的部分元素作为索引。
2. 随机层级分配：插入新节点时，通过随机算法（如抛硬币）决定其出现的最高层级，避免手动平衡。
3. 搜索路径优化：从最高层开始查找，若下一节点值大于目标值，则下降一层继续查找，逐步逼近目标。

详细步骤与示例

1. 数据结构定义
每个节点包含：

• 值（value）：存储的数据。
• 前进指针数组（forward[]）：指向同一层级的下一个节点。
• 层级（level）：节点最高所在的层级。

示例节点结构（伪代码）：

class SkipListNode {
    int value;
    SkipListNode[] forward; // 长度为节点的层级+1
    int level;
}

2. 初始化
创建一个头节点（head），其层级设为最大允许层级（如MAX_LEVEL）。头节点的所有前进指针初始指向空（NULL）。

3. 搜索操作
以查找值target为例：

• 从最高层（如MAX_LEVEL-1）开始，设置当前节点current = head。
• 横向移动：若当前层的下一节点存在且其值小于target，则向右移动（current = current.forward[i]）。
• 纵向下降：若下一节点值大于或等于target，则下降一层（i--）。
• 重复直到底层（Level 0）。若底层下一节点值等于target，则查找成功。

示例：在跳跃表[1, 3, 5, 7, 9]中查找5（假设有2层索引）：

• Level 2：头节点→1（1<5）→NULL（下降至Level 1）。
• Level 1：1→5（5≥5，下降至Level 0）。
• Level 0：5→5（匹配成功）。

4. 插入操作
插入值x的步骤：

• 步骤1：记录搜索路径
  在搜索x的过程中，记录每一层最后访问的节点（即小于x的最大节点）到数组update[]中。update[i]表示在层级i需要更新指针的节点。

• 步骤2：随机生成层级
  通过随机函数（如每次抛硬币，正面则层级+1，直到反面或达最大层级）决定新节点的层级lvl。

• 步骤3：创建新节点
  新建节点node，其层级为lvl，值为x。

• 步骤4：更新指针
  对于每一层i（从0到lvl）：

  • node.forward[i] = update[i].forward[i]（新节点指向原节点的后继）。
  • update[i].forward[i] = node（原节点指向新节点）。

示例：向空表插入3（随机层级=1）：

• 搜索路径：所有层的update[i]均为头节点。
• 新节点层级为1，更新：
  • Level 1：head→3→NULL
  • Level 0：head→3→NULL

5. 删除操作
删除值x的步骤：

• 步骤1：搜索并记录路径
  类似插入，记录每一层最后访问的节点到update[]。

• 步骤2：检查是否存在
  若底层（Level 0）的下一节点值不等于x，则删除失败。

• 步骤3：更新指针
  对于每一层i，若update[i].forward[i]等于x的节点，则直接跳过该节点：
  update[i].forward[i] = node.forward[i]。

• 步骤4：释放内存
  删除节点后，若高层索引节点被删光，可动态降低跳跃表高度。

关键细节

1. 随机层级的概率控制：通常设定概率p=0.5，即节点有50%概率上升一层。层级数期望为1/(1-p)，保证平衡性。
2. 时间复杂度：
   • 搜索/插入/删除：平均O(log n)，最坏O(n)（但概率极低）。
3. 空间复杂度：平均O(n)，因索引节点数约为n/(1-p)。

对比平衡树

• 优点：实现简单，无需旋转操作，支持范围查询。
• 缺点：概率性结构，最坏情况性能理论较差（但实际罕见）。

通过这种“电梯式”的索引跳跃，跳跃表在保持有序性的同时，大幅提升了操作效率。