跳跃列表

✍ dations ◷ 2025-07-06 09:55:17 #数据结构,概率性数据结构

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

相关

  • 细胞色素P450结构 / ECOD细胞色素P450(英语:cytochrome P450)超家族(官方缩写为CYP)是一大类多种多样的酶。大多数细胞色素P450酶的功能是催化氧化有机化合物。细胞色素P450的受质包括有:如脂
  • 定性研究实证主义 · 反实证主义(英语:Antipositivism) 结构主义 · 冲突理论 中层理论 · 形式理论 批判理论人口 · 团体 · 组织(英语:Organizational theory) · 社会化 社会性
  • 旅行旅行指以步行或交通工具进行的“长距离”位移,亦指为观赏不同景色及了解异与自身文化的差别而到不同城市、地区、国度或到遥远陌生地区参观、游玩、体验的文化概念。与旅游最
  • 卡尔·魏尔斯特拉斯卡尔·特奥多尔·威廉·魏尔施特拉斯(德语:Karl Theodor Wilhelm Weierstraß(发音:),姓氏可写作Weierstrass,1815年10月31日-1897年2月19日),德国数学家,被誉为“现代分析之父”。卡尔
  • 格鲁吉亚拉里拉里(格鲁吉亚语:ლარი,ISO代码:GEL),格鲁吉亚的官方货币单位。每一拉里可以分为100特瑞(英语:tetri)。“拉里”一词是一个古老的格鲁吉亚词语,含义为储藏,而“特瑞”是科尔基斯地区
  • 诘问法苏格拉底反诘法(英语:Socratic method、method of elenchus、elenctic method 或 Socratic debate)或作苏格拉底法,实质上是一种质问的辩证法,广泛地用在验证主要道德观念上。柏
  • 通加斯国家森林通加斯国家森林(英语:Tongass National Forest)位于阿拉斯加狭地,是全美国最大的国家森林。林地面积17 × 106英亩(69,000平方千米),其中大部分是世界自然基金会生态区的温带雨林,
  • 萨拉塔河萨拉塔河(乌克兰语:Сарата),是东欧的河流,流经摩尔多瓦和乌克兰,最终注入萨西克潟湖,河道全长120公里,流域面积1,250平方公里,河畔城镇有萨拉塔。
  • 阮福美垂阮福美垂(越南语:Nguyễn Phúc Mỹ Thùy/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS
  • 中国-巴勒斯坦关系中国-巴勒斯坦关系,此条目叙述的是中华人民共和国与巴勒斯坦国的双边外交关系,双方外交关系始于1965年3月22日,在中国人民外交学会主席吴学谦的主持下,巴勒斯坦解放组织驻北京办