建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
最近在復(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)站題目：有關(guān)BST搜索樹(shù)轉(zhuǎn)換為AVL高度平衡樹(shù)的旋轉(zhuǎn)問(wèn)題
文章位置：http://www.ef60e0e.cn/article/gphgee.html
