AVL樹的删除探讨

avl樹的删除很多教材上都沒有提供，本人對avl樹有着較為深入的研究。現在曬出大體的算法思想。

<b> 3.2</b><b>．1 </b><b>遞歸法</b>

遞歸實作avl樹的結點删除的思想如下。

   在avl樹t上删除值為e的結點步驟如下：

（1）       若樹t為空，傳回0退出否則到（2）;

（2）       比較t的資料和e，若相等跳到（3），若e小于t-&gt;data跳到（4），若e大于t-&gt;data則跳到（5）

（3）       分析t結點的類型

(3.1)若t是葉子結點則直接删除,樹變矮即lower=1；

(3.2)若t隻有右子樹tr則将右子樹結點的值賦給t，删除tr結點将t-&gt;rchild=null，lower=1;

(3.3)若t有左子樹，則找到其中序周遊的前驅結點p，将p結點值用臨時變量temp儲存，并且用指針tptr儲存t；遞歸删除結點p；将tptr所指結點即原t結點的值更新為temp；

 （4）在左子樹t-&gt;lchild中遞歸删除值為e的結點，若删除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0傳回0退出；若lower=1則進行失衡調整各種情況上文有分析

 （5）在右子樹t-&gt;rchild中遞歸删除值為e的結點，若删除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0傳回0退出；若lower=1則進行失衡調整，各種情況上文有分析

大家可以很容易的實作。上文提到的平衡處理情況，很多書籍都有。