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

義馬網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,義馬網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為義馬1000+提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的義馬做網(wǎng)站的公司定做！

后來(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ù)上。

網(wǎng)頁(yè)題目：有關(guān)BST搜索樹(shù)轉(zhuǎn)換為AVL高度平衡樹(shù)的旋轉(zhuǎn)問(wèn)題
轉(zhuǎn)載源于：http://chinadenli.net/article44/gphgee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、域名注冊(cè)、網(wǎng)站排名、定制網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)