那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

AVL树删除节点算法

在这篇文章里说了,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)删除节点只有一个节点或者没有节点,此时平衡才有可能被破坏, 按照上面的算法进行平衡操作.

posted on 2008-09-17 12:38 那谁 阅读(7881) 评论(9)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: AVL树删除节点算法[未登录]  回复  更多评论   

每一次插入的时候,从插入的节点开始往上找,每次遇到一个不平衡的父节点都旋转一次,一直到根节点为止。

删除的时候,将中序右继换过来之后,进行上面的操作。
2008-09-17 12:57 | 陈梓瀚(vczh)

# re: AVL树删除节点算法[未登录]  回复  更多评论   

不一定需要父节点指针,也可以通过保存从根结点到被删除节点的路径,然后网上调整.
2008-09-17 18:08 | 季阳

# re: AVL树删除节点算法  回复  更多评论   

老实说,俺从来没实现过 AVL Tree。实践中,凡是能够使用 AVL Tree 的地方都被 Red-Black Tree 代替了。
2008-09-17 19:40 | Lucifer

# re: AVL树删除节点算法  回复  更多评论   

呵呵什么时候能探讨一下自平衡树(无论AVL还是RB)的节点修改操作?有否除了“节点修改=删除+重新添加”外的更优算法?
2008-09-29 10:57 | E剑仙

# re: AVL树删除节点算法  回复  更多评论   

将18左旋转后到达不到平衡
插入的时候不用插入后才往上找不平衡的结点,直接在找插入的时候就能标记好插入后会导致不平衡的点,然后直接判断如何使用旋转就可以了
2008-10-10 10:12 | dragon

# re: AVL树删除节点算法  回复  更多评论   

“补充:如果这个算法是可行的,那么还有进一步优化的可能.
分两种情况:1)删除节点有两个子节点, 此时, 替代该节点的新结点, 其高度不会发生变化, 也就不会破坏平衡,”

这个说法我有点疑问,比如下面这个例子:
1
/ \
2 3
/
4
如果删除的是结点1,那么3将被替换到1的位置,而并不像你说的那样高度没发生变化。所以我觉得这种情况仍然要进行旋转操作。
不知道我理解的对不对,请多指教。
2009-01-14 03:14 | GUEST

# re: AVL树删除节点算法  回复  更多评论   

用递归最好
2009-02-25 22:57 | zng

# re: AVL树删除节点算法  回复  更多评论   

楼上的楼上GUEST 你的疑问是正确的 不管删除的节点有几个子节点 都是要进行旋转的。
还有就是 你举的这个例子不能通过单旋解决问题 应该要RL旋转才可以 结果应该是这样的
12
 / \
 10 18
/ \  \
5 11  19
2009-09-24 19:31 | kiven

# re: AVL树删除节点算法  回复  更多评论   

Insert 一个结点时, 检查到不平衡时只要一次(LL, LR, RL, RR)调整就可以了;

Delete 一个结点时, 检查到不平衡时需要把不平衡向上传递, 同时可能因为调整后产生不平衡而向下调整;

相关内容可以参见我的博客: http://blog.csdn.net/kyee
2010-06-20 00:00 | Kyee

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理