请问一个关于AVL树的删除恩路.

Question

AVL树的插入思路是:
找到那个插入位置,插入结点,然后从插入位置开始向根结点回溯更新每一个结点的高度,如果在这个路径中有一个结点的平衡因子等于2时,说时AVL树的平衡条件在此被破坏,需要进行旋转..  关键操作就在于判断选择AVL树调整方法LL,RR,LR,RL这四种方法的哪一种. 插入操作是通过判断新加入的结点位于破坏平衡结点的左子树的左边(LL),位于破坏平衡结点的左子树的树的右边(LR).们于破坏来平衡结点右子树的右边(RR),位于破坏平衡结点的右子树的左边(RL),这个判断很容易实现.因为我知道那个插入结点的值,所以这个判断很容易实现.

现在问题就来了.在进行删除操作时,我在怎么办呢?我从被删结点向根回溯更新这条路径上每一个结点的高度,这时我如果发现破坏平衡的结点,我要怎么判断采用四种调整方法的哪一种.请明白的朋友给个思路.最好别让我去读别人的代码.那个太难懂了.

Answer 1

删除节点时，把左子树的最大值（或右子树的最小值）替换到要删除的节点，然后从最大值（最小值）原来的位置从下往上调整。印象中是这样的。

Answer 2

AVL树的插入思路是:
找到那个插入位置,插入结点,然后从插入位置开始向根结点回溯更新每一个结点的高度,如果 ...
zhaogengzi 发表于 2011-04-29 18:11

    http://blogold.chinaunix.net/u3/92831/showart_2166582.html

下载源码，在tree_del.c里，看看就明白了。