跳跃列表

✍ dations ◷ 2025-09-16 14:54:14 #数据结构,概率性数据结构

在计算机科学中,跳跃列表是一种数据结构。它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是 O ( log n ) {\displaystyle O(\log n)} ,优于数组的 O ( n ) {\displaystyle O(n)} 复杂度。

快速的查询效果是通过维护一个多层次的链表实现的,且与前一层(下面一层)链表元素的数量相比,每一层链表中的元素的数量更少(见右下角示意图)。一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间。这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择或确定性选择,其中前者更为常见。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速通道”,这里在第 i {\displaystyle i} 层中的元素按某个固定的概率 p {\displaystyle p} (通常为 1 2 {\displaystyle {\frac {1}{2}}} 1 4 {\displaystyle {\frac {1}{4}}} )出现在第 i + 1 {\displaystyle i+1} 层中。每个元素平均出现在 1 1 p {\displaystyle {\frac {1}{1-p}}} 个列表中,而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在 log 1 / p n {\displaystyle \log _{1/p}n} 个列表中出现。

在查找目标元素时,从顶层列表、头元素起步。算法沿着每层链表搜索,直至找到一个大于或等于目标的元素,或者到达当前层列表末尾。如果该元素等于目标元素,则表明该元素已被找到;如果该元素大于目标元素或已到达链表末尾,则退回到当前层的上一个元素,然后转入下一层进行搜索。每层链表中预期的查找步数最多为 1 p {\displaystyle {\frac {1}{p}}} ,而层数为 log 1 / p n {\displaystyle \log _{1/p}n} ,所以查找的总体步数为 log p n p {\displaystyle -{\frac {\log _{p}n}{p}}} ,由于 p {\displaystyle p} 是常数,查找操作总体的时间复杂度为 O ( log n ) {\displaystyle {\mathcal {O}}(\log n)\,} 。而通过选择不同 p {\displaystyle p} 值,就可以在查找代价和存储代价之间获取平衡。

跳跃列表不像平衡树等数据结构那样提供对最坏情况的性能保证:由于用来建造跳跃列表采用随机选取元素进入更高层的方法,在小概率情况下会生成一个不平衡的跳跃列表(最坏情况例如最底层仅有一个元素进入了更高层,此时跳跃列表的查找与普通列表一致)。但是在实际中它通常工作良好,随机化平衡方案也比平衡二叉查找树等数据结构中使用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用:插入可以在跳跃列表不同的部分并行地进行,而不用对数据结构进行全局的重新平衡。

因为跳跃列表中的元素可以在多个列表中,所以每个元素可以有多于一个指针。

跳跃列表的插入和删除的实现与普通的链表操作类似,但高层元素必须在进行多个链表中进行插入或删除。

跳跃列表的最坏时间性能具有一定随机性,但是可以通过时间复杂度为 O ( n ) {\displaystyle {\mathcal {O}}(n)} 的遍历操作(例如在打印列表全部内容时)以无随机的算法重整列表的结构,从而使跳跃列表的实际查找时间复杂度尽量符合理论平均值 O ( log n ) {\displaystyle {\mathcal {O}}(\log n)}

除了使用无随机算法之外,我们可以以下面的准随机方式地生成每一层:

make all nodes level 1j ← 1while the number of nodes at level j > 1 do  for each i'th node at level j do    if i is odd       if i is not the last node at level j        randomly choose whether to promote it to level j+1      else        do not promote      end if    else if i is even and node i-1 was not promoted      promote it to level j+1    end if  repeat  j ← j + 1repeat

类似无随机版本,准随机重整仅在需要执行一个 O ( n ) {\displaystyle {\mathcal {O}}(n)} 操作(访问每个节点)的时候伴随进行。

跳跃列表由威廉·普(英语:William Pugh)发明。发明者对跳跃列表的评价是:“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。”

相关

  • 肌动蛋白解聚因子肌动蛋白解聚因子(英语:Actin depolymerizing factors)是一个微丝蛋白家族, 用于调节肌动蛋白的装配与解聚。
  • 拉森拉森国家森林(英语:Lassen National Forest)是一座美国国家森林,位于加利福尼亚州东北部,占地面积1,700平方英里(4,400平方千米),名自1850年代,将此地开采、耕作,并向移居而来的人们推
  • 加丹加省加丹加省(法语:Province du Katanga)是刚果民主共和国南部的一个省,首府卢本巴希。根据新宪法,该省已于2009年2月被4个较小的省份坦噶尼喀省、上洛马米省、卢阿拉巴省、上加丹加
  • 台湾金融保险机构列表以下列出中华民国(台湾)的各种从事金融服务的机构。依照相关法规,中华民国的金融机构分为以下类型:此外,还可依法人登记地分为3种类型:本国金控人寿类非金控人寿类外商本国外商※
  • lshlsh 是一套由GNU项目 推行的,实施 SSH-2 协议的自由软件,包含服务器及客户端程序。依照secsh-srp实施远程安全密码协议,此外还包括公共密钥身份验证。Kerberos 也一定程度上得
  • 煲机老化(Burn in)是系统的零部件在放在整机运行(服务)前,进行“锻炼”的过程。这个测试过程将在监控的条件下,使各种错误产生,从而产品的负载能力能够由此创建。一般音响器材在刚购买
  • 全州神社全州神社(ぜんしゅうじんじゃ)是朝鲜日治时期坐落在全罗北道全州府(今大韩民国全罗北道全州市)的一座神社。旧社格是国币小社。祭祀天照大神・明治天皇・国魂大神。1916年(大正5
  • 希木叶尔王国希木叶尔王国(阿拉伯语:مملكة حِمْيَر‎, ,南阿拉伯字母: �����,希伯来语:.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-fami
  • 单环刺螠单环刺螠(学名:/英语俗称:penis fish),俗称海肠,胶东半岛又称海鸡子,因其形状似男性生殖器官阴茎而又俗称为阴茎鱼,是一种生活在海洋的螠虫动物。单环刺螠和其他刺螠属的生物一样,是
  • 裂果红科裂果红科共有2属19种,分布在新喀里多尼亚、马来西亚东部和澳大利亚的昆士兰州。本科植物为灌木;羽状复叶;花排成伞状花序;果实为圆柱形肉质蒴果,干燥开裂,种子有翅。本科植物木质