左偏樹

左偏樹（英語：Leftist tree），也可稱為左偏堆、左傾堆，是計算機科學中的一種樹，是一種優先隊列實現方式，屬於可並堆，在信息學中十分常見，在統計問題、最值問題、模擬問題和貪心問題等等類型的題目中，左偏樹都有着廣泛的應用。斜堆是比左偏樹更為一般的數據結構。

不同於斜堆合併的平均情況複雜度,左偏堆的合併操作的最壞情況複雜度為 $O(logn)$，而完全二叉堆為 $O(n)$，所以左偏堆適合基於合併操作的情形。

由於左偏堆已經不是完全二叉樹，因此不能用數組存儲表示，需要用鏈接結構。

定義

左偏樹的節點的距離值

左偏樹是一種可並堆的實現。左偏樹是一棵二叉樹，它的節點除了和二叉樹的節點一樣具有左右子樹指針（left, right）外，還有兩個屬性： 鍵值和距離（英文文獻中稱為s-value）。鍵值用於比較節點的大小。距離的定義如下：

當且僅當節點 i 的左子樹或右子樹為空時，節點被稱作外節點（實際上保存在二叉樹中的節點都是內節點，外節點是邏輯上存在而無需保存。把一顆二叉樹補上全部的外節點，則稱為extended binary tree）。節點i的距離是節點 i 到它的後代中的最近的外節點所經過的邊數。特別的，如果節點 i 本身是外節點，則它的距離為0;而空節點的距離規定為 -1。

性質

1. 節點的鍵值小於或等於它的左右子節點的鍵值。
2. 節點的左子節點的距離不小於右子節點的距離。
3. 節點的距離等於它的右子節點的距離加1。
4. 一棵N個節點的左偏樹root節點的距離最多為log(N+1)-1。

操作

初始化一個左偏樹

初始化左偏樹有兩種方式。

第一種是每次選擇一個節點與樹合併，直到所有節點都合併為一個樹。這種方法不太有效，時間複雜度為$O(nlogn)$。

第二種方法是使用隊列，將隊列中前兩個節點合併，將合併後的新節點放到隊列的末尾，直到隊列中只有一個節點。這種方法的時間複雜度為$O(n)$。

合併兩顆左偏樹

假設堆是小根堆，合併時選擇關鍵字較小的節點作為根節點，然後將關鍵字大的節點與根節點的右子堆合併。

在合併之後，比較子堆的s值。通過交換左右子堆來保證左節點的s值始終大於等於右節點。然後更新節點的s值。

Java代碼實現合併兩棵左偏的最小樹：

1. root鍵值最小的樹的右子樹與其它樹合併；
2. 上步合併結果作為與root鍵值最小樹的右子樹。
3. 比較root的左右子樹的距離值（s-value），如果右子樹大於左子樹則交換兩棵子樹

public Node merge(Node x, Node y) {
  if(x == null)
    return y;
  if(y == null) 
    return x;

  // if this was a max height biased leftist tree, then the 
  // next line would be: if(x.element < y.element)
  if(x.element.compareTo(y.element) > 0) {  
    // x.element > y.element
    Node temp = x;
    x = y;
    y = temp;
  }

  x.rightChild = merge(x.rightChild, y);

  if(x.leftChild == null) {
    // left child doesn't exist, so move right child to the left side
    x.leftChild = x.rightChild;
    x.rightChild = null;

  } else {
    // left child does exist, so compare s-values
    if(x.leftChild.s < x.rightChild.s) {
      Node temp = x.leftChild;
      x.leftChild = x.rightChild;
      x.rightChild = temp;
    }
    // since we know the right child has the lower s-value, we can just
    // add one to its s-value
    x.s = x.rightChild.s + 1;
  }
  return x;
}

其他操作

增加一個節點、刪除根節點、初始化一批數據，都是基於合併操作。

延伸閱讀

• Leftist Trees （頁面存檔備份，存於網際網路檔案館）, Sartaj Sahni
• 傅清祥,王曉東 算法與數據結構(第二版) 電子工業出版社
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms (Second Edition) The MIT Press
• Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second Edition) Pearson Education