跳跃列表

维基百科,自由的百科全书
跳到导航 跳到搜索
跳跃列表
类型 列表
发明时间 1989
发明者 W. Pugh
大O符号时间复杂度
算法 平均 最差
空间 O(n) O(n log n)[1]
搜索 O(log n) O(n)[1]
插入 O(log n) O(n)
删除 O(log n) O(n)

计算机科学领域,跳跃链表是一种数据结构,允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表,且每一层链表中的元素是前一层链表元素的子集(见右边的示意图)。一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间。这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。被挑过的元素可能被随机性地选择[2]或确定性地选择,[3]其中前者更为常见。

描述[编辑]

一张跳跃列表的示意图。每个带有箭头的框表示一个指针, 而每行是一个稀疏子序列的链表;底部的编号框(黄色)表示有序的数据序列。查找从顶部最稀疏的子序列向下进行, 直至需要查找的元素在该层两个相邻的元素中间。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的「快速跑道」,这里在第层中的元素按某个固定的概率(通常为)出现在第 层中。平均起来,每个元素都在个列表中出现,而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在(即基于的对数)个列表中出现。

要查找一个目标元素,起步于头元素和顶层列表,并沿着每个链表搜索,直到到达小于或着等于目标的最后一个元素。通过跟踪起自目标直到到达在更高列表中出现的元素的反向查找路径,在每个链表中预期的步数显而易见最多为。所以查找的总体代价是,当是常数时是。通过选择不同值,就可以在查找代价和存储代价之间作出权衡。

插入和删除的实现非常像相应的链表操作,除了"高层"元素必须在多个链表中插入或删除之外。

跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证,因为用来建造跳跃列表的扔硬币方法总有可能(尽管概率很小)生成一个糟糕的不平衡结构。但是在实际中它工作的很好,随机化平衡方案比在平衡二叉查找树中用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用,这里的插入可以在跳跃列表不同的部分并行的进行,而不用全局的数据结构重新平衡。

实现细节[编辑]

往跳跃列表中插入一个元素

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

operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to search time. (Choose the level of the i'th finite node to be 1 plus the number of times we can repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as we have the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them.

除此之外,我们可以以下面的方式准随机地生成每一层:

make all nodes level 1
j ← 1
while 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 + 1
repeat

近似于无随机版本,准随机仅在需要运行一个操作(访问每个节点)的时候进行。

历史[编辑]

跳跃列表由 William Pugh 发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees,在其中详细描述了他的工作。参见 引用下载文档

引用发明者的话:

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。

参见[编辑]

参考文献[编辑]

  1. ^ 1.0 1.1 Papadakis, Thomas. Skip Lists and Probabilistic Analysis of Algorithms (PDF) (Ph.D.). University of Waterloo. 1993. 
  2. ^ Pugh, W. Skip lists: A probabilistic alternative to balanced trees (PDF). Communications of the ACM. 1990, 33 (6): 668. doi:10.1145/78973.78977. 
  3. ^ Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert. Deterministic skip lists (PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA: 367–375. 1992. doi:10.1145/139404.139478. 

外部链接[编辑]