跳跃列表

✍ dations ◷ 2025-10-21 05:02:39 #数据结构,概率性数据结构

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

相关

  • 安哥拉历史安哥拉为非洲西南部国家。安哥拉这个词是来源于金邦杜语中的王。从考古学的角度来看,安哥拉历史开始于旧石器时代。人类最早开始居住现今安哥拉是在旧石器时代和新时期时代。
  • XHTML1.0 (Recommendation), 1.1 (Recommendation), 1.1 SE (Working Draft), 5 (Working Draft),可扩展超文本标记语言(英语:eXtensible HyperText Markup Language,XHTML),是一种标
  • 施泰尔马克州坐标:47°15′N 15°10′E / 47.250°N 15.167°E / 47.250; 15.167施泰尔马克州(德语:Steiermark),或依其英语名称译为施蒂利亚州(Styria),是奥地利的一个联邦州,位于奥地利的东南部
  • 各国森林面积列表本表旨在列出整个地球、大洲、地区、国家、省、州和地区的森林面积及相关数据,森林覆盖率的主要来源为美国中央情报局的世界概况。(km2)(km2)(km2)
  • 澳大利亚联邦银行澳大利亚联邦银行(Commonwealth Bank of Australia,ASX: CBA)是澳大利亚的一间主要银行,位列澳大利亚四大银行之一,总部位于悉尼。在澳大利亚证券交易所上市,是一间具有国际性质的
  • 苏菲·阿布·塔勒布苏菲·阿布·塔勒布(阿拉伯语:صوفى أبو طالب‎,Ṣūfī Abū Ṭālib,1925年1月27日-2008年2月21日),埃及政治人物。1978年到1983年担任埃及议会议长,1981年10月6日穆罕
  • 苏丹穆罕默德五世苏丹穆罕默德五世(马来语:Sultan Muhammad V;1969年10月6日-),本名为东古穆罕默德·伊卜尼·法里斯·伊卜尼·柏特拉,苏丹伊斯迈·伊卜尼·柏特拉之子(马来语:Tengku Muhammad Faris
  • 松浦淳六郎松浦 淳六郎(まつうら じゅんろくろう、1884年8月11日 - 1944年2月12日)为大日本帝国陆军军人。最终阶级为陆军中将。旧姓・泽井。福冈县出身。大庄屋・松浦虎作的六男。就读
  • 2013年6月逝世人物列表2013年6月逝世人物列表,是用于汇总2013年6月期间逝世人物的列表。
  • 二氧化碳激光器二氧化碳激光器(Carbon dioxide laser)是由贝尔实验室在1964年发明的世界上最早的气体激光器,也是目前使用最广泛的工业用激光。目前世界上功率最高的激光器就是以二氧化碳气