939
AVL樹的刪除探討
AVL樹的刪除很多教材上都沒有提供，本人對AVL樹有著較為深入的研究。現在曬出大體的算法思想。
3.2．1 遞歸法
遞歸實現AVL樹的結點刪除的思想如下。
在AVL樹T上刪除值為E的結點步驟如下：
（1） 若樹T為空，返回0退出否則到（2）;
（2） 比較T的數據和E，若相等跳到（3），若E小於T->data跳到（4），若E大於T->data則跳到（5）
（3） 分析T結點的類型
(3.1)若T是葉子結點則直接刪除,樹變矮即lower=1；
(3.2)若T隻有右子樹TR則將右子樹結點的值賦給T，刪除TR結點將T->rchild=NULL，lower=1;
(3.3)若T有左子樹，則找到其中序遍曆的前驅結點P，將P結點值用臨時變量temp保存，並且用指針Tptr保存T；遞歸刪除結點P；將Tptr所指結點即原T結點的值更新為temp；
（4）在左子樹T->lchild中遞歸刪除值為E的結點，若刪除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0返回0退出；若lower=1則進行失衡調整各種情況上文有分析
（5）在右子樹T->rchild中遞歸刪除值為E的結點，若刪除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0返回0退出；若lower=1則進行失衡調整，各種情況上文有分析
大家可以很容易的實現。上文提到的平衡處理情況，很多書籍都有。
最後更新：2017-04-02 05:21:05