跳跃列表

✍ dations ◷ 2025-07-27 20:00:58 #数据结构,概率性数据结构

在计算机科学中,跳跃列表是一种数据结构。它使得包含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)发明。发明者对跳跃列表的评价是:“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。”

相关

  • 血液循环循环系统(英语:circulatory system),也称为心血管系统(英语:cardiovascular system)或血管系统(英语:vascular system)是负责血液循环,在细胞间传送养分(如氨基酸及电解质)、氧气、二氧化
  • 开胸验肺张海超开胸验肺事件,是指2009年河南省新密市农民工张海超为了证明自己得的是职业病尘肺病,却多方求助无门的情况下,而自己要求开胸验肺的一个惊人之举。暴露出现在中国职业病维
  • 阿尔伯特·甘瑟阿尔伯特·卡尔·路德维希·戈特希尔夫·甘瑟(德语:Albert Karl Ludwig Gotthilf Günther,亦称Albert Charles Lewis Gotthilf Günther,1830年10月3日-1914年2月1日),又依德语译
  • 月球交点月球交点是月球的轨道交点,它是月球轨道在天球上穿越过黄道(太阳在以恒星为背景的天球上移动的路径)的位置。升交点是月球穿越黄道进入北方的点,降交点是穿越黄道进入南方的点。
  • 氙酸盐氙酸盐统称含有氙酸根离子(XeO42-)的盐类。碱金属的氙酸盐固体粉末可以通过将三氧化氙溶液与碱金属氢氧化物严格按等比混合,再经冷冻和干燥而制得。氙酸钠(NaHXeO4·1.5H2O)和氙
  • 幽灵岛幽灵岛,是在信史时期间曾经被标注在地图中,但其后人们发现其不存在,而从地图中删除的岛屿。与之相对的概念是失落岛屿,即曾经存在于传说或史前时代中,但现今并不存在的岛屿。而消
  • 皮埃尔-约瑟夫·普鲁东皮埃尔-约瑟夫·普鲁东 (法语:Pierre-Joseph Proudhon,1809年1月15日-1865年1月19日),法国互惠共生论经济学家,首位自称无政府主义者的人,也就是无政府主义的奠基人。他1840年出版的
  • 二硫化钨二硫化钨是一种无机化合物,化学式为WS2。灰色有金属光泽的细小六方晶系结晶或粉末。在空气中稳定。不溶于水,溶于硝酸和氢氟酸混酸中。溶于熔融碱,不溶于醇。钨酸铵与硫化氢气
  • 朝鲜半岛新石器时代朝鲜半岛新石器时代一般是指朝鲜半岛公元前8000年至公元前1500年的历史时期,但也有公元前7000的朝鲜半岛新石器考古发现。公元前15世纪前后,朝鲜新石器时代被青铜时所代替。朝
  • 卢卡兹·加尔古拉卢卡兹·加尔古拉(Łukasz Garguła,宽式IPA:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000