跳跃表（Skip List）的查找、插入与删除操作
字数 2663 2025-12-08 19:13:01

跳跃表（Skip List）的查找、插入与删除操作

一、问题描述

跳跃表是一种基于有序链表的多层概率性数据结构，由 William Pugh 在 1990 年提出，用于实现有序集合的高效查找、插入和删除操作。它在平均情况和最坏情况下的时间复杂度与平衡树（如红黑树、AVL树）相当，但实现更为简单，并且支持区间查询。在 Redis 和 LevelDB 等实际系统中广泛应用。

今天我将详细讲解跳跃表的核心操作：查找、插入和删除，重点是理解其多层结构如何加速查找，以及如何通过随机化维护近似平衡。

二、数据结构基础

在深入操作之前，我们先回顾跳跃表的结构：

  • 一个跳跃表由多层有序链表组成。
  • 最底层（第 0 层）包含所有元素，按升序（或降序）链接。
  • 上面每一层都是下面一层的“快速通道”，包含下面一层的部分元素，类似于地铁的“快线”。
  • 每个节点包含：
    • 一个值（key）。
    • 一个“高度”（level），表示节点出现在哪些层。
    • 一个“前进指针”数组（forward[]，长度=高度），指向该节点在每一层的下一个节点。

例如，一个值为 9 的节点，高度为 3，表示它出现在第 0、1、2 层，它的 forward[0] 指向第 0 层下一个节点，forward[1] 指向第 1 层下一个节点，以此类推。

三、查找操作

目标：在跳跃表中查找是否存在键为 key 的元素。

步骤分解：

  1. 从最高层（比如 maxLevel）的头节点开始。
  2. 在当前层，沿着“前进指针”向右移动，直到遇到下一个节点的键大于等于 key，或者为 NULL。
  3. 如果当前层的下一个节点键等于 key，则查找成功，返回该节点。
  4. 如果当前层的下一个节点键大于 key，则下降一层（层数减 1），回到步骤 2 继续向右比较。
  5. 如果下降到第 0 层仍未找到，则说明 key 不存在。

关键点：

  • 高层允许快速跳过多个节点，类似二分查找的跳跃。
  • 查找路径是一个“Z字形”过程：先在高层大步前进，再逐层下降，最终在第 0 层精确比对。

示例：查找 17（假设 maxLevel=3）

  • 第 3 层：从头节点出发，下一个节点是 6（小于 17），向右到 6；6 的下一个是 NULL，下降。
  • 第 2 层：从 6 出发，下一个是 25（大于 17），下降。
  • 第 1 层：从 6 出发，下一个是 9（小于 17），向右到 9；9 的下一个是 25（大于 17），下降。
  • 第 0 层：从 9 出发，下一个是 12（小于 17），向右到 12；12 的下一个是 17（等于 17），找到。

四、插入操作

目标：插入一个新键 key，并维持跳跃表的多层结构。

步骤分解：

  1. 确定新节点高度：通过随机算法决定新节点出现在几层。常见方法是：从第 0 层开始，每次抛硬币（概率 p=0.5），如果正面则增加一层，直到出现反面或达到最大高度限制。这样，节点出现在第 i 层的概率约为 1/2^(i+1)，保证高层节点稀疏。
  2. 查找插入位置：类似查找过程，但需要记录每一层中“最后一个小于 key 的节点”的指针，存入 update 数组（长度为 maxLevel）。
    • 例如，update[i] 存储第 i 层中，在插入位置前一个节点的指针。
  3. 创建新节点：分配节点，设置其键为 key，高度为随机确定的高度 h。
  4. 链接新节点：
    • 对于每一层 i（0 ≤ i < h）：
      • 新节点的 forward[i] 指向 update[i] 在第 i 层原来的下一个节点。
      • update[i] 的 forward[i] 指向新节点。
  5. 更新跳跃表高度：如果新节点高度大于当前跳跃表的最大高度，更新头节点的高度，并将新增层的前进指针指向新节点。

示例：插入 15（假设随机高度 h=2）

  • 假设当前表有元素：头节点 → 6 → 9 → 12 → 17 → 25。
  • 查找 update 数组：
    • 第 1 层：小于 15 的最后一个节点是 9。
    • 第 0 层：小于 15 的最后一个节点是 12。
  • 创建节点 15（高度 2）。
  • 链接：
    • 第 1 层：15 指向 9 原来的下一个（17），9 指向 15。
    • 第 0 层：15 指向 12 原来的下一个（17），12 指向 15。

五、删除操作

目标：删除键为 key 的节点。

步骤分解：

  1. 查找待删节点：类似查找过程，同时记录每一层中“最后一个小于 key 的节点”的指针，存入 update 数组。
  2. 检查是否存在：在第 0 层，如果 update[0] 的下一个节点键等于 key，则该节点为待删节点；否则 key 不存在，返回。
  3. 解除链接：
    • 对于待删节点的每一层 i：
      • 将 update[i] 在第 i 层的前进指针，指向待删节点在第 i 层的前进指针（即跳过待删节点）。
  4. 释放节点内存。
  5. 更新跳跃表高度：如果删除的节点是最高层中的唯一节点，则降低跳跃表的高度。

示例：删除 9（假设 9 高度为 3）

  • 查找 update 数组：
    • 第 2 层：小于 9 的最后一个节点是头节点。
    • 第 1 层：小于 9 的最后一个节点是 6。
    • 第 0 层：小于 9 的最后一个节点是 6。
  • 检查：update[0]（即 6）的下一个节点是 9，存在。
  • 解除链接：
    • 第 2 层：头节点指向 9 的下一个（如 25）。
    • 第 1 层：6 指向 9 的下一个（12）。
    • 第 0 层：6 指向 9 的下一个（12）。

六、复杂度分析

  • 空间复杂度：平均 O(n)，每个节点平均高度约 1/(1-p) = 2（当 p=0.5）。
  • 时间复杂度：
    • 查找、插入、删除的平均时间复杂度均为 O(log n)。
    • 最坏情况（所有节点高度都为 1）退化为有序链表，O(n)，但概率极低。
  • 与平衡树对比：跳跃表实现简单，无需旋转等复杂操作，且天然支持区间查询（在第 0 层遍历即可）。

七、关键点总结

  1. 随机化层高：通过概率保证高层节点稀少，实现近似平衡。
  2. update 数组：在插入和删除中记录每一层的前驱节点，是链接操作的关键。
  3. 查找路径：从高层向低层、从大范围向精确位置逐步逼近，是加速的本质。

通过以上步骤，你应该能理解跳跃表如何通过多层结构以简单的方式实现高效动态操作。如果你想进一步了解随机层高的数学证明或实际系统中的优化（如固定最大层高、使用确定性哈希替代随机），我们可以继续深入。

跳跃表（Skip List）的查找、插入与删除操作 一、问题描述 跳跃表是一种基于有序链表的多层概率性数据结构，由 William Pugh 在 1990 年提出，用于实现有序集合的高效查找、插入和删除操作。它在平均情况和最坏情况下的时间复杂度与平衡树（如红黑树、AVL树）相当，但实现更为简单，并且支持区间查询。在 Redis 和 LevelDB 等实际系统中广泛应用。 今天我将详细讲解跳跃表的核心操作：查找、插入和删除，重点是理解其多层结构如何加速查找，以及如何通过随机化维护近似平衡。 二、数据结构基础 在深入操作之前，我们先回顾跳跃表的结构： 一个跳跃表由多层有序链表组成。 最底层（第 0 层）包含所有元素，按升序（或降序）链接。 上面每一层都是下面一层的“快速通道”，包含下面一层的部分元素，类似于地铁的“快线”。 每个节点包含： 一个值（key）。 一个“高度”（level），表示节点出现在哪些层。 一个“前进指针”数组（forward[ ]，长度=高度），指向该节点在每一层的下一个节点。 例如，一个值为 9 的节点，高度为 3，表示它出现在第 0、1、2 层，它的 forward[0] 指向第 0 层下一个节点， forward[1] 指向第 1 层下一个节点，以此类推。 三、查找操作 目标：在跳跃表中查找是否存在键为 key 的元素。 步骤分解： 从最高层（比如 maxLevel ）的头节点开始。 在当前层，沿着“前进指针”向右移动，直到遇到下一个节点的键大于等于 key ，或者为 NULL。 如果当前层的下一个节点键等于 key ，则查找成功，返回该节点。 如果当前层的下一个节点键大于 key ，则下降一层（层数减 1），回到步骤 2 继续向右比较。 如果下降到第 0 层仍未找到，则说明 key 不存在。 关键点 ： 高层允许快速跳过多个节点，类似二分查找的跳跃。 查找路径是一个“Z字形”过程：先在高层大步前进，再逐层下降，最终在第 0 层精确比对。 示例 ：查找 17（假设 maxLevel=3） 第 3 层：从头节点出发，下一个节点是 6（小于 17），向右到 6；6 的下一个是 NULL，下降。 第 2 层：从 6 出发，下一个是 25（大于 17），下降。 第 1 层：从 6 出发，下一个是 9（小于 17），向右到 9；9 的下一个是 25（大于 17），下降。 第 0 层：从 9 出发，下一个是 12（小于 17），向右到 12；12 的下一个是 17（等于 17），找到。 四、插入操作 目标：插入一个新键 key ，并维持跳跃表的多层结构。 步骤分解： 确定新节点高度 ：通过随机算法决定新节点出现在几层。常见方法是：从第 0 层开始，每次抛硬币（概率 p=0.5），如果正面则增加一层，直到出现反面或达到最大高度限制。这样，节点出现在第 i 层的概率约为 1/2^(i+1)，保证高层节点稀疏。 查找插入位置 ：类似查找过程，但需要记录每一层中“最后一个小于 key 的节点”的指针，存入 update 数组（长度为 maxLevel）。 例如， update[i] 存储第 i 层中，在插入位置前一个节点的指针。 创建新节点 ：分配节点，设置其键为 key ，高度为随机确定的高度 h 。 链接新节点 ： 对于每一层 i（0 ≤ i < h）： 新节点的 forward[i] 指向 update[i] 在第 i 层原来的下一个节点。 update[i] 的 forward[i] 指向新节点。 更新跳跃表高度 ：如果新节点高度大于当前跳跃表的最大高度，更新头节点的高度，并将新增层的前进指针指向新节点。 示例 ：插入 15（假设随机高度 h=2） 假设当前表有元素：头节点 → 6 → 9 → 12 → 17 → 25。 查找 update 数组： 第 1 层：小于 15 的最后一个节点是 9。 第 0 层：小于 15 的最后一个节点是 12。 创建节点 15（高度 2）。 链接： 第 1 层：15 指向 9 原来的下一个（17），9 指向 15。 第 0 层：15 指向 12 原来的下一个（17），12 指向 15。 五、删除操作 目标：删除键为 key 的节点。 步骤分解： 查找待删节点 ：类似查找过程，同时记录每一层中“最后一个小于 key 的节点”的指针，存入 update 数组。 检查是否存在 ：在第 0 层，如果 update[0] 的下一个节点键等于 key ，则该节点为待删节点；否则 key 不存在，返回。 解除链接 ： 对于待删节点的每一层 i： 将 update[i] 在第 i 层的前进指针，指向待删节点在第 i 层的前进指针（即跳过待删节点）。 释放节点内存 。 更新跳跃表高度 ：如果删除的节点是最高层中的唯一节点，则降低跳跃表的高度。 示例 ：删除 9（假设 9 高度为 3） 查找 update 数组： 第 2 层：小于 9 的最后一个节点是头节点。 第 1 层：小于 9 的最后一个节点是 6。 第 0 层：小于 9 的最后一个节点是 6。 检查： update[0] （即 6）的下一个节点是 9，存在。 解除链接： 第 2 层：头节点指向 9 的下一个（如 25）。 第 1 层：6 指向 9 的下一个（12）。 第 0 层：6 指向 9 的下一个（12）。 六、复杂度分析 空间复杂度 ：平均 O(n)，每个节点平均高度约 1/(1-p) = 2（当 p=0.5）。 时间复杂度 ： 查找、插入、删除的平均时间复杂度均为 O(log n)。 最坏情况（所有节点高度都为 1）退化为有序链表，O(n)，但概率极低。 与平衡树对比：跳跃表实现简单，无需旋转等复杂操作，且天然支持区间查询（在第 0 层遍历即可）。 七、关键点总结 随机化层高 ：通过概率保证高层节点稀少，实现近似平衡。 update 数组 ：在插入和删除中记录每一层的前驱节点，是链接操作的关键。 查找路径 ：从高层向低层、从大范围向精确位置逐步逼近，是加速的本质。 通过以上步骤，你应该能理解跳跃表如何通过多层结构以简单的方式实现高效动态操作。如果你想进一步了解随机层高的数学证明或实际系统中的优化（如固定最大层高、使用确定性哈希替代随机），我们可以继续深入。