版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
4.5平衡二叉树假定二叉搜索树中每个结点的查找概率都是相同的,称查找所有结点的比较次数的平均值为树的“平均查找长度”(ASL)。一、什么是平衡二叉树〖例〗搜索树结点不同插入次序,将导致不同的深度和平均查找长度ASL
Jan AprAprFeb
MarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov
(a)自然月份序列ASL(a)=(1+2×2+3×3+4×3+5×2+6×1)/12=3.5
(b)按July,Feb,May,Mar,Aug,Jan,Apr,Jun,Oct,Sept,Nov,Dec
ASL(b)=3.0
(c)月份字符串大小顺序
ASL(c)=6.5
树深在最好的情况下是O(logN),所以,二叉搜索树在最好情况下的查找复杂度是O(logN)。上述ASL的计算结果表明,一棵树的ASL值越小,它的结构越好,与完全二叉树越接近,其查找时间复查度也越接近O(logN)。因此,为了保证二叉搜索树查找的对数级时间效率,应尽可能创建枝繁叶茂的树,而避免树枝过长、过少。最好的结构是完美二叉树,从根到叶的各条路径都是相同的,称这种树为完全平衡的。
二、定义
“平衡因子(BalanceFactor,简称BF):BF(T)=hL-hR, 其中hL和hR分别为T的左、右子树的高度。
平衡二叉树(BalancedBinaryTree)(AVL树)
①空树,或者
②任一结点左、右子树高度差的绝对值不超过1,即|BF(T)|≤1
因此,平衡二叉树上每个结点的平衡因子只可能是-1、0和1,否则,只要有一个结点的平衡因子的绝对值大于1,该二叉树就不是平衡二叉树。三、平衡二叉树的调整
一般的二叉排序树是不平衡的,若能通过某种方法使其既保持有序性,又具有平衡性,就找到了构造平衡二叉排序树的方法,该方法称为平衡化旋转。
在对AVL树进行插入或删除一个结点后,通常会影响到从根结点到插入(或删除)结点的路径上的某些结点,这些结点的子树可能发生变化。这时就需要做“平衡化”处理,即相应的局部“旋转”调整,使得调整后的树达到平衡。1000MarMayNov
2Mar1右单旋
MayMay0
0Mar
0Nov
Nov
不平衡的“发现者”是Mar,“麻烦结点”Nov在发现者右子树的右边, 因而叫RR插入,需要RR旋转(右单旋)AL1
A0BRR插入AL2
A1
BRR旋转0A0BBRBLBRBLBRALBL1.单旋调整cc1010011AugApr2
2May0
LL旋转左单旋1
2May0
0AugMarNov
0AprAug
0MarNov
0
Apr“发现者”是Mar,“麻烦结点”Apr在发现者左子树的左边,因而叫LL插入,需要LL旋转(左单旋)0B1AAR
LL插入1B2AAR
LL旋转BL0B0ABLBRBLBRBRARcc001000110001Jan
0
Apr
1Aug
0
2May
1Mar
0Nov
LR左-右双旋
0
Apr
1Aug
2Mar
0Jan
1May
0NovJan旋转“发现者”是May,“麻烦结点”Jan在左子树的右边,因而叫LR插入,需要LR旋转
LR2LR0B0A插入1
B
A1旋转0or1
0C1or0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.双旋调整DDDDD0Apr200110110200011010001DecJulyFeb
0Apr
1Aug
1Dec
2
Mar
0
Jan0
1May
0July
2
0NovRL
右-左双旋旋转1
Dec
1
Aug
0
Feb
2Mar
1Jan
1May
0July
0Nov
Feb一般情况调整如下:
RL2RLA00B插入A
11B旋转0or1
0C1or0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD101Jan110012110DecMarMay110100AprApr0Feb0July0112020010202011Nov00JuneOctSeptAprJune
110
DecDecMar AugAugFebJanJuly AugFebJuly000
11
JanMar110001June
2May Nov
0May June
1Nov0
Oct
0
Oct0
Sept
注意:有时候插入元素即便不需要调整结构,也可能需要重新计算 一些平衡因子。typedefstructAVLNode*Position;typedefPositionAVLTree;
/*AVL树类型*/typedefstructAVLNode{
ElementTypeData;
/*结点数据*/AVLTreeLeft;/*指向左子树*/AVLTreeRight;/*指向右子树*/intHeight;/*树高*/}四、AVL树的插入intMax(inta,intb){returna>b?a:b;}AVLTreeInsert(AVLTreeT,ElementTypeX){/*将X插入AVL树T中,并且返回调整后的AVL树*/if(!T)
{/*若插入空树,则新建包含一个结点的树*/
T=(AVLTree)malloc(sizeof(structAVLNode));T->Data=X;
T->Height=0;
T->Left=T->Right=NULL;}/*if(插入空树)结束*/elseif(X<T->Data){/*插入T的左子树*/T->Left=Insert(T->Left,X);
/*如果需要左旋*/
if(GetHeight(T->Left)-GetHeight(T->Right)==2)
if(X<T->Left->Data)
T=SingleLeftRotation(T);/*左单旋*/
else
T=DoubleLeftRightRotation(T);/*左-右双旋*/}/*elseif(插入左子树)结束*/elseif(X>T->Data){/*插入T的右子树*/T->Right=Insert(T->Right,X);/*如果需要右旋*/if(GetHeight(T->Left)-GetHeight(T->Right)==-2)
if(X>T->Right->Data)T=SingleRightRotation(T);/*右单旋*/
else
T=DoubleRightLeftRotation(T);/*右-左双旋*/}/*elseif(插入右子树)结束*//*elseX==T->Data,无须插入*/T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1;
/*别忘了更新树高*/returnT;}AVLTreeSingleLeftRotation(AVLTreeA)16.{/*注意:A必须有一个左子结点B*/17./*将A与B做左单旋,更新A与B的高度,返回新的根结点B*/18.19.AVLTreeB=A->Left;20.A->Left=B->Right;21.B->Right=A;22.A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;23.B->Height=Max(GetHeight(B->Left),A->Height)+1;24.25.returnB;26.}27.28.AVLTreeDoubleLeftRightRotation(AVLTreeA)29.{/*注意:A必须有一个左子结点B,且B必须有一个右子结点C*/30./*将A、B与C做两次单旋,返回新的根结点C*/31.32./*将B与C做右单旋,C被返回*/33.A->Left=SingleRightRotation(A->Left);34./*将A与C做左单旋,C被返回*/35.returnSingleLeftRotation(A);36.}37.38./*************************************/39./*对称的右单旋与右-左双旋请自己实现*/40./*************************************/41.AVLTreeSingleLeftRotation(AVLTreeA){/*注意:A必须有一个左子结点B*//*将A与B做左单旋,更新A与B的高度,返回新的根结点B*/
AVLTreeB=A->Left;
A->Left=B->Right;
B->Right=A;
A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;
B->Height=Max(GetHeight(B->Left),A->Height)+1;returnB;
}AVLTreeDoubleLeftRightRotation(AVLTreeA){/*注意:A必须有一个左子结点B,且B必须有一个右子结点C*//*将A、B与C做两次单旋,返回新的根结点C*/A->Left=SingleRightRotation(A->Left);/*将B与C做右单旋,C被返回*/returnSingleLeftRotation(A);/*将A与C做左单旋,C被返回*/}
作业:1、在分量1~11的数组中按从小到大顺序存放11个元素,如果用顺序查找和二分查找分别查找这11个元素,哪个位置的元素在这两种方法的查找中总次数最少?..A.1B.2C.3D.62、在分量1~11的数组中按从小到大顺序存放11个元素,如果进行二分查找,查找次数最少的元素位于什么位置?..A.1B.5C.6D.11测验:1.设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。2.已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树,然后给出该树的后序遍历序列。图6-27二叉树adebfgchkmn3、一棵度为m的树有n个节点。若每个节点直接用m个链指向相应的儿子,则表示这个树所需要的总空间是n*(m+1)(假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟(FirstChild/NextSibling)表示法时,所需的总空间是:..A.3nB.2nC.n*mD.n*(m-1)4、如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结点,那么该完全二叉树共有多少个结点?..A.31B.39C.63D.715、若有一二叉树的总结点数为98,只有一个儿子的结点数为48,则该树的叶结点数是多少?..A.25B.50C.不确定D.这样的树不存在6、设深度为d(只有一个根结点时,d为1)的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为2d-1..A.√B.×7、假定只有四个结点A、B、C、D的二叉树,其前序遍历序列为ABCD,则下面哪个序列是不可能的中序遍历序列?..A.ABCDB.ACDBC.DCBAD.DABC8、对于二叉树,如果其中序遍历结果与前序遍历结果一样,那么可以断定该二叉树________..A.是完全二叉树B.所有结点都没有左儿子C.所有结点都没有右儿子D.这样的树不存在9、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA和FDBEACG,那么该二叉树的前序遍历结果是什么?..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG10、假定只有四个结点A、B、C、D的二叉树,其前序遍历序列为ABCD,则下面哪个序列是不可能的中序遍历序列?..A.ABCDB.ACDBC.DCBAD.DABC11、对于二叉树,如果其中序遍历结果与前序遍历结果一样,那么可以断定该二叉树________..A.是完全二叉树B.所有结点都没有左儿子C.所有结点都没有右儿子D.这样的树不存在12、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA和FDBEACG,那么该二叉树的前序遍历结果是什么?..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG13、非递归方法中序遍历下面这颗二叉树,其堆栈操作序列(P代表为push,O代表为pop)是什么?..A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药品批发行业的数字化营销策略
- 平面设计基础从零开始学汇报制作
- 大数据在企业管理中的应用案例
- 不同地域风格餐饮空间设计解析
- 幼儿爱国课程设计
- 个人品牌形象建立及营销方法
- 幼儿园美语元旦课程设计
- 《摇滚主题电影节研究》
- 宿舍考勤系统课程设计
- 《喘息服务介入自闭症儿童母亲亲职压力缓解的应用研究》
- 2024广西继续教育公需科目(高质量共建“一带一路”)
- 输电线路工频参数测试仪校准规范
- APS系统设计蓝图与方案
- 心爱之物五年级作文精彩开头和结尾10篇
- 我是记忆小达人(课件)-心理健康六年级
- 非ST段抬高型急性冠脉综合征诊断和治疗指南(2024)解读
- YBT 6266-2024《高温纯化炉》规范要求
- 模拟电子技术基础(山东理工大学)智慧树知到期末考试答案章节答案2024年山东理工大学
- 幼儿园跳绳活动方案及总结大班
- (高清版)WST 408-2024 定量检验程序分析性能验证指南
- 流行病学-厦门大学中国大学mooc课后章节答案期末考试题库2023年
评论
0/150
提交评论