-
左偏樹
鎖定
- 中文名
- 左偏樹
- 外文名
- Leftist Tree
- 屬 性
- 是一種可並堆的實現
- 實 質
- 一棵二叉樹
- 學 科
- 數據結構
- 領 域
- 數據結構
左偏樹簡介
左偏樹（英語：leftist tree或leftist heap），也可稱為左偏堆、左傾堆，是計算機科學中的一種樹，是一種優先隊列實現方式，屬於可並堆，在信息學中十分常見，在統計問題、最值問題、模擬問題和貪心問題等等類型的題目中，左偏樹都有着廣泛的應用。斜堆是比左偏樹更為一般的數據結構。
不同於斜堆合併的平均情況複雜度,左偏堆的合併操作的最壞情況複雜度為O(log n)，而完全二叉堆為O(n)，所以左偏堆適合基於合併操作的情形。
由於左偏堆已經不是完全二叉樹，因此不能用數組存儲表示，需要用鏈接結構。
左偏樹定義
左偏樹是一種可並堆的實現。左偏樹是一棵二叉樹，它的節點除了和二叉樹的節點一樣具有左右子樹指針（left, right）外，還有兩個屬性： 鍵值和距離（英文文獻中稱為s-value）。鍵值用於比較節點的大小。距離的定義如下：
當且僅當節點 i 的左子樹且右子樹為空時，節點被稱作外節點（實際上保存在二叉樹中的節點都是內節點，外節點是邏輯上存在而無需保存。把一顆二叉樹補上全部的外節點，則稱為extended binary tree）。節點i的距離是節點 i 到它的後代中的最近的外節點所經過的邊數。特別的，如果節點 i 本身是外節點，則它的距離為0;而空節點的距離規定為 -1。
[1]
左偏樹性質
- 節點的左子節點的距離不小於右子節點的距離。
- 節點的距離等於它的右子節點的距離加1。
- 一棵N個節點的左偏樹root節點的距離最多為log(N+1)-1。
左偏樹操作
左偏樹合併兩顆左偏樹
Java代碼實現合併兩棵左偏的最小樹：
- root鍵值最小的樹的右子樹與其它樹合併；
- 上步合併結果作為與root鍵值最小樹的右子樹。
- 比較root的左右子樹的距離值（s-value），如果右子樹大於左子樹則交換兩棵子樹publicNodemerge(Nodex,Nodey){if(x==null)returny;if(y==null)returnx;//ifthiswasamaxheightbiasedleftisttree,thenthe//nextlinewouldbe:if(x.element<y.element)if(x.element.compareTo(y.element)>0){//x.element>y.elementNodetemp=x;x=y;y=temp;}x.rightChild=merge(x.rightChild,y);if(x.leftChild==null){//leftchilddoesn'texist,somoverightchildtotheleftsidex.leftChild=x.rightChild;x.rightChild=null;}else{//leftchilddoesexist,socompares-valuesif(x.leftChild.s<x.rightChild.s){Nodetemp=x.leftChild;x.leftChild=x.rightChild;x.rightChild=temp;}//sinceweknowtherightchildhasthelowers-value,wecanjust//addonetoitss-valuex.s=x.rightChild.s+1;}returnx;}
左偏樹其他操作
增加一個節點、刪除根節點、初始化一批數據，都是基於合併操作。
