左偏樹(英語:Leftist tree),也可稱為左偏堆左傾堆,是電腦科學中的一種,是一種優先佇列實現方式,屬於可並,在資訊科學中十分常見,在統計問題、最值問題、模擬問題和貪心問題等等類型的題目中,左偏樹都有着廣泛的應用。斜堆是比左偏樹更為一般的數據結構。

不同於斜堆合併的平均情況複雜度英語average-case complexity,左偏堆的合併操作的最壞情況複雜度英語Worst-case complexity,而完全二叉堆積為 ,所以左偏堆適合基於合併操作的情形。

由於左偏堆已經不是完全二叉樹,因此不能用陣列儲存表示,需要用連結結構。

定義

 
左偏樹的節點的距離值

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

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

性質

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

操作

初始化一個左偏樹

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

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

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

合併兩顆左偏樹

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

在合併之後,比較子堆的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;
}

其他操作

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

參考文獻

  1. ^ 《左偏樹的特點及其應用》黃源河2005全國青少年資訊科學奧林匹克競賽冬令營國家集訓隊論文

延伸閱讀

  • 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