左偏堆的特點(diǎn)及其應(yīng)用

1、左傾樹的特點(diǎn)及應(yīng)用，廣東省中山一中黃園河2。左傾樹的定義，左傾樹是一個(gè)可合并堆，它不僅支持優(yōu)先級(jí)隊(duì)列的三個(gè)基本操作(插入、刪除、取最小節(jié)點(diǎn))，還支持一個(gè)非常特殊的操作合并操作。左傾樹是一個(gè)堆有序的二叉樹。左傾的樹滿足了左派的屬性。左偏樹的定義左偏屬性定義左偏樹中的外部節(jié)點(diǎn)是左子樹或右子樹為空的節(jié)點(diǎn)。節(jié)點(diǎn)I的距離(dist(i)定義為從節(jié)點(diǎn)I到其后代中最近的外部節(jié)點(diǎn)的邊數(shù)。任何節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離(左偏移屬性)。根據(jù)左偏屬性，節(jié)點(diǎn)的距離等于以節(jié)點(diǎn)為根的子樹的最右邊路徑的長(zhǎng)度。4，左傾樹的性質(zhì)，定理：如果左傾樹有N個(gè)節(jié)點(diǎn)，左傾樹的距離不應(yīng)超過對(duì)數(shù)(N 1) -1。最右邊的路徑：

2、 ACG最右邊的路徑節(jié)點(diǎn)數(shù)=3距離=2，左傾樹的最大距離為8個(gè)節(jié)點(diǎn)：log(8 1) -1=2，5，左傾樹的操作，左傾樹支持以下操作：MakeNull初始化一個(gè)空的左傾樹合并兩個(gè)左傾樹插入一個(gè)新的節(jié)點(diǎn)最小值得到最小節(jié)點(diǎn)刪除最小值刪除最小節(jié)點(diǎn)刪除任何已知節(jié)點(diǎn)減少一個(gè)節(jié)點(diǎn)的鍵值，6， 左傾樹合并的操作，合并操作是遞歸的，合并T1和T2左傾樹，首先合并T1的右子樹和T2，7。 合并左傾樹，這是遞歸的，首先合并T1的右子樹和T2，8。合并左樹，這是遞歸的，交換左右子樹并更新根節(jié)點(diǎn)距離，合并后，右子樹距離可能大于左子樹距離。合并操作代碼如下：函數(shù)合并(a，b)如果a=空，則返回b如果b=空，則返回a如果

3、鍵(b) dist(左(a)然后交換(左(a)，右(a)如果右(a)=空，則dist (a) 0否則dist (a) dist(右(a) 1返回一個(gè)結(jié)束函數(shù)，10。以下是合并的示例：11。以下是合并的示例：12。以下是合并的示例：13。以下是合并的示例：18、NULL、14。下面是一個(gè)合并的例子。15，左傾樹操作合并，下面是一個(gè)合并示例：1，1，2，26，17，37，18，8，7，16，左傾樹操作合并，下面是一個(gè)合并示例：0，2，17、左傾樹被合并。以下是合并的示例：3、10、2、0、1、18。合并操作總是沿著兩個(gè)左傾樹的最右邊的路徑執(zhí)行。有N個(gè)節(jié)點(diǎn)的左傾樹在最右邊的路徑上最多有N(1)個(gè)節(jié)點(diǎn)。因此，合并操作的時(shí)間復(fù)雜度為：0(對(duì)數(shù)N1對(duì)數(shù)N2)=0(對(duì)數(shù)N)，19，插入一個(gè)新節(jié)點(diǎn)，將待插入的節(jié)點(diǎn)作為單節(jié)點(diǎn)左偏樹，合并兩個(gè)左偏樹：0(對(duì)數(shù)N)，20，刪除左偏樹，刪除最小節(jié)點(diǎn)，刪除根節(jié)點(diǎn)合