跳跃列表

✍ dations ◷ 2025-11-09 18:45:57 #数据结构,概率性数据结构

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

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

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

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

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

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

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

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

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

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

相关

血氧饱和仪血氧饱和仪（英语：Pulse Oximeter，简称：血氧仪），是一种主要为测量病人的血液中的脉搏氧饱和度的仪器。最初的一台血氧饱和仪由G.A. Millikan于20世纪40年代研发成功。自1980年代，美
β-受体阻滞剂β受体阻断药（英语：Beta blockers），又称Beta受体阻断药、β受体阻断剂、β受体阻滞剂、β受体拮抗剂或β阻断药、乙型阻断剂，是一类用来治疗心律不齐、防止心脏病发作后的二次心
礼烈亲王代善礼烈亲王代善（满语：ᡩᠠᡳᡧᠠᠨ，穆麟德：Daišan，太清：Daixan；1583年8月19日－1648年11月25日），清太祖努尔哈赤次子，元妃佟佳氏所生，1583年七月初三出生，清太宗皇太极之兄。他的后裔可以无
埃及猫埃及猫，中型短毛猫品种。体重2.5-5千克，是唯一天然豹纹的家猫。埃及猫的皮肤和毛色上都有像豹的斑纹。奥西猫是一种和埃及猫极相极的品种，不过奥西猫品种是人工繁殖的，只有特定
G55二连浩特－广州高速公路，简称二广高速，中国国家高速公路网编号为G55，起点在二连浩特，途经乌兰察布、大同、朔州、太原、长治、晋城、济源、洛阳、平顶山、南阳、襄阳、荆门、荆州
阿富汗经济自从塔利班政权在2001年倒台之后，阿富汗的经济前景得到了重大改善。这主要是由于超过20亿美元的国际援助，农业的恢复，以及市场机制的重新建立。2003年农业的繁荣是由于四年旱灾
美国宪法第六修正案宪法正文 I ∙ II ∙ III ∙ IV ∙ V ∙ VI ∙ VII其它修正案 XI ∙ XII ∙ XIII ∙ XIV ∙ XV XVI ∙ XVII ∙ XVIII ∙ XIX ∙ XX XXI ∙ XXII ∙ XXIII
华裔卡华裔卡，是指中华人民共和国政府可能在未来签发的一种面向海外华人群体的永久居留证件，目前相当大功能被更全面全国性的中国人才签证优惠制度所取代。据统计，中国实行改革开放以
达尔文奖章达尔文奖章（Darwin Medal）是英国皇家学会每两年颁发一次的奖项，表扬“查尔斯·达尔文对于生物学领域公认贡献，特别是进化、种群生物学、生物生物学和生物多样性方面”。该奖项于
ViuTV电视节目列表 (2010年代)本列表是ViuTV节目列表的子列表，列出2010年代的ViuTV的综艺及资讯节目。注：除特别注明外，所有节目均为高清制作且节目名称后的为该节目于其所属地区的原名(如有)。