摘要訊息 : 可以跳躍的前向連結串列.

0. 前言

在前項連結串列 (《【資料結構】前向連結串列》) 中進行二分搜尋 (《【演算法】二分搜尋法 (Binary Search)》) 的話, 雖然時間複雜度仍然可以視為 \Theta(\log {n}), 但是搜尋的效能要比在連續儲存的向量 (《【資料結構】向量 (順序表)》) 要低不少. 因為在前向連結串列中, 一次只能向前進一步, 而向量可以隨機訪問任意位置. 在計算時間複雜度的時候, 我們像《【資料結構】前向連結串列》中那樣不把結點前進的步伐進入. 如果前項連結串列本身就有序, 我們希望可以通過修改前向連結串列的尋訪方式, 使得在前向連結串列中搜尋的時間複雜度 \Theta(\log {n}) 可以和在向量中進行二分搜尋的時間複雜度 \Theta(\log {n}) 相媲美.

更新紀錄 :

• 2022 年 5 月 17 日進行第一次更新和修正.

1. 對數級別時間複雜度?

在前向連結串列中進行二分搜尋, 雖然我們可以其時間複雜度視為 \Theta(\log {n}), 但是實際的時間複雜度是多少呢?

我們採用《程式碼效能分析》中第 3 節中的列表法來計算在前向連結串列中進行二分搜尋的實際時間複雜度. 我們首先使用 C++ 寫出對應的程式碼 :

struct node {
    int value;
    node *next;
};

int distance(node *begin, node *end = nullptr) {
    auto d {0};
    for(; begin not_eq end; ++d, static_cast<void>(begin = begin->next));
    return d;
}
node *advance(node *begin, int distance) {
    for(; distance-- not_eq 0; begin = begin->next);
    return begin;
}
node *binary_search(node *begin, node *end, int value) {
    auto left {0}, right {distance(begin, end) - 1};
    while(left <= right) {
        const auto mid {(right + left) / 2};
        const auto mid_node {advance(begin, mid)};
        const auto &node_value {mid_node->value};
        if(node_value == value) {
            return mid_node;
        }else if(node_value < value) {
            left = mid + 1;
        }else {
            right = mid - 1;
        }
    }
    return nullptr;
}

陳述式	運作步伐	頻率	陳述式總步伐
node *binary_search(node *begin, node *end, int value)	0	0	0
auto left {0}, right {distance(begin, end) - 1};	n + 2	1	n + 2
while(left <= right)	1	\Theta(\log {n})	\Theta(\log {n})
const auto mid {(left + right) / 2};	1	\Theta(\log {n})	\Theta(\log {n})
const auto mid_node {advance(begin, mid)};	\Theta(\log {n}) + 1	\Theta(\log {n})	\Theta(\log {n})(\Theta(\log {n}) + 1)
const auto &node_value {mid_node->value};	1	\Theta(\log {n})	\Theta(\log {n})
if(mid_value == value) {	\frac {1}{3}	\Theta(\log {n})	\frac {1}{3}\Theta(\log {n})
return mid_node;	\frac {1}{2}	1	\frac {1}{2}
}else if(node_value < value) {	\frac {1}{3}	\Theta(\log {n})	\frac {1}{3}\Theta(\log {n})
left = mid + 1;	1	\frac {1}{3}\Theta(\log {n})	\frac {1}{3}\Theta(\log {n})
}else {	\frac {1}{3}	\Theta(\log {n})	\frac {1}{3}\Theta(\log {n})
right = mid - 1;	1	\frac {1}{3}\Theta(\log {n})	\frac {1}{3}\Theta(\log {n})
}	0	0	0
}	0	0	0
return nullptr;	\frac {1}{2}	1	\frac {1}{2}
}	0	0	0
程式步伐總計	n + \Theta(\log^{2}{n}) + \frac {17}{3}\Theta(\log {n}) + 3

雖然 \Theta(\log^{2}{n}) = O(n), 但是 \Theta(\log^{2}{n}) \neq \Omega(n). 所以根據《漸近分析基礎》中的定義 1, 即大 O 記法的定義, 最終 Code 1 中函式 binary_search 的時間複雜度為 O(n). 對比第 0 節中的粗糙結論, 這個結論是非常精確的. 準確地說, 在前向連結串列中進行二分搜尋的時間複雜度並不是對數級別的, 其上限應該是線性級別的.

那麼是否有可能小幅度地更改前向連結串列中指向型標記, 使得在前向連結串列中搜尋 (不再是二分搜尋) 的時間複雜度真正保持在 \Theta(\log {n})?

2. 跳躍列表

定義 1. 我們稱有序向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} : \alpha_{1} \leq \alpha_{2} \leq ... \leq \alpha_{n} \right \} 的擴展 \boldsymbol {\alpha} = \left \{ (p_{1}^{0}, p_{2}^{0}, ..., p_{m_{0}}^{0}), \big ( \alpha_{1}, (p_{1}^{1}, p_{2}^{1}, ..., p_{m_{1}}^{1}) \big ), \big ( \alpha_{2}, (p_{1}^{2}, p_{2}^{2}, ..., p_{m_{2}}^{2}) \big ), ..., \big ( \alpha_{n}, (p_{1}^{n}, p_{2}^{n}, ..., p_{m_{n}}^{n}) \big ) \right \} 為跳躍列表 (skip list, 又稱跨越串列). 其中, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) 為第 i 個結點的指向型標記組; m_{i} 為第 i 個結點指向型標記組中指向型標記的數量, 1 \leq i \leq n; p_{j}^{i} 必須指向排列在第 i 個結點之後的結點; m_{0} = \max \left \{ p_{m_{1}}^{1}, p_{m_{2}}^{2}, …, p_{m_{n}}^{n} \right \}.

指向型標記的定義見《【資料結構】前向連結串列》第 1 節. 本篇文章中, 我們主要討論的是元素升序排序的的跳躍列表, 也就是跳躍列表中的元素從小到大對排列. 對於降序的情況, 類似可得.

和前向連結串列相比, Figure 1 中的跳躍列表中每一個結點多了幾個指向型標記. 除了最低層的指向型標記之外, 高層的指向型標記都是不一定按照順序指向下一個結點, 這便是跳躍的由來. 再仔細觀察 Figure 1 和定義 1, 我們會發現這個跳躍列表的結點其實和前向連結串列是不同的, 因為 Figure 1 中的跳躍列表中多了一個頭部結點, 這個頭部結點只是一個指向型標記組, 不存在元素. 跳躍列表的 “跳躍” 操作正是依賴於 (p_{1}^{0}, p_{2}^{0}, ..., p_{m_{0}}^{0}) 這個結點.

2. 跳躍列表的級

定義 2. 我們稱跳躍列表 \boldsymbol {\alpha} = \big \{ (p_{1}^{0}, p_{2}^{0}, ..., p_{m_{0}}^{0}), \big ( \alpha_{1}, (p_{1}^{1}, p_{2}^{1}, ..., p_{m_{1}}^{1}) \big ), \big ( \alpha_{2}, (p_{1}^{2}, p_{2}^{2}, ..., p_{m_{2}}^{2}) \big ), ..., \big ( \alpha_{n}, (p_{1}^{n}, p_{2}^{n}, ..., p_{m_{n}}^{n}) \big ) \big \} 為跳躍列表 (skip list). 其中, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) 中的 \max \left \{ p_{m_{1}}^{1}, p_{m_{2}}^{2}, ..., p_{m_{n}}^{n} \right \} 為跳躍列表 \boldsymbol {\alpha} 的級 (level).

根據定義 2, 換句話說, 跳躍列表的級就是那個指向型標記最多的那個結點中指向型標記的數量, 即 m_{0}. 那麼 Figure 1 中這個跳躍列表的級為 4.

定義 2'. 我們稱 m_{0} 為跳躍列表 \boldsymbol {\alpha} 的級, 其中 \boldsymbol {\alpha} = \big \{ (p_{1}^{0}, p_{2}^{0}, ..., p_{m_{0}}^{0}), \big ( \alpha_{1}, (p_{1}^{1}, p_{2}^{1}, ..., p_{m_{1}}^{1}) \big ), \big ( \alpha_{2}, (p_{1}^{2}, p_{2}^{2}, ..., p_{m_{2}}^{2}) \big ), ..., \big ( \alpha_{n}, (p_{1}^{n}, p_{2}^{n}, ..., p_{m_{n}}^{n}) \big ) \big \}.

定義 3. 對於跳躍列表中的某個結點 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ), 我們稱 m_{i} 為該結點的級.

根據定義 2, 顯然當 m_{0} = 1 的時候, 這個跳躍列表就是一個前項連結串列. 除此之外, 如果把其它級無視, 只看第 k 級的話, 那麼第 k 級也代表了一個前向連結串列. 也就是說, 跳躍列表中的每一級都代表了一個前項連結串列.

2.1 跳躍搜尋

在前向連結串列中搜尋元素, 必須按照指向型標記的指向, 在相鄰的向後結點中進行搜尋. 對於有序的元素排列, 向相鄰的後結點一步一步前進是前向連結串列搜尋的效能瓶頸. 而跳躍列表允許在結點之間進行跳躍, 因此我們可以通過條約的方法進行搜尋.

在 Figure 1 中, 如果我們想要搜尋 2, 那麼首先從跳躍列表最高的級, 即第 4 級開始搜尋. 從第 4 級向後跳躍, 到達元素為 4 的結點. 由於 2 < 4, 所以即使 4 後面還有元素, 那些元素必定至少大於等於 4, 再向後跳躍搜尋是沒有意義的, 於是我們把搜尋級別降低一級. 現在從第 3 級向後跳躍, 到達元素為 2 的結點, 於是我們找到了 2 所在的位置.

但是如果想要搜尋 2.5 的話, 就需要再進行兩次跳躍. 在 Figure 2 的基礎上, 我們發現到達的元素 2 < 2.5. 所以需要在元素為 2 的結點上向後進行跳躍, 到達元素為 4 的結點, 然而 2.5 < 4, 所以需要再次將搜尋級別降低一級. 即使再降低一級, 仍然會遇到相似的情況, 跳躍到元素為 4 的結點, 那麼繼續把搜尋級別降低一級. 這個時候, 搜尋級別已經在最低一級, 也就是第一級了. 向後跳躍到達元素為 3 的結點, 但是 2.5 < 3. 此時, 我們斷定 : 元素 2.5 並不在這個跳躍列表中.

而在跳躍列表中搜尋元素所需要的輔助空間和元素數量無關, 所以 Algorithm 1 的空間複雜度為 \Theta(1). 而搜尋的時間複雜度是依賴於級如何產生的.

2.2 級的產生

如果一個跳躍列表中元素不多, 但是級很高, 會產生怎麼樣的現象呢?

Figure 3 中的跳躍列表級為 11. 要搜尋元素, 我們需要不斷從第 11 級慢慢下降到第 4 級, 這個時候搜尋才真正開始. 因為第 4 級以上的級, 向後跳躍沒有任何意義, 這些指向型標記沒有指向任何結點. 這對於搜尋沒有任何幫助, 不但會佔用額外的空間, 還拖慢了搜尋的效能. 為此, 級並不能隨意增高. 那麼是否有一個比較好的方案來產生或者增高級呢?

首先我們要明確, 對於跳躍列表 \boldsymbol {\alpha} = \big \{ (p_{1}^{0}, p_{2}^{0}, ..., p_{m_{0}}^{0}), \big ( \alpha_{1}, (p_{1}^{1}, p_{2}^{1}, ..., p_{m_{1}}^{1}) \big ), \big ( \alpha_{2}, (p_{1}^{2}, p_{2}^{2}, ..., p_{m_{2}}^{2}) \big ), ..., \big ( \alpha_{n}, (p_{1}^{n}, p_{2}^{n}, ..., p_{m_{n}}^{n}) \big ) \big \} 中的 m_{0} 是和其中一個結點的指向型標記數量相等的. 對於一個新插入的結點, 我們以機率 p 對級進行不斷增高. 我們以一定的方法產生某個亂數 r, 且 r 滿足 r \in [0, 1]. 如果 r < p (又或者 r > p), 那麼就為新插入結點增加一個指向型標記; 如果 r \geq p (又或者 r \leq p), 那麼新插入結點指向型標記的增加停止. 除此之外, 我們還需要考慮一種情況, 就是新插入結點的指向型標記比 m_{0} 還大. 在這種情況下, 我們僅允許新插入結點的指向型標記數量比 m_{0} 大 1. 也就是當新插入結點的指向型標記數量為 m_{0} + 1 的時候, 新插入結點指向型標記的增加也要停止. 這個時候, 頭部結點的指向型標記組也需要增借一個新的指向型標記.

那麼如果令機率 p = \frac {1}{2}, 在擁有大量元素的跳躍列表中級一般處於什麼級別呢? 我編寫的跳躍列表級的產生採用了 Algorithm 2. 對於不同的元素數量級別, 我生成了十次跳躍列表, 每一次都將跳躍列表的級記錄下來, 最終取級總和的平均數 :

一般來說, 跳躍列表中的任意結點的指向型標記數量一旦固定, 也就是某個結點的級一旦固定, 就不會對其進行更改. 相比於較低級的前項連結串列, 跳躍列表中級越高的前向連結串列中的元素通常也越少.

一般來說, 級產生的機率 p 一般設為 p = \frac {1}{2}. 這是前輩們經過實驗得到的經驗結論.

2.3 跳躍搜尋的時間複雜度

我們並沒有在第 2.1 節作出時間複雜度的斷言, 因為跳躍列表的時間複雜度是依賴於級產生的方式的, 而且證明需要用到級產生過程中的固定機率 p.

斷言 1. 在跳躍列表中搜尋元素的演算法 Algorithm 1 的時間複雜度是機率 \Theta(\log {n}) 的.

證明 :

TODO

3. 插入

對於新插入的元素 e, 首先要使用 Algorithm 2 確定這個元素所產生結點的級 l. 現在產生了一個新的結點 \big ( e, (p_{1}, p_{2}, ..., p_{l}) \big ). 目前, p_{1} = p_{2} = ... = p_{l} = \infty.

首先, 如果 l = m_{0} + 1 話, 我們要為頭部節點增加一個指向型標記 p_{m_{0} + 1}^{0}, 並且使其指向 \big ( e, (p_{1}, p_{2}, ..., p_{l}) \big ), 即 p_{m_{0} + 1}^{0} = \big ( e, (p_{1}, p_{2}, ..., p_{l}) \big ). 最後令 p_{l} = \infty. 接下來我們處理 l \leq m_{0} 的情形.

對於第 k 級 (k = 1, 2, ..., m_{0}), 我們只要找到在這個級上兩個相鄰結點 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ) 和 \big ( \alpha_{j}, (p_{1}^{j}, p_{2}^{j}, ..., p_{m_{i}}^{j}) \big ) 使得 \alpha_{i} < e 成立但是 \alpha_{j} < e 不成立, 那麼我們就可以把 e 安排到它們之間. 其中, p_{i}^{k} = \big ( \alpha_{j}, (p_{1}^{j}, p_{2}^{j}, ..., p_{m_{i}}^{j}) \big ). 我們令 p_{k} = p_{i}^{k} = \big ( \alpha_{j}, (p_{1}^{j}, p_{2}^{j}, …, p_{m_{i}}^{j}) \big ), 再令 p_{k}^{i} = \big ( e, (p_{1}, p_{2}, …, p_{l}) \big ). 這裡有一個特殊情況, 就是 \alpha_{i} 是該級中最大的元素, 自然也就不存在 \big ( \alpha_{j}, (p_{1}^{j}, p_{2}^{j}, ..., p_{m_{i}}^{j}) \big ). 換句話說, p_{k}^{i} = \infty. 但是這種情況我們不需要特殊處理, 因為 p_{k} = p_{k}^{i} 會使得 p_{k} 指向 \infty, 這仍然是正確的.

有一點需要特別指出的是, 當我們完成在第 k 級的連結重設之後, 對於第 k - 1 級我們並不需要從頭去搜尋適當的位置. 根據 Algorithm 2, 若第 k 級存在, 必定也存在第 1, 2, ..., k - 1 級. 因為只有當 k - 1 級產生的時候, 這個結點才有機會進入第 k 級; 否則, 它連進入第 k 級的資格都不會有. 所以在第 k 級的插入完成之後, 我們只需要在當前結點下降一級, 再往後搜尋滿足 \alpha_{i} < e 成立但是 \alpha_{j} < e 不成立的相鄰結點 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ) 和 \big ( \alpha_{j}, (p_{1}^{j}, p_{2}^{j}, ..., p_{m_{i}}^{j}) \big ) 即可.

例題 1. 在 Figure 1 中插入元素 2.5, 其級為 3.

解 :

首先配置結點 \big ( 2.5, (p_{1}, p_{2}, p_{3}) \big ). 其中, p_{1} = p_{2} = p_{3} = \infty.

一開始, 我們向 p_{4}^{0} 指向的結點前進, 但是我們發現 4 > 2.5 而且新結點沒有第 4 級, 所以我們下降一級. p_{3}^{0} 指向了結點 \big ( 2, (p_{1}^{3}, p_{2}^{3}, p_{3}^{3}) \big ). 由於 2 < 2.5, 所以我們在這一級上繼續尋找合適的位置. p_{3}^{3} 指向了元素為 4 的結點, 由於 2 < 2.5 < 4, 所以新結點應該在這一級中插入到它們之間, 即令 p_{3} = p_{3}^{3}, 然後令 p_{3}^{3} = \big ( 2.5, (p_{1}, p_{2}, p_{3}) \big ).

第 3 級的重設完成, 要下降一級到第 2 級. 這一級的情況和第 3 級是類似的, 我們令 p_{2} = p_{2}^{3} 且 p_{2}^{3} = \big ( 2.5, (p_{1}, p_{2}, p_{3}) \big ).

最後下降到第 1 級. p_{1}^{3} 指向了元素為 3 的結點, 同樣有 2 < 2.5 < 3, 因此我們令 p_{1} = p_{1}^{3} 且 p_{1}^{3} = \big ( 2.5, (p_{1}, p_{2}, p_{3}) \big ).

最終, 整個跳躍列表的有序性和正確性得到了維護.

\blacksquare

例題 1'. 在 Figure 1 中插入元素 2.5, 其級為 5.

解 :

首先配置結點 \big ( 2.5, (p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) \big ). 其中, p_{1} = p_{2} = p_{3} = p_{4} = \infty. 然後還要為頭部節點增加一個新的指向型標記 p_{5}^{0} 並將其指向 \big ( 2.5, (p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) \big ), 即 p_{5}^{0} = \big ( 2.5, (p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) \big ). 然後讓 p_{5} = \infty.

接下來處理第 4 級, 由於 p_{4}^{0} 指向了元素為 4 的結點且 2.5 < 4, 所以令 p_{4} = p_{4}^{0} 且 p_{4}^{0} = \big ( 2.5, (p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) \big ).

下面的處理和例題 1' 中是類似的. 最終整個跳躍列表的有序性和正確性得到了維護.

\blacksquare

向跳躍列表中插入元素所需要的輔助空間和原跳躍列表中擁有的元素是沒有關係的, 所以空間複雜度為 \Theta(1). 向跳躍列表中插入元素必須要搜尋到合適的插入位置, 這裡的時間複雜度為 \Theta(\log {n}). 設新插入元素帶有 l 個指向型標記, 那麼就需要調整 l 級的連結. 在每一級中找到需要調整的結點所需要的時間複雜度為 \Theta(\log {n}). 總體來說, 在跳躍列表中插入元素的時間複雜度為 \Theta(l) \cdot \Theta(\log {n}) = \Theta(l\log {n}).

4. 移除

如果要求從一個跳躍列表中移除指定的結點 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ), 我們需要在第 k 級中找到哪一個結點的指向型標記 p_{k}^{j} 連結到了 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ), 即 p_{k}^{j} = \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ). 然後令 p_{k}^{j} = p_{k}^{i} 即可. 對於 k = 1, 2, ..., m_{i}, 我們都採取類似的處理方法. 最終結點 \big ( \alpha_{i}, (p_{1}^{i}, p_{2}^{i}, ..., p_{m_{i}}^{i}) \big ) 就會從跳躍列表中被移除. 這種是以搜尋連結的方法對跳躍列表的連結進行重設, 以達到移除結點的目的.

例題 2. 從 Figure 1 中移除結點 \big ( 2, (p_{1}^{3}, p_{2}^{3}, p_{3}^{3}) \big ).

解 :

首先在第三級中, 是頭部結點連結到了 \big ( 2, (p_{1}^{2}, p_{2}^{2}, p_{3}^{2}) \big ), 也就是說 p_{3}^{0} = \big ( 2, (p_{1}^{2}, p_{2}^{2}, p_{3}^{2}) \big ). 此時, 我們令 p_{3}^{0} = p_{3}^{2} = \big ( 4, (p_{1}^{5}, p_{2}^{5}, p_{3}^{5}, p_{4}^{5}) \big ). 即我們在第三級中把頭部結點和 \big ( 4, (p_{1}^{5}, p_{2}^{5}, p_{3}^{5}, p_{4}^{5}) \big ) 這個結點連結起來了.

在第二級中, p_{2}^{2} 連結到了 \big ( 2, (p_{1}^{2}, p_{2}^{2}, p_{3}^{2}) \big ), 我們令 p_{2}^{2} = p_{2}^{3} = \big ( 4, (p_{1}^{5}, p_{2}^{5}, p_{3}^{5}, p_{4}^{5}) \big ).

在第一級中, p_{1}^{2} 連結到了 \big ( 2, (p_{1}^{2}, p_{2}^{2}, p_{3}^{2}) \big ), 我們令 p_{1}^{2} = p_{1}^{3} = \big ( 3, p_{1}^{3}) \big ).

最終, 回收結點 \big ( 2, (p_{1}^{2}, p_{2}^{2}, p_{3}^{2}) \big ) 之後, 跳躍列表仍然有序且正確.

\blacksquare

如果跳躍列表中的元素數量很多, 那麼通過在某一級中通過搜尋連結的方式重設連結是需要尋訪不少結點的. 而且級數越低, 需要尋訪的結點就越多. 而且有時候, 我們可能只能得到要移除的是跳躍列表中的某個元素, 而不知道要移除哪一個結點. 這個時候, 採用 Algorithm 4 那樣搜尋連結的方式就不太現實. 在知道要被移除的結點元素為 e 的情況下, 我們可以借助類似於 Algorithm 1 的搜尋元素方式來提高搜尋的效能. 對於允許元素重複的跳躍列表, 我們預設要移除的是搜尋過程中第一次遇到的那一個. 以元素為基礎的搜尋實際上的目的是找到高度接近 e 但是小於 e 的結點.

另外我們要知道, 如果某個結點有第 l 級, 那麼必有第 1, 2, ..., l - 1 級. 因為根據 Algorithm 2, 只有在第 k 級被產生的情況下, 才有機率產生第 k + 1 級.

例如我們要在 Figure 7 中移除元素為 4 的結點, 最接近它的是元素為 3 的結點. 如果按照 Algorithm 4 中的演算法, 連結重設從第 5 級開始. 從第 5 級降低到第 1 級, 每一級分別需要尋訪的結點數量為 3, 5, 7, 8, 9 個, 總計要尋訪 32 個結點. 而如果按照跳躍搜尋的方式, 我們從頭部結點跳到第三個 0, 由於接下來沒有連結任何結點, 所以要下降一級. 下面一級同樣沒有連結任何結點, 所以要再下降一級. 這裡尋訪了四個結點, 其中兩個是空的結點, 即 \infty. 接下來跳躍到第一個 1, 再往後我們就找到了要移除的結點, 這裡尋訪了兩個結點. 在處理完第五級的連結之後, 下降到第四級, 同樣的處理方式, 尋訪了一個結點. 現在下降到第三級, 由於接下來的元素是 3, 所以前進到 3 對應的結點, 再向後尋訪一個結點就又遇到了 4, 這裡尋訪了兩個結點. 最後第一級和第二級是和第三級一樣的處理方式, 這裡尋訪了兩個結點. 通過計算總和, 我們尋訪了 11 個結點, 比之前 33 個結點要少得多!

例題 3. 從 Figure 7 中移除元素 4.

解 :

在第 7 級中, p_{7}^{0} 連結到了結點 \big ( 0, p_{1}^{3}, p_{2}^{3}, ..., p_{7}^{3} \big ). 因為 0 < 4, 所以還需要在第 7 級上向前進. 由於 p_{7}^{3} = \infty, 需要下降一級到達. 但是 p_{6}^{3} = \infty, 所以還需要再下降一級. p_{6}^{3} 連結到了結點 \big ( 1, (p_{1}^{5}, p_{2}^{5}, ..., p_{5}^{5}) \big ). 因為 1 < 4, 因此向前進到達 p_{5}^{5}, 這就是我們第一次遇到 4, 因此設定 \big ( 4, (p_{1}^{9}, p_{2}^{9}, ..., p_{5}^{9}) \big ). 接下來令 p_{5}^{5} = p_{9}^{5} = \infty.

在 p_{5}^{5} 上下降一級, 到達 p_{5}^{4}. 由於 p_{5}^{4} 連結的就是我們要移除的結點, 所以令 p_{5}^{4} = p_{9}^{4} = \infty.

再下降一級到達 p_{5}^{3}, 由於它連結的結點中的元素為 3, 而 3 < 4, 所以在第 3 級上向前進. 我們發現 p_{8}^{3} 連結的是我們要移除的結點, 所以令 p_{8}^{3} = p_{9}^{3} = \infty. 在下降到第 2 級和第 1 級上, 令 p_{8}^{2} = p_{9}^{2} = \infty 且 p_{8}^{1} = p_{9}^{1} = \infty.

最終, 結點 \big ( 4, (p_{1}^{9}, p_{2}^{9}, ..., p_{5}^{9}) \big ) 就從跳躍列表中被移除了.

\blacksquare

不論是哪一種移除方式, 所需要的輔助空間都和元素數量 n 無關, 所以從跳躍列表移除結點或者元素的空間複雜度為 \Theta(1). 在跳躍列表的非第一級中重新進行連結需要尋訪 \Theta(\log {n}) 個結點. 對於第一級, Algorithm 4 至多需要尋訪 n 個結點, 至少需要尋訪 1 個結點; 而 Algorithm 5 在第一級中只需要尋訪 O(\log {n}) 個結點. 所以採用搜尋連結的方法在第一級中重設連結的時間複雜度為 \Theta(n), 而採用搜尋元素的方法在第一級中重設連結的時間複雜度為 \Theta(\log {n}). 設被移除的結點擁有 l 個指向型標記, 那麼採用搜尋連結的方式從跳躍列表中移除元素的時間複雜度為 \Theta((l - 1)\log {n}) + \Theta(n) = \Theta(n). 如果採用搜尋元素的方式, 從跳躍列表中移除元素的時間複雜度為 \Theta(\log {n}).

5. 和跳躍列表有關的演算法

由於跳躍列表中的元素是有序的, 雖然它是屬於線性的資料結構, 旋轉這樣的演算法是不能用於跳躍列表的. 字典比較可以用於跳躍列表, 我們只需要在第 1 級中進行尋訪即可, 這個時候它會退化為一個前項連結串列. 關於跳躍列表的字典比較, 可以參考《【資料結構】向量 (順序表)》, 這裡不再累贅.

6. C++ 實作

本節僅建議 C++ 基礎較好的讀者閱讀.

因為 C++ 標準樣板程式庫中沒有跳躍列表這個資料結構, 所以在本節中, 我們將使用 C++ 實作一個類似於 C++ 標準樣板程式庫容器的跳躍列表.

6.1 疊代器

要實作這樣一個容器, 首先就要實作它的疊代器. 跳躍列表本質上是一個前向連結串列, 因此它的疊代器應該是前向疊代器. 不過在此之前, 我們需要明確跳躍列表每個結點的具體結構 :

template <typename T>
struct skip_list_node {
public:
    T value;
    skip_list_node **next;
    size_t max_level;
};

其中, 成員變數 max_level 既表示了該節點的最高的級, 同時也表示了成員變數 next 的動態陣列大小.

對於跳躍列表的疊代器, 我們將其宣告如下 :

template <typename T, bool IsConst>
class skip_list_iterator;

第二個樣板參數 IsConst 代表這個疊代器是否為不可更改內容的疊代器, 即是否為標準樣板程式庫容器中的 const_iterator. 根據 C++ 標準樣板程式庫的規範, 每個疊代器都有一個名為 iterator_category 的別名, 表示疊代器的類型. 那麼在跳躍列表中, 這個別名應該是 using iterator_category = std::forward_iterator_tag;. 這個疊代器應該有兩個成員 : skip_list_node<T> *node 和 std::size_t level. 其中, node 表示目前位於哪一個結點, level 表示目前疊代器位於結點中的哪一級. 那麼其多載的 operator== 不僅要比較兩個疊代器是否處在同一個結點, 同時也應該比較是否處在同一級. 除了建構子和解構子之外, 它應該具備多載的 operator*, operator-> 和 operator++. 其中, skip_list_iterator<T, false> 還應該具備向 skip_list_iterator<T, true> 發生隱含型別轉化的能力. 不過光具備上述操作可能無法滿足我們的全部要求, 因為我們還需要調整疊代器的級. 此處, 我為其增加了兩個多載運算子 :

skip_list_iterator<T, IsConst> &skip_list_iterator<T, IsConst>::operator+() & noexcept {
    ++this->level;
    return *this;
}
skip_list_iterator<T, IsConst> &skip_list_iterator<T, IsConst>::operator-() & noexcept {
    --this->level;
    return *this;
}

這個是所有 C++ 標準樣板程式庫中容器的疊代器都不具備的, 這也說明了跳躍列表的特殊性. 除了這些需要額外說明的之外, 剩下的都是非常簡單的, 大家可以自行嘗試實作.

6.2 跳躍列表的結構

跳躍列表除了需要明確型別之外, C++ 標準樣板程式庫還要求每一個容器的樣板引數都可以接受一個空間配置器以自訂記憶體配置操作. 此處, 我們暫時不考慮記憶體配置自訂, 閣下可以統一使用 std::operator new (std::malloc) 和 std::operator delete (std::free) 來替代. 由於跳躍列表的特殊性, 它本身是一個有序的容器, 因此它還需要進行比較. 跳躍列表需要產生一個級, 這裡使用到了亂數生成. 將這個生成的機率亂數和標準機率進行比較, 於是我們還需要一個機率的產生器. 總結這些, 我們得到了跳躍列表的宣告 :

#include <random>
#include <functional>

struct skip_list_probability_generator {
    constexpr double operator()() const noexcept {
        return 0.5;
    }
};
struct skip_list_random_number_generator {
    double operator()() const noexcept {
        static std::random_device d {};
        static std::default_random_engine e(d());
        static std::uniform_real_distribution<double> u(0.0, 1.0);
        return u(e);
    }
};

template <typename T, /* typename Allocator = std::allocator<T> */, typename Compare = std::less<T>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list;

每一次在用到 std::less<T>, skip_list_probability_generator 和 skip_list_probability_generator 的時候, 如果都要去建構對應的物件將會耗費不少時間, 因此我們直接將其作為跳躍列表的成員變數. 但是如果直接將它們作為跳躍列表的成員變數, 這必定會影響到 skip_list 的靜態大小, 即 sizeof 值變得很大. 我們希望盡力壓縮它的靜態大小, 而預設的 std::less<T>, skip_list_probability_generator 和 skip_list_probability_generator 它們都不存在成員, 因此可以通過繼承的方式來壓縮. 這就是 C++ 中的空基礎類別壓縮技術. 如果給定的三個類別都不是無狀態的 (也就是它們存在成員變數或者存在虛擬成員函式等情況), 那麼它們是無法使用空基礎類別壓縮的 :

template <typename Compare, typename Random, typename Probability, bool, bool, bool>
struct skip_list_compress_auxiliary {
public:
    Compare c;
    Random r;
    Probability p;
public:
    constexpr skip_list_compress_auxiliary() = default;
    explicit skip_list_compress_auxiliary(Compare c) : c {std::move(c)}, r {}, p {} {}
    explicit skip_list_compress_auxiliary(Random r) : c {}, r {std::move(r)}, p {} {}
    explicit skip_list_compress_auxiliary(Probability p) : c {}, r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare c, Random r) : c {std::move(c)}, r {std::move(r)}, p {} {}
    skip_list_compress_auxiliary(Compare c, Probability p) : c {std::move(c)}, r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Random r, Probability p) : c {}, r {std::move(r)}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare c, Random r, Probability p) :
            c {std::move(c)}, r {std::move(r)}, p {std::move(p)} {}
public:
    Compare &compare() noexcept {
        return this->c;
    }
    const Compare &compare() const noexcept {
        return this->c;
    }
    Random &random() noexcept {
        return this->r;
    }
    const Random &random() const noexcept {
        return this->r;
    }
    Probability &probability() noexcept {
        return this->p;
    }
    const Probability &probability() const noexcept {
        return this->p;
    }
};

樣板參數列表中後面三個 bool 型別的樣板參數用於偏特製化, 它們分別表示對應的類別是否不存在成員變數以及是否不可繼承. 上述程式碼是三個類別都需要作為成員的情況, 一旦某一個類別可以通過繼承來壓縮靜態大小, 那麼我們可以寫為 :

template <typename Compare, typename Random, typename Probability>
struct skip_list_compress_auxiliary<Compare, Random, Probability, true, false, false> : public Compare {
public:
    Random r;
    Probability p;
public:
    constexpr skip_list_compress_auxiliary() = default;
    explicit skip_list_compress_auxiliary(Compare) : Compare(), r {}, p {} {}
    explicit skip_list_compress_auxiliary(Random r) : Compare(), r {std::move(r)}, p {} {}
    explicit skip_list_compress_auxiliary(Probability p) : Compare(), r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare, Random r) : Compare(), r {std::move(r)}, p {} {}
    skip_list_compress_auxiliary(Compare, Probability p) : Compare(), r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Random r, Probability p) : Compare(), r {std::move(r)}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare, Random r, Probability p) :
            Compare(), r {std::move(r)}, p {std::move(p)} {}
public:
    Compare &compare() noexcept {
        return static_cast<Compare &>(*this);
    }
    const Compare &compare() const noexcept {
        return static_cast<const Compare &>(*this);
    }
    Random &random() noexcept {
        return this->r;
    }
    const Random &random() const noexcept {
        return this->r;
    }
    Probability &probability() noexcept {
        return this->p;
    }
    const Probability &probability() const noexcept {
        return this->p;
    }
};

Code 5-2 就壓縮了至少一個 Compare 大小 (通常為 1, 但是需要記憶體對位的情況, 可能為 4 或者 8 甚至更大). 如果 sizeof(skip_list_compress_auxiliary<Compare, Random, Probability, false, false, false>) 的值為 3, 那麼sizeof(skip_list_compress_auxiliary<Compare, Random, Probability, true, false, false>) 的值為 2. 剩餘情況大家可以自行實作.

然後我們需要用到一個介面簡化程式碼 :

template <typename Compare, typename Random, typename Probability>
using skip_list_compress = skip_list_compress_auxiliary<Compare, Random, Probability, is_empty_v<Compare> and not is_final_v<Compare>, is_empty_v<Random> and not is_final_v<Random>, is_empty_v<Probability> and not is_final_v<Probability>>;

這樣可以避免我們手動地給出三個 bool 型別的樣板引數.

最後考慮到跳躍列表至少要保存頭部節點, 因此我們繼續進行壓縮 :

template <typename NodeType, typename Compare, typename Random, typename Probability>
struct skip_list_compress_with_node_type : skip_list_compress<Compare, Random, Probability> {
public:
    NodeType n;
public:
    constexpr skip_list_compress_with_node_type() = default;
    explicit skip_list_compress_with_node_type(NodeType n) :
            skip_list_compress<Compare, Random, Probability>(), n {n} {}
    skip_list_compress_with_node_type(NodeType n, Compare c) :
            skip_list_compress<Compare, Random, Probability>(std::move(c)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Random r) :
            skip_list_compress<Compare, Random, Probability>(std::move(r)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Random r) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(r)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Random r, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(r), std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Random r, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(r), std::move(p)),
            n {std::move(n)} {}
public:
    NodeType &node() noexcept {
        return this->n;
    }
    const NodeType &node() const noexcept {
        return this->n;
    }
};

這樣, 以 skip_list_compress_with_node_type 作為 skip_list 的成員的話, 如果用於比較的類別, 隨機數產生器和機率產生器都是無狀態類別的話, 那麼 sizeof(skip_list<T>) 的值將會是 8. 如果不進行壓縮, 那麼 sizeof(skip_list<T>) 的值將會是 24, 如果增加一個空間配置器, 那麼這個值將會是 32. 這樣的空基礎類別優化的技術, 在 C++ 標準樣板程式庫中相當常見.

每一個 C++ 標準樣板程式庫中的容器都會有一些型別別名, 以方便特性萃取, 我們也為我們的跳躍列表增加型別別名成員 :

#include <functional>

template <typename T, typename Compare = std::less<>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list {
public:
    using value_compare = Compare;
    using random_number_generator = Random;
    using probability_generator = Probability;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T &;
    using const_reference = const T &;
    using rvalue_reference = T &&;
    using pointer = T *;;
    using const_pointer = const T *;
    using iterator = skip_list_iterator<T, false>;
    using const_iterator = skip_list_iterator<T, true>;
};

如果跳躍列表的記憶體配置允許自訂, 那麼還需要增加一個型別別名 using allocator_type = Allocator;.

跳躍列表僅有一個成員 :

#include <functional>

template <typename T, typename Compare = std::less<>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list {
public:
    using value_compare = Compare;
    using random_number_generator = Random;
    using probability_generator = Probability;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T &;
    using const_reference = const T &;
    using rvalue_reference = T &&;
    using pointer = T *;;
    using const_pointer = const T *;
    using iterator = skip_list_iterator<T, false>;
    using const_iterator = skip_list_iterator<T, true>;
private:
    skip_list_compress_with_node_type<skip_list_node<T> *, value_compare, random_number_generator, probability_generator> head;
};

最後, 我們宣告它的成員函式並且按照前面章節所呈現的演算法進行實作即可 :

#include <functional>
#include <type_traits>
#include <initializer_list>

template <typename T, typename Compare = std::less<>, typename Random =, typename Probability = skip_list_probability_generator>
class skip_list {
public:
    using value_compare = Compare;
    using random_number_generator = Random;
    using probability_generator = Probability;
    using size_type = allocator_traits_t(allocator_type, size_type);
    using difference_type = allocator_traits_t(allocator_type, difference_type);
    using value_type = T;
    using reference = allocator_traits_t(allocator_type, reference);
    using const_reference = allocator_traits_t(allocator_type, const_reference);
    using rvalue_reference = allocator_traits_t(allocator_type, rvalue_reference);
    using pointer = allocator_traits_t(allocator_type, pointer);
    using const_pointer = allocator_traits_t(allocator_type, const_pointer);
    using iterator = skip_list_iterator<T, false>;
    using const_iterator = skip_list_iterator<T, true>;
private:
    skip_list_compress_with_node_type<skip_list_node<T> *, value_compare, random_number_generator, probability_generator> head;
public:
    skip_list();
    explicit skip_list(size_type);
    skip_list(size_type, const_reference);
    explicit skip_list(value_compare);
    explicit skip_list(random_number_generator);
    explicit skip_list(probability_generator);
    skip_list(value_compare, random_number_generator);
    skip_list(value_compare, probability_generator);
    skip_list(random_number_generator, probability_generator);
    skip_list(value_compare, random_number_generator, probability_generator);
    template <typename Iterator>
    skip_list(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    skip_list(std::initializer_list<value_type>);
    skip_list(const skip_list &);
    skip_list(skip_list &&) noexcept;
    ~skip_list() noexcept;
public:
    skip_list &operator=(const skip_list &);
    skip_list &operator=(skip_list &&) noexcept;
    skip_list &operator=(std::initializer_list<value_type>);
    skip_list &operator=(random_number_generator);
    skip_list &operator=(probability_generator);
public:
    void assign(size_type, const_reference);
    template <typename Iterator>
    void assign(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    void assign(std::initializer_list<value_type>);
    reference front() noexcept;
    const_reference front() const noexcept;
    iterator before_begin() noexcept;
    const_iterator before_begin() const noexcept;
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cbefore_begin() const noexcept;
    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;
    iterator lbefore_begin() noexcept;
    const_iterator lbefore_begin() const noexcept;
    const_iterator clbefore_begin() const noexcept;
    iterator lbegin() noexcept;
    const_iterator lbegin() const noexcept;
    const_iterator clbegin() const noexcept;
    bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_level() const noexcept;
    constexpr size_type max_size() noexcept;
    void clear() noexcept;
    void swap(skip_list &) noexcept;
    iterator insert(const_reference, size_type);
    iterator insert(rvalue_reference);
    template <typename Iterator>
    iterator insert(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    iterator insert(std::initializer_list<value_type>);
    iterator erase_after(const_iterator, const_iterator) noexcept;
    iterator erase_after(const_iterator) noexcept;
    template <typename ...Args>
    iterator emplace(Args &&...);
    void pop_front() noexcept;
public:
    random_number_generator &get_random_number_generator() noexcept;
    const random_number_generator &get_random_number_generator() const noexcept;
    probability_generator &get_probability_generator() noexcept;
    const probability_generator &get_probability_generator() const noexcept;
    template <typename ...Args>
    void reset_random_number_generator(Args &&...);
    template <typename ...Args>
    void reset_probability_generator(Args &&...);
public:
    template <typename ValueType>
    size_type remove(const ValueType &);
    template <typename UnaryPredicate>
    size_type remove_if(UnaryPredicate);
    template <typename BinaryPredicate>
    void unique(BinaryPredicate);
    template <typename ValueType>
    iterator find(const ValueType &);
    template <typename ValueType>
    const_iterator find(const ValueType &) const;
    template <typename UnaryPredicate>
    iterator find_if(UnaryPredicate);
    template <typename UnaryPredicate>
    const_iterator find_if(UnaryPredicate) const;
    template <typename ValueType>
    bool contains(const ValueType &) const;
    template <typename UnaryPredicate>
    bool contains_if(UnaryPredicate) const;
    template <typename ValueType>
    size_type count(const ValueType &) const;
    template <typename UnaryPredicate>
    size_type count_if(UnaryPredicate) const;
};

除了一些新增加的函式, 基本上大部分都和 C++ 標準樣板程式庫保持了一致. 對於新增加的成員函式, 主要有 :

• lbegin, clbegin, lbefore_begin 和 clbefore_begin : 它用於回傳最低層的疊代器. 預設情況下, 我們回傳的疊代器處於節點的最高層. 這樣, 對於尋訪所有元素帶來了困難;
• max_level : 用於回傳當前跳躍列表中的最高級數, 它就直接保存在頭部節點中. 因為不可能存在任何節點, 其級數高於頭部節點.

在列出的成員函式中, 個人認為比較複雜的操作有 :

1. 複製建構子和複製指派運算子;
2. 帶有插入操作的成員函式;
3. 帶有搜尋操作的成員函式;
4. 帶有移除操作的成員函式;

對此, 我有對應的建議 :

1. 閣下可以撰寫一個從其它跳躍列表複製到當前跳躍列表的專用函式, 讓複製建構子和複製指派運算子共享這個函式即可. 不過需要注意的是, 複製指派運算子在複製元素之前, 要清理當前存在於跳躍列表的元素. 如果為了保持例外安全, 應該作一個其它跳躍列表的副件後才對本跳躍列表進行清理;
2. 所有 insert 系列成員函式都可以委託給成員函式 emplace. 在插入時, 閣下還需要考慮級的增加, 以及維護整個跳躍列表的級;
3. erase 系列成員函式可以統一委託給其中一個或者兩個 erase 以簡化程式碼;
4. 如果跳躍列表中, 最高級對應的連結串列有且唯有頭部節點, 那麼我不建議繼續向上增加級.

6.3 實作

我自己用 C++ 實作了跳躍列表 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/skip_list.hpp, 大家可以參考後自行實作.