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则进行失衡调整，各种情况上文有分析

大家可以很容易的实现。上文提到的平衡处理情况，很多书籍都有。