到目前為止, 我們已經介紹了兩種搜尋方式 : 順序搜尋和二分搜尋. 這兩種搜尋方式分別針對不同的資料架構. 接下來, 我們要介紹第一種有序的資料結構 : 跳躍列表 (Skip List), 它能夠提到資料搜尋的效率. 一般情況下, 二分搜尋的演算法時間複雜度為 O(\log {n}), 而跳躍列表同樣也可以達到 O(\log {n}) 時間複雜度. 相比於那些我們已經介紹過的資料結構來說, 跳躍列表算是比較遲出現的資料結構之一, 它被發明於上個世紀 90 年代. 如果你已經知道平衡樹系列的資料機構 (不知道也沒關係, 我們之後會講, 你只需要知道它們的實作非常複雜), 那麼了解完跳躍列表之後, 你就會知道跳躍列表是一個能夠在搜尋效率上媲美平衡樹但是實作又不那麼複雜的資料結構

首先, 我們需要介紹一下跳躍列表的基本結構. 跳躍列表是以前向連結串列為基礎的資料結構, 它在前向連結串列的基礎上, 增加了若干個結點 :

1. level

在第一段中, 我們已經說明了跳躍列表是一個有序的資料結構, 所以當有元素要插入一個跳躍列表, 它首先要經過比較, 找到合適的位置之後, 再配置一個新的結點插入. 這並不是重點. 跳躍列表插入時的重點在於這個結點應該帶有幾個指向下一個結點的指標. 這就涉及到跳躍列表的另外一個概念 : 級. 首先看到上面圖像中的頭部結點, 它總共帶有三個指標, 指向下一個結點. 所以它的級是 2. 第 0 級實際上就是普通的前向連結串列, 第一級和第二級中所包含的元素越來越少. 我暫時不敘述為什麼第一級及其以上連結串列存在的原因, 首先要讓大家知道, 級是如何產生的. 很簡單, 隨機產生. 也就是說, 頭部結點可以有任意級, 產生的亂數是多少, 它就有多少級. 但是, 一般來說, 我們不會讓頭部結點有任意大的級, 這是因為可能會產生下面的情況 :

過高的級不會帶來任何好處, 因為它們指向的下一個結點全都是空的, 這不但需要更多的記憶體, 還會對搜尋的效率產生很大的影響. 我們一開始就說過了, 跳躍列表是為了提高搜尋效率的資料結構. 除此之外, 這個問題不但會在頭部結點存在, 而且會在任何一個結點存在. 所以在開頭, 我特意加了一句 "在運氣不錯的情況下", 就是因為跳躍列表屬於概率型資料結構. 要是運氣不是特別好的話... 搜尋效率就大打折扣了. 所以, 我們並不能讓級的產生非常隨意, 而是要進行一定的限制

對於頭部結點的級, 我們可以讓它被結點數量牽制 : 在跳躍列表允許重複的情況下, 跳躍列表初始化時, 如果一次性插入 n 個結點, 那麼頭部結點的級不超過 n. 一般來說, 這取決於個人習慣, 比如我就喜歡把級限制在 \Theta(\log {n})

如果插入一個元素的情況下, 我們就產生一個亂數 r, 並且設定一個基準概率 p (一般來說, 概率基準並不一定是確定的, 這在實作篇中我會降到如何讓概率基準有一定的用戶發揮空間). 如果 r \leq p (也可以 r \geq p, 這並不是一定的), 那麼頭部結點的級數不變; 否則頭部結點的級數加一. 當然, 這也是有前提的, 為了防止產生多個無用的級, 當存在以下情況 :

即最大級連結串列中不存在任何元素, 亦即頭部結點的最高級結點的指標指向空指標, 那麼即使有 r \leq p 成立, 我們也不會讓級數增加

對於普通結點來說, 首先它最大的級至少不會大於頭部結點的級. 在不超過頭部結點的最大級的情況下, 產生一個亂數 r, 根據我們已經設定的基準概率 p. 如果 r \leq p, 那麼該結點擁有的級加一; 否則, 就確定當前級為該結點的級. 舉一個例子, 任意的結點都擁有第 0 級, 不然就無法構成第 0 級前向連結串列了. 現在頭部結點是 3 級, 那麼新配置結點的級至大不超過 3. 我們向跳躍列表中插入一個新的結點, 並設定概率基準 p = 0.5. 對於第一級, 我們產生的亂數為 r = 0.3, 由於 r \leq p 成立, 所以新結點至少有 1 級. 對於是否增加第二級, 我們產生的亂數為 r = 0.8, 由於 r > p, 所以我們不產生第二級. 由於不存在第二級, 所以就不再往上繼續增加級的數量了, 那麼也就設定了這個新結點的級為 1. 也就是說, 對於任意一個結點, 若存在第 i 級, 那麼必定存在第 1, 2, ..., i - 1 級. 每一個結點都必定存在第 0 級. 若存在第 i 級, 是否存在第 i + 1 的概率和我們設定的概率基準 p 有關和產生的亂數 r 有關

2. insert

對於新插入的元素, 首先要進行級的分配, 這裡不再重複累贅. 和前向連結串列一樣, 我們首先要將這個元素對應的結點插入到第 0 級連結串列中. 對於高於第 0 級的連結串列, 我們採取碰撞的方式進行. 所謂碰撞, 只是一個叫法而已, 實際上就是在對應的連結串列中找到合適的位置, 然後將這個結點插入到對應的連結串列中就可以了. 從第 0 級開始一直到這個結點擁有的最高級

不妨以上面這張圖為實例, 我們向這個跳躍列表中插入一個元素 4, 並且設定它的級為 3, 看一下具體的插入流程. 首先是向第 0 級連結串列中插入 :

Tip : 向右滑動查看, 下同

在搜尋到合適的位置之後 (3 後面, nullptr 之前), 將其插入. 插入之後如上圖所示. 接下來我們要把第 1 級到第 3 級都連結起來 :

那麼如何找到合適的位置呢? 這裡涉及到搜尋. 跳躍列表的搜尋是跳躍列表的重頭戲, 我們放在最後講. 那麼對於第 i 級連結串列來說, 我們只要找到一個位置, 這個位置之前的元素都比插入元素要小, 這個位置之後的元素都大於等於插入元素, 那麼這個位置就是合適的位置. 另外, 在第 i 級連結串列中插入, 我們並不需要去比第 i 級連結串列更低級的連結串列中搜尋, 即我們不需要在第 0, 1, ..., i - 1 級連結串列中搜尋

而要保持跳躍列表的結構, 需要的時間複雜度為 O(n)

3. erase

插入要比刪除麻煩一些, 因為我們需要尋訪每一級存在對應元素或者結點的連結串列, 然後從每一級連結串列中刪除它們. 當然, 刪除結點不需要其它操作, 只需要像在前向連結串列中刪除結點一樣刪除跳躍列表中的結點就可以了. 不過, 前向連結串列只刪除一次, 而跳躍列表中的結點需要刪除 n 次. 其中, n 是結點對應的級

4. find

在跳躍列表中進行搜尋, 就要不斷地進行跳躍

假如我們要在這個跳躍列表中搜尋 3. 首先, 我們從頭部結點的最高級出發, 向下一個結點前進 :

我們使用 cursor 表示目前到達的結點位置, 我們發現 4 並不是我們要找的元素, 因為 4 比 3 要大, 因此要搜尋的元素在 4 之前. 於是我們回到原來的位置, 也就是頭部結點, 讓級下降一層, 繼續向下一個結點前進 :

到達新位置之後, 我們還是發現, 2 並不是我們要找的元素. 又因為 3 比 2 要大, 所以要搜尋的元素在 2 之後, 於是我們從目前這個位置出發, 繼續向下一個結點前進 :

又因為 4 比 3 要大, 所以要搜尋的元素在當前結點之前, 於是我們退回原來的結點, 並且再次讓級下降一層 :

由於 4 比 3 要大, 所以再次退回原來的結點並且讓級下降一層, 並向下一個結點前進 :

我們發現, 3 就是我們要找的元素, 因此搜尋結束. 作為補充, 如果我們要尋找 2.5 的話, 由於我們已經位於第 0 級連結串列, 只需要一個一個向後尋找就可以了. 又因為前面結點對應的元素 2 比搜尋元素 2.5 要小, 後面結點對應的元素 3 比 2.5 要大, 所以我們可以確定 2.5 並不在連結串列中

對於刪除元素來說, 它首先需要找到對應元素, 所以它的時間複雜度會稍高一些, 不過和搜尋一樣都是 O(\log {n})

5. 規則的跳躍列表

我們上面所說的跳躍列表級的分配是隨心所欲的. 但是在規則的跳躍列表中, 第 i 級連結串列會有 \frac {n}{2^{i}} 個元素. 保持這樣的結構有一個好處, 就是不論在何種情況下, 搜尋同一個元素的效率都是差不多的. 但是如果對於我們上面所說的跳躍列表來說, 它的搜尋效率快還是慢, 運氣會佔到絕大部分. 若確定基準概率為 p = \frac {1}{2}, 那麼插入的新元素屬於第 i 級連結串列的概率為 \frac {1}{2^{i}}. 對應地, 把新元素插入到第 i 級連結串列中的可能性為 p^{i}. 對於一般的 p 來說, 連結串列的級數為 \left \lfloor \log_{\frac {1}{p}} {n} + 1 \right \rfloor. 在一個規則的跳躍列表中, 第 i 級連結串列包含 \frac {1}{p} 個第 i - 1 級連結串列中的結點

 

在實作篇中, 我將詳細向大家介紹如何在 C++ 中實作一個比較符合 STL 規範的跳躍列表, 在此之前, 大家可以參考一下我的程式碼 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/skip_list.hpp