跳表（Skip List）的搜索与插入操作详解 一、跳表的基本概念 跳表是一种基于有序链表的数据结构，通过添加多级索引实现快速查找。它的核心思想是以空间换时间，在普通有序链表（单层）的基础上，构建多层索引，使得搜索、插入和删除操作的时间复杂度可达到O(log n)。 二、跳表的结构组成 普通链表层（第0层） ：存储所有元素的有序链表。 索引层（第1层及以上） ：每层都是下层元素的子集，高层索引跨越更多底层节点。例如： 第1层索引可能包含第0层的一半元素。 第2层索引可能包含第1层的一半元素，以此类推。 节点结构 ：每个节点包含： 存储的值（如整数、字符串）。 一个指针数组（或列表），长度随机生成，表示该节点出现在哪些层。 三、搜索操作详解 目标 ：在跳表中查找值为 target 的节点。 步骤 ： 从最高层索引开始，向右遍历当前层的指针。 若当前层的下一个节点值小于 target ，则继续向右移动。 若下一个节点值大于或等于 target ，则下降到下一层。 重复步骤1-3，直到下降到第0层。在第0层找到等于 target 的节点则成功，否则失败。 示例 ：查找值 6 （假设跳表有3层索引）： 第2层：从头节点出发，下一个节点为 4 （<6），向右移动到 4 ；再下一个节点为 null （或>6），下降至第1层。 第1层：从 4 出发，下一个节点为 8 （>6），下降至第0层。 第0层：从 4 出发，依次经过 5 、 6 ，找到目标节点。 四、插入操作详解 核心问题 ：新节点应出现在哪些索引层？通过随机生成层数（如抛硬币法）决定。 步骤 ： 确定新节点的层数 ： 从第0层开始，每次以概率 p （如0.5）决定是否上升到更高层。 例如：连续抛硬币，直到出现“反面”则停止，连续正面的次数即为层数。 搜索插入位置并更新指针 ： 从最高层开始，记录每层中最后一个小于新节点值的节点（称为 update 数组）。 例如：插入值 6 ，层数为2，则需更新第0、1、2层中指向 6 的指针。 创建新节点并连接 ： 新节点根据层数生成指针数组。 将每层 update[i] 的指针指向新节点，新节点的指针指向原后续节点。 示例 ：插入 6 （层数=2）： update 数组记录：第2层中 4 ，第1层中 4 ，第0层中 5 。 新节点 6 的第2层指针指向 4 的原后继（如 null ），第1层指向 8 ，第0层指向 7 。 将 4 在第2层、第1层的指针指向 6 ， 5 在第0层的指针指向 6 。 五、时间复杂度与空间复杂度 时间复杂度 ： 搜索、插入、删除均为O(log n)，基于索引的层级数为O(log n)。 空间复杂度 ： 平均每个节点指针数为1/(1-p)，当p=0.5时，平均每个节点有2个指针，空间复杂度为O(n)。 六、跳表的平衡性 与平衡树（如AVL、红黑树）不同，跳表的平衡通过随机化实现，无需复杂旋转操作。 随机层数保证索引分布均匀，避免极端情况下的性能退化。 七、应用场景 Redis有序集合（Sorted Set）的底层实现。 LevelDB、RocksDB等存储引擎的MemTable。 替代平衡树实现有序数据结构，代码更简洁。 通过以上步骤，跳表以简单的随机化策略实现了高效操作，是工程中常用的有序数据结构。