<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Leftist Tree(Leftist Heap) - 左偏樹（左傾堆） -------- #### 左偏樹 左偏樹是一種類似小根堆的二叉樹，它的根節點總是樹中的最小值。與堆不同的是，合并兩個數量為$$ n $$的堆的時間復雜度為$$ O(n \times log_2 n) $$，因為合并兩個堆需要從其中一個取出元素加入另一個，重復$$ n $$次，每次取出/加入操作的時間復雜度為$$ O(log_2 n) $$。 左偏樹的主要操作有：$$ (1) $$合并兩個左偏樹；$$ (2) $$插入新節點；$$ (3) $$查找最值；$$ (4) $$刪除最值。其中$$ (2) - (4) $$的實現依賴于$$ (1) $$，合并操作是左偏樹的核心。 左偏樹中的節點的距離$$ d $$是該節點到最右下葉子節點的距離。左偏樹具有以下性質： $$ (1) $$父節點的值小于等于其左右孩子節點的值，即$$ value_{father} \leq value_{left}, value_{father} \leq value_{right} $$。最小的值在根節點類似小根堆的頭節點； $$ (2) $$父節點的左孩子節點的距離大于等于右孩子節點的距離，即$$ d_{left} \geq d_{right} $$； $$ (3) $$父節點的距離等于其右孩子節點的距離加$$ 1 $$，即$$ d_{father} = d_{right} + 1 $$； $$ (4) $$具有$$ n $$個節點的左偏樹的根節點的距離小于等于$$ log_2?(n+1) - 1 $$，即$$ d_{root} \leq log_2?(n+1) - 1 $$； 下圖中每個節點上，上面的數字代表節點的值，下面的數字代表距離。合并兩個左偏樹的操作，分為兩步：$$ (1) $$遞歸向下合并子樹的根節點；$$ (2) $$遞歸向上更新所有被修改過的節點的距離。我們通過合并下面兩個左偏樹來進行演示：  $$ (1) $$比較兩樹的根節點$$ 6 \lt 7 $$，節點$$ 7 $$沿著節點$$ 6 $$向右下尋找第$$ 1 $$個滿足$$ 7 \lt x $$的節點$$ x $$，替換$$ x $$作為節點$$ 6 $$的新右孩子節點。該節點為節點$$ 8 $$（$$ 7 \lt 8 $$），節點$$ 6 $$的原右孩子節點$$ 8 $$暫時脫離；  $$ (2) $$節點$$ 8 $$沿著節點$$ 7 $$向右下尋找第$$ 1 $$個滿足$$ 8 \lt x $$的節點$$ x $$，替換$$ x $$作為節點$$ 7 $$的新右孩子節點。該節點為節點$$ 12 $$（$$ 8 \lt 12 $$），節點$$ 7 $$的原右孩子節點$$ 12 $$暫時脫離；  $$ (3) $$節點$$ 12 $$沿著節點$$ 8 $$向右下尋找第$$ 1 $$個滿足$$ 12 \lt x $$的節點$$ x $$，替換$$ x $$作為節點$$ 8 $$的新右孩子節點。該節點為節點$$ 13 $$（$$ 12 \lt 13 $$），節點$$ 8 $$的原右孩子節點$$ 13 $$暫時脫離；  $$ (4) $$節點$$ 13 $$沿著節點$$ 12 $$向右下尋找第$$ 1 $$個滿足$$ 13 \lt x $$的節點$$ x $$，替換$$ x $$作為節點$$ 12 $$的新右孩子節點。該節點為節點$$ 26 $$（$$ 13 \lt 26 $$），節點$$ 12 $$的原右孩子節點$$ 26 $$暫時脫離；  $$ (5) $$節點$$ 26 $$沿著節點$$ 13 $$向右下尋找第$$ 1 $$個滿足$$ 26 \lt x $$的節點$$ x $$，節點$$ 13 $$沒有右孩子節點，因此節點$$ 26 $$直接成為節點$$ 13 $$的右孩子節點，不再需要替換，合并操作結束；  向右下插入節點的操作會影響到左偏樹的平衡性，右子樹變得越來越龐大。而且所有節點的距離也是錯的（沒有更新）。實際上每一步合并操作后還需要檢查左右子樹的距離屬性：$$ (1) $$對于$$ d_{left} \lt d_{right} $$的情況，交換左右子樹；$$ (2) $$對于$$ d_{root} \neq d_{right} + 1 $$的情況，更新$$ d_{root} $$。 節點距離的更新必須從葉子節點開始向上進行，對于之前步驟中修改過的節點，重新遍歷計算其距離（其中$$ d_{nil} = -1 $$）： $$ (6) $$ 對于節點$$ 26 $$，$$ d_{27} = 0 \ge d_{nil} = - 1 $$，不需要交換左右子樹，更新$$ d_{26} = d_{nil} + 1 = - 1 + 1 = 0 $$；  $$ (7) $$ 對于節點$$ 13 $$，$$ d_{28} = 0 \ge d_{26} = 0 $$，不需要交換左右子樹，更新$$ d_{13} = d_{26} + 1 = 0 + 1 = 1 $$；  $$ (8) $$ 對于節點$$ 12 $$，$$ d_{31} = 1 \ge d_{26} = 1 $$，不需要交換左右子樹，更新$$ d_{12} = d_{13} + 1 = 1 + 1 = 2 $$；  $$ (9) $$ 對于節點$$ 8 $$，$$ d_{10} = 1 \lt d_{12} = 2 $$，需要交換子樹$$ 10 $$和子樹$$ 12 $$，更新$$ d_{8} = d_{10} + 1 = 1 + 1 = 2 $$；  $$ (10) $$ 對于節點$$ 7 $$，$$ d_{9} = 1 \lt d_{8} = 2 $$，需要交換子樹$$ 9 $$和子樹$$ 8 $$，更新$$ d_{7} = d_{9} + 1 = 1 + 1 = 2 $$；  $$ (11) $$對于節點$$ 6 $$，$$ d_{11} = 2 \ge d_{7} = 2 $$，不需要交換左右子樹，更新$$ d_{6} = d_{7} + 1 = 2 + 1 = 3 $$； 編碼時通過遞歸的方式將合并和更新距離兩個操作放在同一個遞歸函數中，合并函數Merge返回合并后左偏樹的根節點的距離$$ d $$，在Merge中調用左右孩子的合并操作，獲取左右孩子的距離，然后再決定是否交換左右子樹，并更新父節點的距離。本文的將兩個步驟分開是為了方便理解算法。 左偏樹的插入操作，可以看作左偏樹與一個只有根節點的左偏樹的合并操作；刪除最值的操作，可以看作刪除根節點后，合并左右子樹的操作。 左偏樹的合并操作、插入節點操作、刪除根節點操作的時間復雜度都為$$ O(log_2?n) $$。 -------- #### 源碼 [LeftistTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/LeftistTree.h) [LeftistTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/LeftistTree.cpp) #### 測試 [LeftistTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/LeftistTreeTest.cpp)