在這篇
文章里說了,AVL樹平衡的兩個條件是:1)首先,二叉查找樹要求一個樹的根節點必然大于(或小于)其左子樹中的所有節點,
同時必然小于(或大于)其右子樹中的所有節點,也就是說,如果按照中序遍歷二叉查找樹,
它必然是嚴格遞增(或遞減)的.2)AVL樹的平衡條件要求任何一顆子樹,其左右子樹的高度差不超過1.我們要求一顆樹是AVL樹,必須嚴格符合以上的兩
個條件.
可以從這兩個條件著手考慮AVL樹中節點的刪除.
首先,采用二叉查找樹的刪除節點算法刪除一個節點,這個算法在
這里有闡述, 此時必然保證了第一個條件.
其次, 從所刪除節點的父節點開始向上搜索,看看哪里出現了不平衡的地方, 出現不平衡的情況肯定是因為這條路徑上一個節點的兄弟節點高度大于該節點高度,可以通過旋轉將這個兄弟節點上升一層, 這樣就滿足了第二個條件.
以一個例子進行說明:
10 10 18
/ \ / \ / \
5 18 5 18 10 12
/ / \ ==> / \ ==> / / \
4 12 19 12 19 5 11 19
/ /
11 11
假設這里要刪除的節點是4,在刪除了節點4之后, 沿著4的父節點向上查詢, 看看哪里出現了不平衡的情況, 發現節點5的高度比它的兄弟節點低了2, 那么這里要做的就是把這個兄弟節點,也就是18往上移一層, 采用的就是AVL樹的單旋轉方法,最后樹重新達到了AVL樹的兩個條件.
本來想實驗一下這個算法,但是原來
這里的實現中, 節點的struct沒有保存父節點的指針, 修改起來比較麻煩, 就不做實現了.
不知道這個算法是不是正確的,目前僅是我憑空的推理, 如果有其它地方提到了別的AVL樹刪除節點算法, 或者有地方證實了這個算法是可行的,請告訴我一聲,謝謝.
補充:
如果這個算法是可行的,那么還有進一步優化的可能.
分兩種情況:1)刪除節點有兩個子節點, 此時, 替代該節點的新結點, 其高度不會發生變化, 也就不會破壞平衡, 此時不需要進行旋轉操作, 也就不需要往上走查詢平衡是否被破壞了.
2)刪除節點只有一個節點或者沒有節點,此時平衡才有可能被破壞, 按照上面的算法進行平衡操作.