愛(ài)華網(wǎng)本文由作者收集整理所得，作者不保證內(nèi)容的正確行，轉(zhuǎn)載請(qǐng)標(biāo)明出處。
作者：關(guān)新全
1、AVL的插入算法描述
在平衡的二叉排序樹(shù)T上插入一個(gè)關(guān)鍵碼為kx的新元素，遞歸算法可描述如下：
(一)若T為空樹(shù)，則插入一個(gè)數(shù)據(jù)元素為kx的新結(jié)點(diǎn)作為T(mén)的根結(jié)點(diǎn)，樹(shù)的深度增1；
(二)若kx和T的根結(jié)點(diǎn)關(guān)鍵碼相等，則不進(jìn)行插入；
(三)若kx小于T的根結(jié)點(diǎn)關(guān)鍵碼，而且在T的左子樹(shù)中不存在與kx有相同關(guān)鍵碼的結(jié)點(diǎn),則將新元素插入在T的左子樹(shù)上，并且當(dāng)插入之后的左子樹(shù)深度增加1時(shí)，分別就下列情況進(jìn)行處理：
⑴ T的根結(jié)點(diǎn)平衡因子為-1(右子樹(shù)的深度大于左子樹(shù)的深度)，則將根結(jié)點(diǎn)的平衡因子更改為0，T的深度不變；
⑵ T的根結(jié)點(diǎn)平衡因子為0(左、右子樹(shù)的深度相等)，則將根結(jié)點(diǎn)的平衡因子更改為1，T的深度增加1；
⑶ T的根結(jié)點(diǎn)平衡因子為1(左子樹(shù)的深度大于右子樹(shù)的深度),則若T的左子樹(shù)根結(jié)點(diǎn)的平衡因子為1,需進(jìn)行單向右旋平衡處理并且在右旋處理之后，將根結(jié)點(diǎn)和其右子樹(shù)根結(jié)點(diǎn)的平衡因子更改為0，樹(shù)的深度不變；若T的左子樹(shù)根結(jié)點(diǎn)平衡因子為-1，需進(jìn)行先左后右雙向旋轉(zhuǎn)平衡處理，并且在旋轉(zhuǎn)處理之后，修改根結(jié)點(diǎn)和其左、右子樹(shù)根結(jié)點(diǎn)的平衡因子，樹(shù)的深度不變。
（四） 若kx大于T的根結(jié)點(diǎn)關(guān)鍵碼，而且在T的右子樹(shù)中不存在與kx有相同關(guān)鍵碼的結(jié)點(diǎn)，則將新元素插入在T的右子樹(shù)上并且當(dāng)插入之后的右子樹(shù)深度增加1時(shí)，分別就不同情況處理之。其處理操作和（三）中所述相對(duì)稱(chēng)。
AVL樹(shù)的四種情況：
1.簡(jiǎn)單右旋：當(dāng)插入項(xiàng)位于最近的平衡因子為+2的祖先節(jié)點(diǎn)的左孩子的左子樹(shù)中時(shí)采用。見(jiàn)圖1-1.
圖1-1 簡(jiǎn)單右旋
圖1-1中，將新節(jié)點(diǎn)插入到A節(jié)點(diǎn)的左孩子B的左子樹(shù)L(B)中。
簡(jiǎn)單右旋的操作步驟如下：
1.A的父指針指向B
2.A的左孩子指向B的右孩子
3.B的右孩子指向A。
4.更改A的平衡因子為0，更改B的平衡因子為0.
注意L（B）中的平衡因子在添加節(jié)點(diǎn)回溯時(shí)已經(jīng)進(jìn)行了修改，其他部分的平衡因子不變。（添加節(jié)點(diǎn)回溯將在稍后介紹）。
2.簡(jiǎn)單左旋：當(dāng)插入項(xiàng)位于最近的平衡因子為-2的祖先節(jié)點(diǎn)的右孩子的右子樹(shù)中時(shí)。如圖1-2.
圖1-2 簡(jiǎn)單左旋
圖1-2中，新節(jié)點(diǎn)插入到了A節(jié)點(diǎn)右孩子B的右子樹(shù)R(B)中，使用簡(jiǎn)單左旋后，二叉樹(shù)變的平衡。
簡(jiǎn)單左旋的步驟如下：
1.A的父指針指向B
2.A的右孩子指向B的左孩子
3.B的左孩子指向A
4.修改B的平衡因子為0，修改A的平衡因子為0
5.R（B）中的平衡因子在添加新節(jié)點(diǎn)回溯過(guò)程中進(jìn)行修改，其他部分的平衡因子不變。
3.左右旋：當(dāng)插入項(xiàng)位于最近的平衡因子為+2的祖先節(jié)點(diǎn)的左孩子的右子樹(shù)中時(shí)，見(jiàn)圖1-3.
圖1-3 左右旋(LRL)
從圖1-3可以看出，新節(jié)點(diǎn)插入到了A節(jié)點(diǎn)的左孩子B的右孩子C的左子樹(shù)中。
基本操作步驟為：
1.B的右兒子指向C的左兒子
2.C的左兒子指向B
3.A的父指針指向C
4.A的左兒子指向C的右兒子
5.C的右兒子指向A
6.B的平衡因子置為0，C的平衡因子置為0，A的平衡因子置為-1.L（C）中的平衡因子在回溯的時(shí)候進(jìn)行修改。
注意，圖1-3所示的為，新節(jié)點(diǎn)插入到A節(jié)點(diǎn)的左孩子B的右孩子C的左子樹(shù)中，稱(chēng)這種情況為（LRL），還有一種情況是，新節(jié)點(diǎn)插入到A節(jié)點(diǎn)的左孩子B的右孩子C的右子樹(shù)中，這種情況稱(chēng)為（LRR），LRR的操作步驟與LRL相似，就是第6步不同。
LRR第6步為：
LRR中平衡因子B修改為+1，C修改為0，A修改為0，R（C）中的平衡因子在回溯過(guò)程中進(jìn)行更改。
LRR參考圖1-4.
圖1-4 左右旋（LRR）
4.右左旋：當(dāng)插入項(xiàng)位于最近的平衡因子為-2的祖先節(jié)點(diǎn)的右孩子的左子樹(shù)中時(shí)使用。見(jiàn)圖1-5.
圖1-5 右左旋（RLL）
圖1-5中，新節(jié)點(diǎn)插入到了A的右孩子B的左孩子C的左子樹(shù)中。
基本操作步驟：
1.B的左孩子指向C的右孩子
2.C的右孩子指向B
3.A的父指針指向C
4.A的右孩子指向C的左孩子
5.C的左孩子指向A
6.A的平衡因子改為0，B的平衡因子為-1，C的平衡因子為0，L（C）的平衡因子在回溯過(guò)程中進(jìn)行修改。
與左右旋相似，右左旋的第二種情況稱(chēng)為（RLR），旋轉(zhuǎn)后見(jiàn)圖1-6.
圖1-6 右左旋（RLR）
RLR與RLL的前五步相同，RLR的第六步為：
RLR需要將A的平衡因子修改為+1，將B的平衡因子修改為0，將C的平衡因子修改為0。R（C）中的平衡因子在回溯過(guò)程中修改。
注意：旋轉(zhuǎn)后，路徑上剩余的節(jié)點(diǎn)的平衡因子不需要改變。（這個(gè)自己可以很容易推導(dǎo)出來(lái)）
如何插入：
(1)、如何回溯修改祖先結(jié)點(diǎn)的平衡因子
我們知道，在AVL樹(shù)上插入一個(gè)新結(jié)點(diǎn)后，有可能導(dǎo)致其他結(jié)點(diǎn)BF（平衡因子）值的改變，哪些結(jié)點(diǎn)的BF值會(huì)被改變？如何計(jì)算新的BF值呢？要解決這些問(wèn)題，我們必須理解以下幾個(gè)要點(diǎn)：只有根結(jié)點(diǎn)到插入結(jié)（橙色結(jié)點(diǎn)）點(diǎn)路徑（稱(chēng)為插入路徑）上的結(jié)點(diǎn)的BF值會(huì)被改變。如圖2所示，只有插入路徑上結(jié)點(diǎn)（灰色結(jié)點(diǎn)）的BF值被改變，其他非插入路徑上結(jié)點(diǎn)的BF值不變。
當(dāng)一個(gè)結(jié)點(diǎn)插入到某個(gè)結(jié)點(diǎn)的左子樹(shù)時(shí)，該結(jié)點(diǎn)的BF值加1（如圖2的結(jié)點(diǎn)50、43）；當(dāng)一個(gè)結(jié)點(diǎn)插入到某個(gè)結(jié)點(diǎn)的右子樹(shù)時(shí)，該結(jié)點(diǎn)的BF值減1（如圖2的結(jié)點(diǎn)25、30）。如何在程序中判斷一個(gè)結(jié)點(diǎn)是插入到左子樹(shù)還是右子樹(shù)呢？很簡(jiǎn)單，根據(jù)二叉查找樹(shù)的特性可以得出結(jié)論：如果插入結(jié)點(diǎn)小于某個(gè)結(jié)點(diǎn)，則必定是插入到這個(gè)結(jié)點(diǎn)的左子樹(shù)中；如果如果插入結(jié)點(diǎn)大于某個(gè)結(jié)點(diǎn)，則必定插入到這個(gè)結(jié)點(diǎn)的右子樹(shù)中。
修改BF值的操作需從插入點(diǎn)開(kāi)始向上回溯至根結(jié)點(diǎn)依次進(jìn)行，當(dāng)路徑上某個(gè)結(jié)點(diǎn)BF值修改后變?yōu)?，則修改停止。如圖3所示，插入結(jié)點(diǎn)30后，首先由于30<43，將結(jié)點(diǎn)43的BF值加1，使得結(jié)點(diǎn)43的BF值由0變?yōu)?；接下來(lái)由于30>25，結(jié)點(diǎn)25的BF值由1改為0；此時(shí)結(jié)點(diǎn)25的BF值為0，停止回溯，不需要再修改插入路徑上結(jié)點(diǎn)50的平衡因子。道理很簡(jiǎn)單：當(dāng)結(jié)點(diǎn)的BF值由1或-1變?yōu)?，表明高度小的子樹(shù)添加了新結(jié)點(diǎn)，樹(shù)的高度沒(méi)有增加，所以不必修改祖先結(jié)點(diǎn)的平衡因子；當(dāng)結(jié)點(diǎn)的BF值由0變?yōu)?或-1時(shí)，表明原本等高左右子樹(shù)由于一邊變高而導(dǎo)致失衡，整棵子樹(shù)的高度變高，所以必須向上修改祖先結(jié)點(diǎn)的BF值。
（2）、何時(shí)進(jìn)行旋轉(zhuǎn)操作？如何判斷作什么類(lèi)型的旋轉(zhuǎn)？
在回溯修改祖先結(jié)點(diǎn)的平衡因子時(shí)，如果碰到某個(gè)結(jié)點(diǎn)的平衡因子變?yōu)?或-2，表明AVL樹(shù)失衡，這時(shí)需要以該結(jié)點(diǎn)為旋轉(zhuǎn)根，對(duì)最小不平衡子樹(shù)進(jìn)行旋轉(zhuǎn)操作。由于是從插入點(diǎn)開(kāi)始回溯，所以最先碰到的BF值變?yōu)?或-2的結(jié)點(diǎn)必定為最小不平衡子樹(shù)的根結(jié)點(diǎn)。如圖4所示，插入39后，43和50兩個(gè)結(jié)點(diǎn)的BF值都會(huì)變?yōu)?，而必定先訪(fǎng)問(wèn)到結(jié)點(diǎn)43，所以43是最小不平衡子樹(shù)的根。根據(jù)以上Flash動(dòng)畫(huà)演示所示，旋轉(zhuǎn)操作完成后，最小不平衡子樹(shù)插入結(jié)點(diǎn)前和旋轉(zhuǎn)完成后的高度不變，所以可以得出結(jié)論：旋轉(zhuǎn)操作完成后，無(wú)需再回溯修改祖先的BF值。這樣，圖4中的結(jié)點(diǎn)25和50的平衡因子實(shí)際上在插入結(jié)點(diǎn)操作完成后的BF值不變（對(duì)比圖2）。
實(shí)現(xiàn)考慮：
整個(gè)算法需要一個(gè)棧來(lái)配合，首先，在節(jié)點(diǎn)插入時(shí)，從根節(jié)點(diǎn)開(kāi)始判斷，直至找到節(jié)點(diǎn)需要插入的位置，并將經(jīng)過(guò)的整個(gè)路徑放入棧中進(jìn)行存儲(chǔ)。整個(gè)查找過(guò)程時(shí)間復(fù)雜度為log(n).然后按照棧的順序進(jìn)行回溯，修改棧內(nèi)（即插入路徑）節(jié)點(diǎn)的平衡因子的值，直到碰到修改后的值為0的節(jié)點(diǎn)（結(jié)束），或者碰到修改后值為正負(fù)2的節(jié)點(diǎn)（進(jìn)行旋轉(zhuǎn)），整個(gè)回溯過(guò)程最壞會(huì)在log(n)內(nèi)完成，旋轉(zhuǎn)操作是常數(shù)時(shí)間復(fù)雜度。因此，整個(gè)插入過(guò)程的時(shí)間復(fù)雜度為log(n)。（更準(zhǔn)確的說(shuō)在2*log(n)內(nèi)完成）。
本文是作者總結(jié)他人成果之上編寫(xiě)而成，轉(zhuǎn)載引用時(shí)請(qǐng)標(biāo)明出處。
最后感謝那些提供豐富示例的網(wǎng)絡(luò)資源，尤其是參考資料中的那個(gè)連接，連接里樓主不光語(yǔ)言精練，還做了平衡二叉樹(shù)的動(dòng)畫(huà)演示，希望大家多去看看。
參考：
http://webtrados.llh4.com/post/522.html
數(shù)據(jù)結(jié)構(gòu)與算法分析 C++語(yǔ)言描述 第二版jarryNyhoff著。
愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101011/50436.html
