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