摘要訊息 : 一個合併操作比堆積高效的資料結構.

0. 前言

在《【資料結構與演算法】堆積, 堆積排序和優先佇列》中, 我們介紹了一種很特殊的樹, 即堆積. 堆積排序法是我們講述過的所有排序演算法中, 唯一一個時間複雜度為 \Theta(n\log {n}) 且空間複雜度為 \Theta(1) 的排序演算法. 由於堆積內部元素的高度有序性, 這也就導致如果我們要把兩個堆積合併, 是非常麻煩的. 因為以其中一個堆積為基準, 對於另一個堆積中的元素我們要逐個處理, 讓它們最終位於正確的位置. 在樹狀的資料結構中, 一個比較高效率的合併應該是這樣的 : 將另外一棵樹的根節點直接插入到某個樹的一個子節點上. 如果這個插入操作導致局域無序, 我們也只需要進行很少量的操作進行調整即可, 而不是像堆積那樣只能一個一個重新插入元素. 調整操作的時間複雜度最好是局域 \Theta(1) 的. 在這種思想下, 容易地我們想到, 如果插入之後導致原樹局域無序, 那麼交換左右子樹就可以修復的話, 這樣的調整操作的時間複雜度就是 \Theta(1).

更新紀錄 :

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

1. 定義

定義 1. 設 x 是樹 \mathcal {T} 的根節點, x_{1}, x_{2}, ..., x_{n} 是樹 \mathcal {T} 中所有葉子節點. 稱 s_{l}(x) = \min \left \{ s(x, x_{1}), s(x, x_{2}), ..., s(x, x_{n}) \right \} + 1 為節點 x 的左偏高度 (leftist height). 其中, s(x, x_{i} 是從節點 x 到節點 x_{i} 的路徑長度 (《【資料結構】樹》定義 15), i = 1, 2, ..., n.

顯然, 定義 1 可以擴展到任意節點. 因為在樹 \mathcal {T} 中, 任意節點都可以成為根節點, 以其為根節點的樹就是 \mathcal {T} 的子樹. 因此, 定義 1 中的 s_{l}(x) 有一種遞迴的表示方法. 設 x 是樹 \mathcal {T} 中的節點, x_{\mathrm {L}} 和 x_{\mathrm {R}} 分別是 x 的左子節點和右子節點, 那麼有 \displaystyle {s_{l}(x) = \begin {cases} 1 & {\text {左右子節點至少有一個為空}} \\ \min \left \{ s(x_{\mathrm {L}}), s(x_{\mathrm {R}}) \right \} & {\text {左右子節點都不為空}}. \end {cases}}

例題 1. 寫出樹 \mathcal {T}

每一個節點的左偏高度.

解 :

我們從葉子節點開始.

顯然, 根據定義 1, s(\alpha_{6}) = s(\alpha_{7}) = s(\alpha_{5}) = s(\alpha_{3}) = 1. 對於 \alpha_{4} 來說, 其兩個子節點的左偏高度都為 1, 因此 s(\alpha_{4}) = 1 + 1 = 2. 對於 \alpha_{2} 來說, 其子節點中最小的左偏高度為 1, 因此 s(\alpha_{2}) = 2. 對於 \alpha_{1} 來說, 其子節點中最小的左偏高度也是 1, 因此也有 s(\alpha_{1}) = 2.

\blacksquare

定義 2. 設 x 是樹的任意節點, x_{1}, x_{2}, ..., x_{n} 是以 x 為根節點的子樹中的節點 (x_{i} \neq x, i = 1, 2, ..., n). 若 w(n) 表示節點 n 的權重, 我們稱 \displaystyle {w_{l}(x) = w(x) + w(x_{1}) + w(x_{2}) + ... + w(x_{n}) = w(x) + \sum \limits_{i = 1}^{n}w(x_{i})} 為節點 x 的左偏權重 (leftist weight). 特別地, 對於空節點 \infty, 我們定義 w_{l}(\infty) = 0.

定義 3. 設 f 是用於計算節點某一屬性的函數, 若對於樹 \mathcal {T} 中的任意節點 x, 總有 \displaystyle {f(x_{\mathrm {L}}) \geq f(x_{\mathrm {R}})} 成立, 那麼我們稱樹 \mathcal {T} 為左偏樹 (leftist tree). 其中, x_{\mathrm {L}} 是節點 x 的左子節點, x_{\mathrm {R}} 是節點 x 的右子節點. 特別地, 若 f = s_{l}, 則稱這棵左偏樹 \mathcal {T} 為高度優先左偏樹 (height-biased leftist tree); 若 f = w_{l}, 則稱這棵左偏樹 \mathcal {T} 為權重優先左偏樹 (weight-biased leftist tree).

根據高度優先左偏樹的定義, Figure 1 中的樹就是一棵高度優先左偏樹.

接下來在沒有特別說明的情況下, 我們討論的左偏樹都是高度優先左偏樹.

2. 性質

性質 1. 任取一個來自高度優先左偏樹中的節點 x, 則 x 必然滿足 :

1. 以 x 為根的子樹的節點數量至少有 2^{s_{l}(x)} - 1;
2. 若以 x 為根節點的子樹有 m 個節點, 則 s_{l}(x) \leq \log_{2} {(m + 1)};
3. 從 x 到任意葉子節點的最右路徑 (即從 x 開始一直沿右子節點向下移動的路徑) 的長度為 s(x).

證明 :

根據定義 1, s_{l}(x) 的值是 x 到葉子節點的最短路徑, 最短路徑上必定有 s_{l}(x) 個節點. 而 x 到其它葉子節點的路徑必定大於最短路徑, 即必定大於 s_{l}(x), 因此以 x 為根節點的子樹必定有 2^{s_{l}(x)} - 1 個節點

(1) \square

以 x 為根節點的子樹所在的第一層有且唯有 1 個節點, 在第二層至多有 2 個節點, 在第三層至多有 4 個... 在第 s_{l}(x) 層至多有 2^{s_{l}(x) - 1} 個節點. 但是, 在第 s_{l}(x) 層下面可能還有節點, 因為左偏樹並不一定是完全二元樹. 因此, 以 x 為根的樹至少有 \sum \limits_{i = 1}^{s_{l}(x)}2^{i} = 2^{s_{l}(x)} - 1 個. 故有 \displaystyle {m \geq 2^{s_{l}(x)} - 1 \Rightarrow s(x) \leq \log_{2} {(m + 1)}}.

(2) \square

根據 s_{l}(x) 的定義以及高度優先左偏樹的定義, 一個節點的左子節點的 s_{l}(x) 值總是大於等於右子節點的 s_{l}(x) 值. 接著, 我們使用歸納法來證明性質 3 成立. 記 x 的左子節點為 x_{\mathrm {L}}, x 的右子節點為 x_{\mathrm {R}}, 最右路徑長度記為 L.

當 s_{l}(x) = 1 時, x 本身是葉子節點, 顯然 s_{l}(x_{\mathrm {L}}) = s_{l}(x_{\mathrm {R}}) = 0. 此時, L = s_{l}(x) = 1; 當 s_{l}(x) = 2 時, 有且唯有 s_{l}(x_{\mathrm {R}}) = 1; 否則, s_{l}(x) > 2. s_{l}(x_{\mathrm {L}}) 可以是大於等於 1 的任何值, 但是不能是 0 (此時這棵樹不是左偏樹). 自然地, 左側的任意路徑長度一定大於等於 1, L = s_{l}(x) = 2 成立; 不妨假設當 s(x) < n 時, 均有 L = s_{l}(x).

當 s_{l}(x) = n 時, 無論 s_{l}(x_{\mathrm {L}}) 是什麼值 (當然, s_{l}(x_{\mathrm {L}}) \geq n - 1 肯定成立), 必定有 s_{l}(x_{\mathrm {R}}) = n - 1. 由於當 s_{l}(x) < n 時均有 L = s_{l}(x), 因此對於 x_{\mathrm {R}} 為根節點的最右路徑長度為 s_{l}(x_{\mathrm {R}}). 那麼, 對於 x 的最右路徑自然有 L = s_{l}(x) = s_{l}(x_{\mathrm {R}}) + 1 = n.

綜上所述, 從 x 到任意葉子節點的最右路徑 (即從 x 開始一直沿右子節點向下移動的路徑) 的長度為 s_{l}(x).

(3) \square

\blacksquare

3. 合併

以高度優先左偏樹為例. 對於要合併的兩棵左偏樹, 如果一棵樹為空, 那麼另外一棵樹就是合併的結果. 現在, 我們討論兩棵樹都不為空的情況. 我們首先注意到, 兩棵左偏樹合併之前, 從兩棵樹中任取一個節點, 以這個節點為根的子樹也是左偏樹. 如果要把另外一棵樹合併到一棵樹的某個節點中, 總共分為兩種情況 : 要合併的位置不存在節點 (也就是這個節點至少有一個子節點的空的) 和要合併的位置存在節點.

3.1 一般性合併

一般性合併的效能最高, 它只需要保持左偏樹的定義即可, 不需要元素具備有序性. 設 \mathcal {T}_{1} 和 \mathcal {T}_{2} 是兩棵要合併的左偏樹. 現在我們要把 T_{2} 插入到 T_{1} 的 x 節點之下, 作為 x 節點的子樹. 這裡我們假設 x 的子節點至少有一個為空, 而 T_{2} 正是要合併那個為空的子節點上. 如果插入導致左偏樹發生不平衡的情況, 我們僅需要交換左右子樹就可以重新維持平衡性. 但是交換之後需要一直檢查父節點是否仍然保持左偏, 如果不是的話, 就要交換父節點的左右子節點. 一直這樣檢查, 直到根節點檢查完畢或者發現某個父節點已經保持左偏為止. 根據定義 3, 左偏樹中的任意子樹也是一棵左偏樹, 所以在左子節點為空的情況下, 我們總是優先插入到左子節點中.

還有一種情況並不是插入到 x 的子節點中, 而是插入 x 本來所在的位置. 這種情況下, 我們首先把以 x 為根節點的子樹拿出來, 讓 \mathcal {T} 插入. 此時, 情況就變成了向空的子節點插入, 按照前面所敘述的方法即可. 對於以 x 為根節點的子樹, 為了不破壞左偏樹的平衡性, 一個比較簡單的方案是從根節點開始一直沿著左子樹走, 走到葉子節點之後, 把以 x 為根節點的子樹掛在這個葉子節點的左子節點上. 例如在 Figure 3 中, 要把以 \beta_{1} 為根節點的樹插入到 \alpha_{1} 的右子節點上, 那麼需要把以 \alpha_{3} 為根節點的子樹讓出來, 然後把這棵子樹掛在 \alpha_{7} 的左子節點上.

一般性合併只需要保持左偏樹的左偏性質. 設將左偏樹 \mathcal {T}_{2} 合併到左偏樹 \mathcal {T}_{1} 的某個位置, 且 \mathcal {T}_{1} 的高度為 h, 即時合併的過程中交換操作持續到了根節點, 時間複雜度也只是 \Theta(h). 而一般性合併的輔助空間和兩棵樹的元素數量都無關, 因此空間複雜度為 \Theta(1).

3.2 有序性合併

有序合併是指合併之後不但保持高度優先左偏樹的平衡性, 還要維持內部元素的平衡性, 例如要求保持任意節點中的元素至少比其子節點中的元素要大. 在這樣的條件下, 合併的時間複雜度會比一般型合併要高一些, 因為它還要維持元素的有序性. 在有序合併中, 並不區分要合併的位置是否有元素, 因為它們的操作步驟都是一樣的.

設 \mathcal {T}_{1} 和 \mathcal {T}_{2} 是兩棵要合併的左偏樹, 且 \mathcal {T}_{1} 和 \mathcal {T}_{2} 都滿足任意節點中的元素至少比其子節點中的元素要大. 由於合併必須保持元素有序性, 因此我們沒有辦法指定是哪一棵樹合併到另一棵樹中. 記 \mathcal {T}_{1}^{\mathrm {L}} 和 \mathcal {T}_{1}^{\mathrm {R}} 是 \mathcal {T}_{1} 根節點的左子樹和右子樹. 我們首先比較 \mathcal {T}_{1} 和 \mathcal {T}_{2} 兩棵樹根節點中的元素, 根節點中元素比較小的那棵樹將會被合併到根節點中元素較大的那棵樹中. 不妨設 \mathcal {T}_{1} 的根節點元素更大. 接下來是 \mathcal {T}_{1}^{\mathrm {R}} 和 \mathcal {T}_{2} 的合併, 不妨假設合併後的結果得到了左偏樹 \mathcal {T}_{3}. 最後我們需要判斷樹 \mathcal {T}_{1}^{\mathrm {L}} 和 \mathcal {T}_{3} 的 s_{l}(x) 值來決定哪一個子樹位於 \mathcal {T}_{1} 的左子節點, 另一棵樹放置在 \mathcal {T}_{1} 的右子節點. 那麼 \mathcal {T}_{1}^{\mathrm {R}} 和 \mathcal {T}_{2} 使用什麼方式進行合併呢? 遞迴地, 我們使用類似的方式.

如果左偏樹的的任意節點元素都要求比子節點元素要小, 那麼只需要改變 Algorithm 1 中元素比較的方式即可.

例題 2. 合併左偏樹 \mathcal {T}_{1} 和 \mathcal {T}_{2}.

解 :

我們首先記 E 表示一棵空的左偏樹, 節點旁邊的記號表示節點中的元素, 例如 a = 40. 我們開始合併 :

• (遞迴深度 : 0) 要合併 和 , 首先要判定 \alpha_{1} 和 \beta_{1} 的大小. 由於 40 > 18, 因此接下來要合併的是 \alpha_{1} 的右子樹和以 \beta_{1} 為根節點的樹, 即合併 和 , 然後將合併的結果和 再進行合併;
  • (遞迴深度 : 1) 接下來合併 和 . 由於 \beta_{1} > \alpha_{3}, 於是要合併的是 \beta_{1} 的右子樹和以 \alpha_{3} 為根節點的樹, 即合併 和 , 然後將合併的結果和 進行合併;
    • (遞迴深度 : 2) 現在要合併 和 . 由於 \alpha_{3} > \beta_{3}, 因此要合併的是 \alpha_{3} 的右子樹 E 和 . 由於 E 是空樹, 所以合併的結果就是 ;
    • (遞迴深度 : 2) 現在收到了 E 和 的合併結果 , 然後要把它和 進行合併. 由於 s_{l}(\alpha_{3}) = 1 且 s_{l}(\alpha_{3}) = 1, 從而 s_{l}(\alpha_{3}) \geq s_{l}(\beta_{3}), 可以把以 \beta_{3} 為根節點的子樹放到 \alpha_{3} 的右子樹中得到合併結果 .
  • (遞迴深度 : 1) 現在收到了 和 的合併結果 , 現在要把這個結果和 合併. 由於 s_{l}(\alpha_{3}) = 2 且 s_{l}(\beta_{2}) = 1, 於是要把以 \alpha_{3} 為根節點的樹放在 \beta_{1} 的左子樹中, 把原來 \beta_{1} 的左子樹 (以 \beta_{2} 為根節點的子樹) 交換到右子樹上, 得到 .
• (遞迴深度 : 0) 現在收到了 和 的合併結果 , 要把它和 進行合併. 由於 s_{l}(\beta_{1}) = 2 且 s_{l}(\alpha_{2}) = 1, 於是要把以 \beta_{1} 為根節點的樹放置在 \alpha_{1} 的左子樹中, 原來 \alpha_{1} 的左子樹 (以 \alpha_{2} 為根節點的子樹) 交換到右子樹上, 得到最終的合併結果 :

  

\blacksquare

現在我們來分析有序性合併的時間複雜度. 設要合併的兩棵左偏樹為 \mathcal {T}_{1} 和 \mathcal {T}_{2}, 它們總共分別有 m 個節點和 n 個節點. 那麼對於左偏樹 \mathcal {T}_{1} 和 \mathcal {T}_{2} 的最右路徑, 這條路徑上至多有 O(\log {m}) 和 O(\log {n}) 個節點. 每一次合併只需要判定左右子樹的 s_{l}(x) 值然後決定是否交換, 這個過程的時間複雜度為 \Theta(1). 由於只需要考慮最右路徑上的節點數量, 在不考慮計算 s_{l}(x) 值的時間複雜度下 (或者說視計算 s_{l}(x) 的時間複雜度為 \Theta(1)), 總體的時間複雜度為 O(\log {m} + \log {n}).

由於有序性合併的過程中使用了遞迴, 自然需要額外的空間. 由時間複雜度我們知道, 我們總計要進行 O(\log {m} + \log {n}) 次遞迴的有序性合併, 自然也就需要 O(\log {m} + \log {n}) 個空間來儲存函式引數. 於是, 我們可以得到有序性合併的空間複雜度也是 O(\log {m} + \log {n}).

3.3 比較堆積的合併

很顯然, 左偏樹合併的時間複雜度和堆積相比要低得多. 設堆積 \mathcal {H}_{1} 和 \mathcal {H}_{2} 分別具有 m 和 n 個元素, 不妨設將堆積 \mathcal {H}_{2} 併入堆積 \mathcal {H}_{1} 中, 那麼合併總共要進行 n 次, 一次合併過程的時間複雜度為 \Theta(\log {m}), 於是總體的時間複雜度為 \Theta(n\log {m}). 左偏樹的合併將時間複雜度降低到了線性級別. 對於元素很多的左偏樹和堆積來說, 顯然是左偏樹的合併效能更高.

4. 插入和移除

我們首先講述了合併而不是插入和移除. 這是因為插入和刪除實際上都可以委託給合併來完成.

向左偏樹插入一個元素的情形就是合併一棵只有根節點的樹. 對於無序合併來說, 如果指定了插入位置, 那麼就需要考慮插入完成之後, 左右子樹的左偏性是否仍然維持. 如果不是的話, 就要像合併那樣, 一直追溯父節點檢查左偏性. 對於有序合併來說, 由於僅有一個元素的二元樹必定是左偏樹, 我們要做的就是合併這兩棵左偏樹.

若從左偏樹中移除一個元素, 有三種情形. 一個是要移除的節點本身是葉子節點, 沒有任何子節點, 刪除之後我們只需要隨著父節點逐層檢查子樹的左偏性. 對於不平衡的情況, 無論有序合併還是無需合併, 都只需要交換左右子樹即可. 如果要移除的節點只有一個子節點, 那麼把要移除的節點從左偏樹中拿掉之後, 就會得到兩棵左偏樹, 只需要合併這兩棵左偏樹即可. 還有一種是要移除的節點既有左子節點又有右子節點. 這種情況下, 如果把要移除的節點從左偏樹中拿掉之後, 會得到三棵左偏樹. 由於以要移除的節點為根的兩棵子樹元素比原樹要少, 所以先把這兩棵子樹進行合併, 然後把合併得到的新左偏樹再和原樹進行合併即可.

5. 初始化

要注意的是, 無序的左偏樹不存在嚴格的初始化. 一般來說, 我們只能把節點單個安排插入, 然後維持左偏性. 因此我們只討論有序左偏樹的初始化. 左偏樹的初始化可以借助優先佇列完成. 每一次從優先佇列頂部取出一個元素, 然後按照從上至下, 從左至右的順序排列即可. 從左至右逐漸排列元素決定了這棵樹必定是左偏樹, 從上到下逐漸排列元素決定這棵左偏樹必定是有序的. 總體來說, 初始化的時間複雜度為 \Theta(n\log {n}).

6. 實作

我自己用 C++ 實作了左偏樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/leftist_tree.hpp, 大家可以參考後自行實作.