資訊專欄INFORMATION COLUMN
摘要：我們知道，當(dāng)樹(shù)變得不平衡時(shí)和操作會(huì)使二叉搜索樹(shù)的性能降低到。樹(shù)實(shí)現(xiàn)抽象數(shù)據(jù)類型就像一個(gè)普通的二叉搜索樹(shù)，唯一不同的是這棵樹(shù)的工作方式。我們通過(guò)比較每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度完成比較。
平衡二叉搜索樹(shù)
在上一節(jié)中我們討論了建立一個(gè)二叉搜索樹(shù)。我們知道，當(dāng)樹(shù)變得不平衡時(shí)get和put操作會(huì)使二叉搜索樹(shù)的性能降低到O(n)。在這一節(jié)中我們將看到一種特殊的二叉搜索樹(shù)，它可以自動(dòng)進(jìn)行調(diào)整，以確保樹(shù)隨時(shí)都保持平衡。這種樹(shù)被稱為AVL樹(shù)，命名源于其發(fā)明者：G.M. Adelson-Velskii 和 E.M. Landis。
AVL樹(shù)實(shí)現(xiàn)抽象數(shù)據(jù)類型Map就像一個(gè)普通的二叉搜索樹(shù)，唯一不同的是這棵樹(shù)的工作方式。為實(shí)現(xiàn)我們的AVL樹(shù)我們需要在樹(shù)中的每個(gè)節(jié)點(diǎn)加入一個(gè)平衡因子并跟蹤其變化情況。我們通過(guò)比較每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度完成比較。更正式地講，我們定義一個(gè)節(jié)點(diǎn)的平衡因子為左子樹(shù)和右子樹(shù)的高度之差。
$$balanceFactor = height(leftSubTree) - height(rightSubTree)$$
利用以上對(duì)平衡因子的定義，如果平衡因子大于零，我們稱子樹(shù)“左重”(left-heavy)。如果平衡因子小于零，那么子樹(shù)“右重”(right-heavy)。如果平衡因子為零，則樹(shù)是完全平衡的。為實(shí)現(xiàn)AVL樹(shù)，目的是得到一棵平衡的樹(shù)，我們定義平衡因子如果是 -1，0 或 1，那么這棵樹(shù)是平衡的。一旦樹(shù)中節(jié)點(diǎn)的平衡因子超出了這個(gè)范圍，我們需要有一個(gè)把樹(shù)恢復(fù)平衡的過(guò)程。圖 1 是一個(gè)不平衡的“右重”樹(shù)的例子，其中每個(gè)節(jié)點(diǎn)都標(biāo)注了平衡因子。
圖 1：一棵標(biāo)注了平衡因子的不平衡的右重樹(shù)
AVL樹(shù)性能在我們繼續(xù)進(jìn)行之前讓我們看看引入這個(gè)新的平衡因子的結(jié)果。我們的要求是，確保樹(shù)上的平衡因子始終為 -1，0 或 1。我們可以通過(guò)對(duì)鍵的操作得到更好的時(shí)間復(fù)雜度。首先，我們要思考如何利用這個(gè)平衡條件去改變最壞情況下的樹(shù)。有兩種可能性需要考慮，左重樹(shù)和右重樹(shù)。如果我們考慮樹(shù)的高度為 0，1，2 和 3，圖 2 舉出了在新規(guī)則下可能出現(xiàn)的最不平衡的左重樹(shù)的例子。
圖 2：最壞情況下的左重AVL樹(shù)
讓我們看看樹(shù)上的節(jié)點(diǎn)的總數(shù)。我們看到一棵高度為 0 的樹(shù)有 1 個(gè)節(jié)點(diǎn)，一個(gè)高度為 1 的樹(shù)有 1 + 1 = 2 個(gè)節(jié)點(diǎn)，一個(gè)高度為 2 的樹(shù)有 1 + 1 + 2 = 4 個(gè)節(jié)點(diǎn)，一棵高度為 3 的樹(shù)有 1 + 2 + 4 = 7 個(gè)節(jié)點(diǎn)。概括起來(lái)，高度為h的樹(shù)的節(jié)點(diǎn)數(shù)（Nh）為：
$$N_h = 1 + N_{h-1} + N_{h-2}$$
可能你很熟悉這個(gè)公式，因?yàn)樗挽巢瞧跣蛄蟹浅Ｏ嗨啤Ｎ覀兛梢岳眠@個(gè)公式通過(guò)樹(shù)中的節(jié)點(diǎn)的數(shù)目推導(dǎo)出一個(gè)AVL樹(shù)的高度。在我們的印象中，斐波那契數(shù)列與斐波那契數(shù)的關(guān)系為：
$$F_0 = 0
F_1 = 1
F_i = F_{i-1} + F_{i-2} text{ for all } i ge 2$$
數(shù)學(xué)中一個(gè)重要的結(jié)果是，隨著斐波那契序列的數(shù)字越來(lái)越大，F(xiàn)i / Fi?1 越來(lái)越接近于黃金比例 Φ：
$$Φ = frac{1 + sqrt{5}}{2}$$
如果你想看到上式的推導(dǎo)過(guò)程你可以查閱相關(guān)的數(shù)學(xué)資料。我們簡(jiǎn)單地將這個(gè)方程 Fi 近似為：
$$F_i =Φ^i/sqrt{5}$$
如果利用這種近似我們可以將 Nh 的方程改寫(xiě)為：
$$N_h = F_{h+2} - 1, h ge 1$$
通過(guò)黃金比例近似代替斐波那契數(shù)列的項(xiàng)我們可以得到：
$$N_h = frac{Φ^{h+2}}{sqrt{5}} - 1$$
如果我們整理這些方程的項(xiàng)，并且兩邊都以 2 為底取對(duì)數(shù)，然后求解h，則可以導(dǎo)出：
$$log{N_h+1} = (H+2)log{Φ} - frac{1}{2} log{5}
h = frac{log{N_h+1} - 2 log{Φ} + frac{1}{2} log{5}}{log{Φ}}
h = 1.44 log{N_h}$$
這個(gè)推導(dǎo)過(guò)程告訴我們，在任何時(shí)候我們的AVL樹(shù)的高度等于樹(shù)中節(jié)點(diǎn)數(shù)以 2 為底的對(duì)數(shù)的常數(shù)（1.44）倍。這對(duì)我們搜索AVL樹(shù)來(lái)說(shuō)是好消息因?yàn)樗拗屏怂阉鞯膹?fù)雜度到O(logN)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/37752.html
摘要：一旦子樹(shù)平衡因子為零，那么父節(jié)點(diǎn)的平衡因子不會(huì)發(fā)生改變。新根的父節(jié)點(diǎn)將成為舊根的父節(jié)點(diǎn)。因?yàn)槠渌僮鞫际且苿?dòng)整個(gè)子樹(shù)，被移動(dòng)的子樹(shù)內(nèi)的節(jié)點(diǎn)的平衡因子不受旋轉(zhuǎn)的影響。讓表示以為根節(jié)點(diǎn)的子樹(shù)的高度。 既然，我們已經(jīng)證明，保持 AVL 樹(shù)的平衡將會(huì)使性能得到很大的提升，那我們看看如何在程序中向樹(shù)插入一個(gè)新的鍵值。因?yàn)樗械男骆I是作為葉節(jié)點(diǎn)插入樹(shù)的，而新葉子的平衡因子為零，所以我們對(duì)新插入的節(jié)...
摘要：可以看到，一次左單旋將右側(cè)子樹(shù)的高度減小了，而左側(cè)子樹(shù)的高度增加了。如圖，對(duì)進(jìn)行右單旋，需要左子樹(shù)的右子樹(shù)的高度小于等于左子樹(shù)的高度，否則不能達(dá)到平衡的效果，只是把不平衡性從左邊轉(zhuǎn)移到了右邊。 AVL樹(shù) 普通二叉搜索樹(shù)可能出現(xiàn)一條分支有多層，而其他分支卻只有幾層的情況，如圖1所示，這會(huì)導(dǎo)致添加、移除和搜索樹(shù)具有性能問(wèn)題。因此提出了自平衡二叉樹(shù)的概念，AVL樹(shù)（阿德?tīng)柹?維爾斯和蘭迪斯樹(shù)...
摘要：容忍不平衡紅黑樹(shù)的思路的核心是增大了可容忍的高度差，從而實(shí)現(xiàn)既保證查詢效率，也保證了插入和刪除后調(diào)整平衡的效率。紅黑樹(shù)的查詢效率是略低于樹(shù)的，但是紅黑樹(shù)通過(guò)犧牲了少許查詢效率，使插入刪除后的調(diào)整效率達(dá)到了常數(shù)級(jí)別。 定義 Wikipedia - AVL樹(shù) 在計(jì)算機(jī)科學(xué)中，AVL樹(shù)是最早被發(fā)明的自平衡二叉查找樹(shù)。在AVL樹(shù)中，任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹(shù)的最大高度差為1，因此它也被稱為高度平衡...
閱讀 3352·2021-11-22 15:22
閱讀 2877·2021-10-12 10:12
閱讀 2171·2021-08-21 14:10
閱讀 3837·2021-08-19 11:13
閱讀 2856·2019-08-30 15:43
閱讀 3238·2019-08-29 16:52
閱讀 456·2019-08-29 16:41
閱讀 1444·2019-08-29 12:53
