数据结构:跳表-北京尧图网络

一、跳表是什么跳表Skip List是一种支持快速查找、插入和删除的有序数据结构。它的底层仍然是链表但额外建立了多层“索引链表”让查找时可以跳过大量节点。可以把它理解成普通链表逐个节点寻找跳表先大步跳跃接近目标后再小步查找思想类似二分查找但更适合动态插入和删除二、为什么普通链表查找很慢假设有一个有序链表1 → 3 → 5 → 7 → 9 → 11 → 13 → 15查找13时只能从头开始逐个比较1 → 3 → 5 → 7 → 9 → 11 → 13时间复杂度是O(n)数组可以使用二分查找达到O(log n)但数组中间插入或删除元素通常需要移动大量数据复杂度为O(n)。跳表希望同时获得查找O(log n) 插入O(log n) 删除O(log n)这些是期望时间复杂度。三、跳表的基本结构在原始链表上建立多级索引Level 3: HEAD ----------------------→ 13 Level 2: HEAD --------→ 7 ----------→ 13 Level 1: HEAD → 3 ----→ 7 → 9 -----→ 13 Level 0: HEAD → 1 → 3 → 5 → 7 → 9 → 11 → 13 → 15其中Level 0保存全部节点越高层的节点越少高层用于快速定位底层用于找到精确位置每个节点可能同时存在于多层中例如节点7的逻辑结构可能是7.forward[0] → Level 0 的下一个节点 7.forward[1] → Level 1 的下一个节点 7.forward[2] → Level 2 的下一个节点实际上它通常是一个节点持有多个前向指针并不是复制出多个节点。四、查找过程以上面的跳表为例查找11。第一步从最高层开始HEAD → 13因为13 11不能前进于是下降一层。第二步在较低层前进HEAD → 77 11移动到7。下一个节点是13超过目标于是再次下降。第三步继续逼近目标在 Level 17 → 99 11移动到9。下一步会超过目标所以继续下降。第四步在底层精确查找9 → 11找到目标。核心规则是如果右侧节点小于目标向右移动如果右侧节点大于等于目标下降一层伪代码current head 从最高层向下遍历: while current.forward[level] ! null and current.forward[level].value target: current current.forward[level] current current.forward[0] 如果 current.value target: 返回 current 否则: 返回不存在这个过程很像在二维结构中不断“向右、向下”移动。五、插入过程假设要插入8。5.1 找到每一层的前驱节点查找插入位置时记录每一层最后一个小于8的节点update[2] 7 update[1] 7 update[0] 7update数组表示新节点在每一层应该插到哪个节点后面5.2 随机生成节点高度跳表通常通过随机算法决定新节点拥有多少层以概率p 1/2为例level 0 只要抛硬币成功: level 1可能产生50% 的节点只有 Level 0 25% 的节点拥有 Level 01 12.5% 的节点拥有 Level 02 6.25% 的节点拥有 Level 03因此层数越高节点越少。5.3 修改指针假设8被随机为两层节点new.forward[0] update[0].forward[0] update[0].forward[0] new new.forward[1] update[1].forward[1] update[1].forward[1] new插入后Level 1: ... → 7 → 8 → 9 ... Level 0: ... → 7 → 8 → 9 ...重要的是寻找插入位置需要O(log n)修改指针本身只需要O(level)六、删除过程删除节点时同样先找到目标节点在每一层的前驱update[level]然后逐层检查如果 update[level].forward[level] 是目标节点: update[level].forward[level] target.forward[level]例如删除前7 → 8 → 9 删除后7 ─────→ 9如果删除后最高层已经没有任何数据节点可以降低跳表当前的最大层数。七、为什么随机层数能提高效率如果人为固定每隔两个节点建立一层索引Level 2: 1 -------→ 9 Level 1: 1 → 5 ---→ 9 → 13 Level 0: 1 → 3 → 5 → 7 → 9 → 11 → 13查找很快但插入节点后可能需要重新调整大量索引。跳表不维护严格的索引间隔而是随机决定节点高度。虽然局部结构不完全均匀但从概率上看第 0 层约有 n 个节点第 1 层约有 n × p 个节点第 2 层约有 n × p² 个节点第 k 层约有 n × pᵏ 个节点当p 1/2时n, n/2, n/4, n/8, ...这与二分查找不断缩小范围的效果类似所以期望查找复杂度为O(log n)八、时间和空间复杂度操作平均/期望复杂度最坏复杂度查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)范围查询O(log n k)O(n)空间O(n)与最大层数设置有关这里k是范围查询返回的元素数量最坏情况可能是所有节点都只有最底层跳表退化成普通链表。不过在合理随机化和最大层数限制下这种情况概率很低当p 1/2时每个节点的期望指针数量为1 1/2 1/4 1/8 ... 2所以总空间仍然是O(n)。九、跳表和其他结构的对比数据结构查找插入/删除有序遍历特点有序数组O(log n)O(n)容易缓存友好普通链表O(n)找到位置后O(1)容易查找慢哈希表平均O(1)平均O(1)不支持适合精确查询平衡树O(log n)O(log n)支持保证最坏复杂度跳表期望O(log n)期望O(log n)支持实现简单、并发友好相比哈希表跳表支持查找大于等于 x 的第一个元素查询 [left, right] 范围内的元素按顺序遍历普通哈希表通常不能高效完成这些操作。相比平衡树跳表的优点不需要旋转操作插入、删除逻辑相对直观范围遍历自然某些并发场景更容易设计平衡树的优点最坏时间复杂度有严格的O(log n)保证通常不依赖随机数每个节点的结构更加固定

数据结构:跳表

相关推荐

DalinX V12 三支柱落地实录：如何做到 C6=0、C2/C12 逐位不变的同时 C11 提升 +49%

如何设计多Agent的协作与动态切换机制？

00.01.02.tiptop:环境搭建篇（GDC客户端的搭建 GDC的HTTP方式）

更多资讯

Spring Boot民宿系统源码解析：事务边界、MyBatis映射与Vue权限拦截

STM32电机PID闭环控制：增量式算法、M法测速与调参实战

Android旅游APP毕设实战：高德地图集成与离线缓存开发

汕头30米DEM数据全流程处理：从Shapefile裁剪到Python分析

CubeSandbox 浏览器沙箱实战：在 MicroVM 中运行无头 Chromium 并用 Playwright CDP 远程驱动

STM32G431嵌入式开发：CubeMX驱动封装与BSP分层实战

今日更新

基于MATLAB的CRI显色指数计算：从SPD光谱到Ra的完整流程

JSP+Servlet+MySQL博客系统源码部署与优化全攻略

蜂窝调度算法 MATLAB 实现：比例公平、轮询与最大 C/I 对比

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？