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