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