0. 導論

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

1. 定義

首先, 我們注意到, 從二元樹的任意一個節點出發, 從這個節點到其可到達的任何一個葉子節點, 都有且唯有一條路徑, 因為每一個葉子節點它只連結它的父節點, 而沒有連結其它節點. 因此, 從任意一個節點出發, 到達其可達的葉子節點的路徑長度實際上是固定的.

定義 1.x 是一棵二元樹 T 的任意節點, x_{1}, x_{2}, ..., x_{n}x 可以到達的所有節點. 如果 x 存在某個為空的子節點 (只要左右子節點有一個為空又或者都為空), 那麼我們定義 s(x) = 1. 否則, 記 s(x, x_{i}) 是從 x 到葉子節點 x_{i} 的路徑長度, 記 s(x) 是所有路徑長度中最小的, 即 s(x) = \min \left \{ s(x, x_{1}), s(x, x_{2}), ..., s(x, x_{n}) \right \}.

從遞迴的角度出發, 定義 1 中的 s(x) 其實有另外一種表示方法. 首先我們記 x 的左子節點為 L, 右子節點為 R. s(x) 的值實際上是 s(L)s(R) 中較小的那個值, 然後加上 1 即可. 如果 x 本身是葉子節點, 那麼 s(x) = 1. 於是, 我們有 \displaystyle {s(x) = \begin {cases} \min \left \{ s(L), s(R) \right \} + 1 & {x\ \text {的左右子節點都不為空}} \\ 1 & {\text {else}} \end {cases}} 其中, Lx 的左子節點, Rx 的右子節點.

例題 1. 列出下面所有節點的 s(x) 值.

:

這一類的問題應該從葉子節點開始標註. 根據定義 1, 我們能夠容易得到 : s(F) = s(G) = s(E) = s(C) = 1. 然後我們規定一個記號以便於討論, 我們記某個節點 X 的左子節點為 X_{L}, 右子節點為 X_{R}. 現在來看 D 節點, 顯然 s(D_{L}) = s(D_{R}) = 1. 於是根據定義 1, s(D) = 2. 對於節點 B 來說, s(B_{L}) = 2, 但是 s(B_{R}) = 1. 因此, s(B) = 2. 節點 A 也是用類似的方法. s(A_{L}) = 2, s(A_{R}) = 1, 故 s(A) = 2.

\blacksquare

定義 2. (高度優先左偏樹) 對於一棵二元樹 T, 設 x 是二元樹中的節點, x_{L}x 的左子節點, x_{R}x 的右子節點. 若對於 T 中的任意節點 x, 都有 s(x_{L}) \geq s(x_{R}), 那麼我們稱這棵二元樹為高度優先左偏樹.

顯然, 例題 1 中的這棵二元樹就是一棵高度優先左偏樹.

定義 3. (權重優先左偏樹) 對於一棵二元樹 T, 設 x 是二元樹中的節點. 若對於 T 中的任意節點 x, 都有 x 的左子樹中的元素權重之和都比其右子樹中的元素權重之和大, 那麼我們稱這棵樹為權重優先左偏樹.

定義 4. (左偏樹) 對於一棵二元樹 T, 設 x 是二元樹中的節點, x_{L}x 的左子節點, x_{R}x 的右子節點, f 是某一標準函數. 若對於 T 中的任意節點 x, 都有 f(x_{L}) \geq f(x_{R}), 那麼我們稱這棵樹為左偏樹.

Tip : 如果接下來討論到左偏樹, 在沒有特別指定的情形下, 我們預設左偏樹就是高度優先左偏樹.

2. 性質

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

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

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

(1) \square

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

(2) \square

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

s(x) = 1 時, x 本身是葉子節點, 顯然 s(x_{L}) = s(x_{R}) = 0. 此時, L = s(x) = 1;

s(x) = 2 時, 有且唯有 s(x_{R}) = 1; 否則, s(x) > 2. s(x_{L}) 可以是大於等於 1 的任何值, 但是不能是 0 (此時這棵樹不是左偏樹). 自然地, 左側的任意路徑長度一定大於等於 1, L = s(x) = 2 成立;

不妨假設當 s(x) < n 時, 均有 L = s(x);

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

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

(3) \square

\blacksquare

3. 合併

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

3.1 一般性合併

一般性合併的效能最高, 但是不具備任何元素有序性, 它僅保持左偏樹的左偏性. 設 T_{1}T_{2} 是兩棵要合併的左偏樹. 現在我們要把 T_{2} 插入到 T_{1}x 節點之下, 作為 x 節點的子樹. 這裡我們假設 x 的子節點至少有一個為空, 而 T_{2} 正是要合併那個為空的子節點上. 如果插入導致左偏樹發生不平衡的情況, 我們僅需要交換左右子樹就可以重新維持平衡性.

如果 x 的子節點不為空, 大致步驟也差不多 :

現在的問題顯而易見, 就是應該把 "擠" 出來的 C 節點放在哪裡. 簡單粗暴的解決方案是不允許這樣的合併. 但是如果要強行進行這樣的合併, 而為了不破壞左偏樹的平衡性, 一個比較簡單的方案是從根節點開始一直沿著左子樹走, 找到最左側的葉子節點然後把 C 放到這個葉子節點的左子節點上 :

最後我們來分析一下一般性合併的時間複雜度. 首先, 將一棵樹合併到另一棵樹某個節點下需要的時間複雜度是 \Theta(1). 為了維持左偏樹的平衡性, 若需要交換左右子樹, 交換的時間複雜度也為 \Theta(1). 因此, 如果不允許合併到有節點的地方, 總體的一般性合併的時間複雜度就是 \Theta(1). 如果允許合併到有節點的地方, 被 "擠" 出來的節點還需要找到它自己的地方. 如果按照一直沿左子樹走的方案, 平均情況下還要再走過 \Omega(\log {n}) 個節點, 此時時間複雜度為 \Omega(\log {n}).

3.2 有序合併

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

AB 是兩棵要合併的左偏樹. 由於合併是有序的, 因此我們沒有辦法指定誰合併到誰中. 記 A_{L}A_{R}A 的左子樹和 A 的右子樹. 我們首先比較兩棵樹根節點中的元素, 根節點中元素比較小的那棵樹被合併到根節點中元素較大的那棵樹中. 不妨設 A 的根節點元素更大. 接下來是 A_{R}B 的合併, 不妨假設合併後的結果得到了左偏樹 C. 最後我們需要判斷樹 A_{L}Cs(x) 值來決定哪一個子樹位於 A 的左子節點, 另一棵樹放置在 A 的右子節點. 那麼 A_{R}B 使用什麼方式進行合併呢? 還是使用同樣的方式, 那麼這裡就可以使用遞迴進行合併. 我將用 C++ 虛擬碼來表示合併的演算法 :

/*template <typename T>
struct tree_node {
    T value;
    tree_node *left;
    tree_node *right;
    tree_node *parent;
};*/

template <typename TreeNode>
int s_x(TreeNode);

template <typename TreeNode>
TreeNode merge(TreeNode A, TreeNode B) {
    if(B == nullptr) {
        return A;
    }else if(A == nullptr) {
        return B;
    }
    if(A->value >= B->value) {
        auto result {merge(A->right, B)};
        if(s_x(A->left) < s_x(result)) {
            A->right = A->left;
            A->left = result;
        }else {
            A->right = result;
        }
    }else {
        auto result {merge(B->right, A)};
        if(s_x(B->left) < s_x(result)) {
            B->right = B->left;
            B->left = result;
        }else {
            B->right = result;
        }
    }
}

例題 2. 合併左偏樹 A 和左偏樹 B.

:

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

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

\blacksquare

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

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

3.3 比較堆積的合併

很顯然, 左偏樹合併的時間複雜度和堆積的合併來說 (堆積的合併自然是將另外一個堆積的元素一個一個插入堆積中), 要低得多. 設堆積 AB 分別具有 mn 個元素, 不妨設將堆積 B 併入堆積 A 中, 那麼合併總共要進行 n 次, 合併過程的時間複雜度為 \Theta(\log {m}), 於是總體的時間複雜度為 \Theta(n\log {m}). 左偏樹的合併將時間複雜度降低為二次線性的時間複雜度. 對於元素很多的左偏樹和堆積來說, 顯然是左偏樹的合併效能更高.

4. 插入和刪除

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

4.1 插入

插入一棵左偏樹的情形就是合併, 只是插入到一個節點為空的地方罷了. 現在我們討論插入單個元素的情形. 對於無序合併來說, 可以直接把原來的左偏樹放置在要插入元素的左子節點上即可. 對於有序合併來說, 我們要做的就是合併原左偏樹和一棵以插入元素為根節點的左偏樹 (要注意, 僅有一個元素的二元樹必定是左偏樹).

4.2 刪除

若刪除的元素本身是葉子節點, 沒有任何子節點, 刪除之後我們只需要逐層檢查左偏樹的平衡性. 對於不平衡的情況, 無論有序合併還是無需合併, 都只需要交換左右子樹即可. 如果元素本身帶有一個子樹, 另外一個子節點為空, 那麼直接將這棵子樹和原樹作合併. 如果元素帶有兩棵子樹, 也就是沒有一個子節點為空, 那麼將這兩棵子樹合併之後, 再和原樹合併即可.

5. 初始化

無序左偏樹的初始化時間複雜度就是 \Theta(n), 因為它無序維護元素的有序性. 我們只討論有序左偏樹的初始化. 左偏樹的初始化可以借助優先佇列完成. 每一次從優先佇列頂部取出一個元素, 然後按照從上至下, 從左至右的順序排列即可. 從左至右逐漸排列元素決定了這棵樹必定是左偏樹, 從上到下逐漸排列元素決定這棵左偏樹必定是有序的.

6. 實作

資料結構 leftist_tree : GitHub 點擊直達