最近在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)，看到BST的時(shí)候遇到了問(wèn)題，就是當(dāng)刪除或增加樹(shù)中節(jié)點(diǎn)時(shí)，要求保證樹(shù)的高度平衡行，也就是使BST成為AVL。

成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括岐山網(wǎng)站建設(shè)、岐山網(wǎng)站制作、岐山網(wǎng)頁(yè)制作以及岐山網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，岐山網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶(hù)以成都為中心已經(jīng)輻射到岐山省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶(hù)的支持與信任！

后來(lái)看了很多資料，說(shuō)LL、RR、LR、RL啥的，沒(méi)看懂。之后經(jīng)過(guò)和同學(xué)研究發(fā)現(xiàn)了一個(gè)特性，就是offending node與其回溯路徑上的最近的兩個(gè)點(diǎn)有大小關(guān)系。

如上圖，一個(gè)空BST樹(shù)，插入16到樹(shù)中，由于是空樹(shù)，那么16就作為根節(jié)點(diǎn)。之后再輸入3。3比16小，放在16的左邊作為左子節(jié)點(diǎn)，再輸入7，7比16小，走左子樹(shù)一邊，然后7再和3相比較，7比3大，走3的右子樹(shù)。但是如上圖所示，這不是一棵AVL樹(shù)，因?yàn)?6的左子樹(shù)高度為2，右子樹(shù)高度為0，左右高度差的絕對(duì)值為2，超過(guò)了AVL的條件：左右高度絕對(duì)差<2。那么就需要“旋轉(zhuǎn)子樹(shù)”以保證其AVL特性。

看了很多書(shū)，都說(shuō)什么左旋轉(zhuǎn)啊右旋轉(zhuǎn)啊，像上圖這種情況還比較復(fù)雜，需要先左旋轉(zhuǎn)后右旋轉(zhuǎn)。

其實(shí)，經(jīng)過(guò)這些天的研究發(fā)現(xiàn)，以上圖為例，當(dāng)節(jié)點(diǎn)7進(jìn)入樹(shù)之后，打破了平衡，那么就從節(jié)點(diǎn)7開(kāi)始回溯找到offending node，也就是節(jié)點(diǎn)16。然后選擇offending node與回溯路徑上的距離節(jié)點(diǎn)16的最近的兩個(gè)node，也就是節(jié)點(diǎn)3和7。這三個(gè)點(diǎn)選取之后，對(duì)三個(gè)點(diǎn)進(jìn)行大小比較，找出最小、大和中間節(jié)點(diǎn)，比如16、3、7三個(gè)節(jié)點(diǎn)的按大小排序后的順序是3、7、16。然后中間的節(jié)點(diǎn)（節(jié)點(diǎn)7）作為新樹(shù)的根，其左節(jié)點(diǎn)是最小節(jié)點(diǎn)，右節(jié)點(diǎn)是大節(jié)點(diǎn)，然后將新樹(shù)接回原來(lái)的樹(shù)上。

當(dāng)前題目：有關(guān)BST搜索樹(shù)轉(zhuǎn)換為AVL高度平衡樹(shù)的旋轉(zhuǎn)問(wèn)題-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/dcseid.html