有關BST搜索樹轉換為AVL高度平衡樹的旋轉問題

最近在復習數(shù)據(jù)結構，看到BST的時候遇到了問題，就是當刪除或增加樹中節(jié)點時，要求保證樹的高度平衡行，也就是使BST成為AVL。

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

后來看了很多資料，說LL、RR、LR、RL啥的，沒看懂。之后經過和同學研究發(fā)現(xiàn)了一個特性，就是offending node與其回溯路徑上的最近的兩個點有大小關系。

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

看了很多書，都說什么左旋轉啊右旋轉啊，像上圖這種情況還比較復雜，需要先左旋轉后右旋轉。

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

網(wǎng)頁題目：有關BST搜索樹轉換為AVL高度平衡樹的旋轉問題
轉載源于：http://muchs.cn/article44/gphgee.html

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

廣告

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