跨越串列

在電腦科學中，跨越串列是一種資料結構。它使得包含n個元素的有序序列的尋找和插入操作的平均時間複雜度都是${\displaystyle O(\log n)}$，優於陣列的${\displaystyle O(n)}$複雜度。

跨越串列
類型	串列
發明時間	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]，其中前者更為常見。

描述

一張跨越串列的示意圖。每個帶有箭頭的框表示一個指標, 而每行是一個稀疏子序列的鏈結串列；底部的編號框（黃色）表示有序的資料序列。尋找從頂部最稀疏的子序列向下進行, 直至需要尋找的元素在該層兩個相鄰的元素中間。

跨越串列是按層建造的。底層是一個普通的有序鏈結串列。每個更高層都充當下面串列的「快速通道」，這裡在第${\displaystyle i}$層中的元素按某個固定的概率${\displaystyle p}$（通常為${\displaystyle {\frac {1}{2}}}$或${\displaystyle {\frac {1}{4}}}$）出現在第${\displaystyle i+1}$ 層中。每個元素平均出現在${\displaystyle {\frac {1}{1-p}}}$個串列中，而最高層的元素（通常是在跨越串列前端的一個特殊的頭元素）在${\displaystyle \log _{1/p}n}$個串列中出現。

在尋找目標元素時，從頂層串列、頭元素起步。演算法沿著每層鏈結串列搜尋，直至找到一個大於或等於目標的元素，或者到達當前層串列末尾。如果該元素等於目標元素，則表明該元素已被找到；如果該元素大於目標元素或已到達鏈結串列末尾，則退回到當前層的上一個元素，然後轉入下一層進行搜尋。每層鏈結串列中預期的尋找步數最多為${\displaystyle {\frac {1}{p}}}$，而層數為${\displaystyle \log _{1/p}n}$，所以尋找的總體步數為${\displaystyle -{\frac {\log _{p}n}{p}}}$，由於${\displaystyle p}$是常數，尋找操作總體的時間複雜度為${\displaystyle {\mathcal {O}}(\log n)\,}$。而通過選擇不同${\displaystyle p}$值，就可以在尋找代價和儲存代價之間取得平衡。

跨越串列不像平衡樹等資料結構那樣提供對最壞情況的效能保證：由於用來建造跨越串列採用隨機選取元素進入更高層的方法，在小概率情況下會生成一個不平衡的跨越串列（最壞情況例如最底層僅有一個元素進入了更高層，此時跨越串列的尋找與普通串列一致）。但是在實際中它通常工作良好，隨機化平衡方案也比平衡二元搜尋樹等資料結構中使用的確定性平衡方案容易實現。跨越串列在平行計算中也很有用：插入可以在跨越串列不同的部分並列地進行，而不用對資料結構進行全域的重新平衡。

實現細節

往跨越串列中插入一個元素

因為跨越串列中的元素可以在多個串列中，所以每個元素可以有多於一個指標。

跨越串列的插入和刪除的實現與普通的鏈結串列操作類似，但高層元素必須在進行多個鏈結串列中進行插入或刪除。

跨越串列的最壞時間效能具有一定隨機性，但是可以通過時間複雜度為${\displaystyle {\mathcal {O}}(n)}$的遍歷操作（例如在列印串列全部內容時）以無隨機的演算法重整串列的結構，從而使跨越串列的實際尋找時間複雜度儘量符合理論平均值${\displaystyle {\mathcal {O}}(\log n)}$。

除了使用無隨機演算法之外，我們可以以下面的准隨機方式地生成每一層：

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

類似無隨機版本，准隨機重整僅在需要執行一個${\displaystyle {\mathcal {O}}(n)}$操作（訪問每個節點）的時候伴隨進行。

歷史

跨越串列由威廉·普（英語：William Pugh）發明。^[2]發明者對跨越串列的評價是：「跨越串列是在很多應用中有可能替代平衡樹而作為實現方法的一種資料結構。跨越串列的演算法有同平衡樹一樣的漸進的預期時間邊界，並且更簡單、更快速和使用更少的空間。」

參見

• 布隆過濾器
• 跳躍圖（英語：Skip graph）

參考文獻

1. Papadakis, Thomas. Skip Lists and Probabilistic Analysis of Algorithms (PDF) (學位論文). University of Waterloo. 1993 [2018-06-03]. （原始內容 (PDF)存檔於2017-08-10）.
2. Pugh, W. Skip lists: A probabilistic alternative to balanced trees (PDF). Communications of the ACM. 1990, 33 (6): 668 [2018-06-03]. doi:10.1145/78973.78977. （原始內容存檔 (PDF)於2020-06-20）.
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 [2018-06-03]. doi:10.1145/139404.139478. （原始內容 (PDF)存檔於2021-05-06）.

外部連結

• Description （頁面存檔備份，存於網際網路檔案館） from the Dictionary of Algorithms and Data Structures
• skip lists by Thomas Niemann
• Skip List（跳躍表）原理詳解與實現 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye技術網站 （頁面存檔備份，存於網際網路檔案館）