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

最近在複習資料結構，看到BST的時候遇到了問題，就是當删除或增加樹中節點時，要求保證樹的高度平衡行，也就是使BST成為AVL。

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

<a href="http://s3.51cto.com/wyfs02/M01/09/F6/wKiom1LLjJyS8zHjAAA-UEATkyU808.jpg" target="_blank"></a>

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

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

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

本文轉自 rickqin 51CTO部落格，原文連結:http://blog.51cto.com/rickqin/1349348