登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

聊天机器

Chatbot's private blog

 
 
 

日志

 
 

平衡2叉树  

2009-02-09 18:12:55|  分类: 程序理论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二叉排序树的问题:性能跟输入数据的顺序有关,最好的时候是折半查找性能,最差是顺序查找性能,所以有必要对如何构建这棵树好好研究研究。AVL的诞生(为什么不是BBT,而叫AVL,不解)

定义

平衡因子BF:左子树深度减右子数深度。

AVL所有节点的平衡因子为1,0,-1的二叉排序数称为AVL。

补充定义:

问题节点:当加入一个新节点后导致的、第一个平衡因子不再符合AVL定义的节点。

理论:如果问题节点的子树深度与加入节点前的深度一样,则其上面将不会有问题节点了,这棵树已经是一个AVL了。

分析不平衡的原因:

1)原来问题节点的BF为1,现在在其左子树上加新节点,使得BF=2

2)原来问题节点的BF为-1,现在在其右子树上加新节点,使得BF=-2

1)的讨论

原来                                             现在(加节点后,还没调整)

      问题节点b                                    问题节点b

左树a         右树c                     左树a +1        右树c

设原来a深度为h+1,c深度为h,则b的深度为h+2,a必然可以再细分(h>=0)

          左树a

子树a1     子树a2

a1,a2的设定必然有一个是h(因为a的深度是h+1,a本身一个,所以其子树最大的深度为h),新节点必加入h

的子树,而且加入后,其深度变为h+1(否则子树BF不变,其上面节点的BF不会出问题)

另一个也是h,由上面分析知道另一个可能是h,或h-1(最大的是h,本身是AVL),但如果是h-1则,新加入的

节点将使另一个子树变为h+1,则第一个不满足AVL树的节点将是a,而不是a的parent b节点。

a)考虑新加入的节点在a1中,这就是LL问题(左边的左边)。

解决很容易:将b拉入右树,a上提,a2归入b的左子树

新结构如下:

                a

子树aa1     子树b

                 子树aa1     子树c

从a看进来,树的深度为h+2 ,与原来相同。

b)考虑新加入的节点在a2中,这就是LR问题(左边的右边)。

解决比较复杂,还需要再分析一步:则新a2的深度将会是h+1,则a2又可以仿照前面的a节点写成:

    左树a2

子树aa1     子树aa2

aa1与aa2有一个深度是h,另一个h-1(分析:最大的深度是h,所以必然有一个,而且是新加入节点引起

深度增加的,所以另一个是h-1)

将b拉入右树,a2上提,a2的两棵树分别给a,以及b

新结构如下:

                                                 a2

                        子树a                                            子树b

                 子树a1       aa1                   aa2                             子树c

从a2看进来,树的深度为h+2 ,与原来相同。

2)同理分析:在RR时,将b的右树节点上提,b变为其左节点

                          在RL时,还要在分解,将b的右节点的左节点上移取代b的位置。

(完)

  评论这张
 
阅读(612)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018