在这篇
文章里说了,AVL树平衡的两个条件是:1)首先,二叉查找树要求一个树的根节点必然大于(或小于)其左子树中的所有节点,
同时必然小于(或大于)其右子树中的所有节点,也就是说,如果按照中序遍历二叉查找树,
它必然是严格递增(或递减)的.2)AVL树的平衡条件要求任何一颗子树,其左右子树的高度差不超过1.我们要求一颗树是AVL树,必须严格符合以上的两
个条件.
可以从这两个条件着手考虑AVL树中节点的删除.
首先,采用二叉查找树的删除节点算法删除一个节点,这个算法在
这里有阐述, 此时必然保证了第一个条件.
其次, 从所删除节点的父节点开始向上搜索,看看哪里出现了不平衡的地方, 出现不平衡的情况肯定是因为这条路径上一个节点的兄弟节点高度大于该节点高度,可以通过旋转将这个兄弟节点上升一层, 这样就满足了第二个条件.
以一个例子进行说明:
10 10 18
/ \ / \ / \
5 18 5 18 10 12
/ / \ ==> / \ ==> / / \
4 12 19 12 19 5 11 19
/ /
11 11
假设这里要删除的节点是4,在删除了节点4之后, 沿着4的父节点向上查询, 看看哪里出现了不平衡的情况, 发现节点5的高度比它的兄弟节点低了2, 那么这里要做的就是把这个兄弟节点,也就是18往上移一层, 采用的就是AVL树的单旋转方法,最后树重新达到了AVL树的两个条件.
本来想实验一下这个算法,但是原来
这里的实现中, 节点的struct没有保存父节点的指针, 修改起来比较麻烦, 就不做实现了.
不知道这个算法是不是正确的,目前仅是我凭空的推理, 如果有其它地方提到了别的AVL树删除节点算法, 或者有地方证实了这个算法是可行的,请告诉我一声,谢谢.
补充:
如果这个算法是可行的,那么还有进一步优化的可能.
分两种情况:1)删除节点有两个子节点, 此时, 替代该节点的新结点, 其高度不会发生变化, 也就不会破坏平衡, 此时不需要进行旋转操作, 也就不需要往上走查询平衡是否被破坏了.
2)删除节点只有一个节点或者没有节点,此时平衡才有可能被破坏, 按照上面的算法进行平衡操作.