溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
最近在復習數據結構，看到BST的時候遇到了問題，就是當刪除或增加樹中節點時，要求保證樹的高度平衡行，也就是使BST成為AVL。
后來看了很多資料，說LL、RR、LR、RL啥的，沒看懂。之后經過和同學研究發現了一個特性，就是offending node與其回溯路徑上的最近的兩個點有大小關系。
如上圖，一個空BST樹，插入16到樹中，由于是空樹，那么16就作為根節點。之后再輸入3。3比16小，放在16的左邊作為左子節點，再輸入7，7比16小，走左子樹一邊，然后7再和3相比較，7比3大，走3的右子樹。但是如上圖所示，這不是一棵AVL樹，因為16的左子樹高度為2，右子樹高度為0，左右高度差的絕對值為2，超過了AVL的條件：左右高度絕對差<2。那么就需要“旋轉子樹”以保證其AVL特性。
看了很多書，都說什么左旋轉啊右旋轉啊，像上圖這種情況還比較復雜，需要先左旋轉后右旋轉。
其實，經過這些天的研究發現，以上圖為例，當節點7進入樹之后，打破了平衡，那么就從節點7開始回溯找到offending node，也就是節點16。然后選擇offending node與回溯路徑上的距離節點16的最近的兩個node，也就是節點3和7。這三個點選取之后，對三個點進行大小比較，找出最小、最大和中間節點，比如16、3、7三個節點的按大小排序后的順序是3、7、16。然后中間的節點（節點7）作為新樹的根，其左節點是最小節點，右節點是最大節點，然后將新樹接回原來的樹上。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
