跳表
跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除．
跳表的期望空间复杂度为 𝑂(𝑛)O(n)
，跳表的查询，插入和删除操作的期望时间复杂度都为 𝑂(log𝑛)O(logn)．
基本思想
顾名思义，跳表是一种类似于链表的数据结构．更加准确地说，跳表是对有序链表的改进．
为方便讨论，后续所有有序链表默认为 升序 排序．
一个有序链表的查找操作，就是从头部开始逐个比较，直到当前节点的值大于或者等于目标节点的值．很明显，这个操作的复杂度是 𝑂(𝑛)O(n)．
跳表在有序链表的基础上，引入了 分层 的概念．首先，跳表的每一层都是一个有序链表，特别地，最底层是初始的有序链表．每个位于第 𝑖i 层的节点有 𝑝p 的概率出现在第 𝑖 +1i+1 层，𝑝p 为常数．
记在 𝑛n 个节点的跳表中，期望包含 1𝑝1p 个元素的层为第 𝐿(𝑛)L(n) 层，易得 𝐿(𝑛) =log1𝑝𝑛L(n)=log1pn．
在跳表中查找，就是从第 𝐿(𝑛)L(n) 层开始，水平地逐个比较直至当前节点的下一个节点大于等于目标节点，然后移动至下一层．重复这个过程直至到达第一层且无法继续进行操作．此时，若下一个节点是目标节点，则成功查找；反之，则元素不存在．这样一来，查找的过程中会跳过一些没有必要的比较，所以相比于有序链表的查询，跳表的查询更快．可以证明，跳表查询的平均复杂度为 𝑂(log𝑛)O(logn)．
复杂度证明
空间复杂度
对于一个节点而言，节点的最高层数为 𝑖i 的概率为 𝑝𝑖−1(1 −𝑝)pi−1(1−p)．所以，跳表的期望层数为 ∑𝑖≥1𝑖𝑝𝑖−1(1 −𝑝) =11−𝑝∑i≥1ipi−1(1−p)=11−p，且因为 𝑝p 为常数，所以跳表的 期望空间复杂度 为 𝑂(𝑛)O(n)．
在最坏的情况下，每一层有序链表等于初始有序链表，即跳表的 最差空间复杂度 为 𝑂(𝑛log𝑛)O(nlogn)．
时间复杂度
从后向前分析查找路径，这个过程可以分为从最底层爬到第 𝐿(𝑛)L(n) 层和后续操作两个部分．在分析时，假设一个节点的具体信息在它被访问之前是未知的．
假设当前我们处于一个第 𝑖i 层的节点 𝑥x，我们并不知道 𝑥x 的最大层数和 𝑥x 左侧节点的最大层数，只知道 𝑥x 的最大层数至少为 𝑖i．如果 𝑥x 的最大层数大于 𝑖i，那么下一步应该是向上走，这种情况的概率为 𝑝p；如果 𝑥x 的最大层数等于 𝑖i，那么下一步应该是向左走，这种情况概率为 1 −𝑝1−p．
令 𝐶(𝑖)C(i) 为在一个无限长度的跳表中向上爬 𝑖i 层的期望代价，那么有：
𝐶(0)=0𝐶(𝑖)=(1−𝑝)(1+𝐶(𝑖))+𝑝(1+𝐶(𝑖−1))C(0)=0C(i)=(1−p)(1+C(i))+p(1+C(i−1))
解得 𝐶(𝑖) =𝑖𝑝C(i)=ip．
由此可以得出：在长度为 𝑛n 的跳表中，从最底层爬到第 𝐿(𝑛)L(n) 层的期望步数存在上界 𝐿(𝑛)−1𝑝L(n)−1p．
现在只需要分析爬到第 𝐿(𝑛)L(n) 层后还要再走多少步．易得，到了第 𝐿(𝑛)L(n) 层后，向左走的步数不会超过第 𝐿(𝑛)L(n) 层及更高层的节点数总和，而这个总和的期望为 1𝑝1p．所以到了第 𝐿(𝑛)L(n) 层后向左走的期望步数存在上界 1𝑝1p．同理，到了第 𝐿(𝑛)L(n) 层后向上走的期望步数存在上界 1𝑝1p．
所以，跳表查询的期望查找步数为 𝐿(𝑛)−1𝑝 +2𝑝L(n)−1p+2p，又因为 𝐿(𝑛) =log1𝑝𝑛L(n)=log1pn，所以跳表查询的 期望时间复杂度 为 𝑂(log𝑛)O(logn)．
在最坏的情况下，每一层有序链表等于初始有序链表，查找过程相当于对最高层的有序链表进行查询，即跳表查询操作的 最差时间复杂度 为 𝑂(𝑛)O(n)．
插入操作和删除操作就是进行一遍查询的过程，途中记录需要修改的节点，最后完成修改．易得每一层至多只需要修改一个节点，又因为跳表期望层数为 log1𝑝𝑛log1pn，所以插入和修改的 期望时间复杂度 也为 𝑂(log𝑛)O(logn)．
具体实现
获取节点的最大层数
模拟以 𝑝p 的概率往上加一层，最后和上限值取最小．
---|---
### 查询
查询跳表中是否存在键值为 `key` 的节点．具体实现时，可以设置两个哨兵节点以减少边界条件的讨论．
---|---
插入
插入节点 (key, value)．插入节点的过程就是先执行一遍查询的过程，中途记录新节点是要插入哪一些节点的后面，最后再执行插入．每一层最后一个键值小于 key 的节点，就是需要进行修改的节点．
---|---
### 删除
删除键值为 `key` 的节点．删除节点的过程就是先执行一遍查询的过程，中途记录要删的节点是在哪一些节点的后面，最后再执行删除．每一层最后一个键值小于 `key` 的节点，就是需要进行修改的节点．
---|---
完整代码
下列代码是用跳表实现的 map．未经正经测试，仅供参考．
参考代码
---|---
## 跳表的随机访问优化
访问跳表中第 𝑘k 个节点，相当于访问初始有序链表中的第 𝑘k 个节点，很明显这个操作的时间复杂度是 𝑂(𝑛)O(n) 的，并不足够优秀．
跳表的随机访问优化就是对每一个前向指针，再多维护这个前向指针的长度．假设 𝐴A 和 𝐵B 都是跳表中的节点，其中 𝐴A 为跳表的第 𝑎a 个节点，𝐵B 为跳表的第 𝑏b 个节点 (𝑎 <𝑏)(a<b)，且在跳表的某一层中 𝐴A 的前向指针指向 𝐵B，那么这个前向指针的长度为 𝑏 −𝑎b−a．
现在访问跳表中的第 𝑘k 个节点，就可以从顶层开始，水平地遍历该层的链表，直到当前节点的位置加上当前节点在该层的前向指针长度大于等于 𝑘k，然后移动至下一层．重复这个过程直至到达第一层且无法继续行操作．此时，当前节点就是跳表中第 𝑘k 个节点．
这样，就可以快速地访问到跳表的第 𝑘k 个元素．可以证明，这个操作的时间复杂度为 𝑂(log𝑛)O(logn)．
## 参考资料
1. [Skip Lists: A Probabilistic Alternative to Balanced Trees](https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf)
2. [Skip List](https://en.wikipedia.org/wiki/Skip_list)
3. [A Skip List Cookbook](http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf)
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/skiplist.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/skiplist.md "edit.link.title")
> __本页面贡献者：[Backl1ght](https://github.com/Backl1ght), [Tiphereth-A](https://github.com/Tiphereth-A), [Enter-tainer](https://github.com/Enter-tainer), [CookiePieWw](https://github.com/CookiePieWw), [HeRaNO](https://github.com/HeRaNO), [ksyx](https://github.com/ksyx), [Xeonacid](https://github.com/Xeonacid)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用