《数据结构-二叉平衡树.ppt》由会员分享,可在线阅读,更多相关《数据结构-二叉平衡树.ppt(40页珍藏版)》请在三一办公上搜索。
1、动态查找树表平衡二叉树,平衡二叉树的定义,如何构造平衡二叉树,平衡二叉树的查找性能分析,小结和作业,课堂练习,程序讲解,动态查找树表平衡二叉树,LL型,LR型,RR型,RL型,应用举例,造成不平衡的原因,总结,平衡二叉树,由关键字序列 3,1,2,5,4构造而得的二叉查找树,由关键字序列 1,2,3,4,5构造而得的二叉查找树,,ASL=(1+2+3+4+5)/5=3,ASL=(1+2+2+3+3)/5=2.2,(a),(b),2,1,3,4,5,3,5,4,1,2,根据不同的关键字输入序列,可以生成各种不同形态的二叉查找树,其性能差别很大,从(a)图知,其已蜕变成单分支树,平均查找时间为(N
2、+1)/2 与顺序查找相同。,所以,含有n个结点的二叉查找树的平均查找长度和树的形态有关。在某些情况下,需要将二叉查找树进行平衡化处理,将其调整为平衡二叉树时,来提高它的查找性能。,平衡二叉树,平衡二叉树,二叉平衡树:,树中每个结点的左、右子树深度之差的绝对值不大于1,即。,平衡二叉树,结点的平衡因子:该结点的左子树的深度减去它的右子树的深度,平衡二叉树所有结点的平衡因子只可能为:-1,0,1。,平衡二叉树,非平衡树,0,1,2,2,0,0,0,1,1,平衡树,平衡二叉树的构造,1)新结点插在平衡因子值为0的结点左或右都不会造成不平衡。,平衡结点,50,左重结点,右重结点,50,40,55,5
3、0,35,60,2)新结点插在平衡因子值为1的结点的右分支,或者-1的结点的左分支,该结点也不会造成不平衡。,1,-1,0,0,0,50,1,40,50,-1,60,平衡二叉树的构造,3)新结点插在平衡因子值为1的结点的左分支上,或者为-1的结点的右分支上,此时,该结点的平衡因子的绝对值大于1,造成二叉查找树不平衡。,20,插入结点20后,根结点的平衡因子由1变为2,平衡二叉树的构造,插入结点70后,根结点的平衡因子由-1变为-2,70,平衡二叉树的构造,1.LL型新结点插在左重结点A(A是离新结点插入位置最近的左重结点地址)的左孩子的左分支上。如下图棕色代表新结点,称LL型。,A,B,BL,
4、BR,AR,A,B,BL,AR,平衡二叉查找树,插入x后不再平衡,1,A,B,BL,BR,AR,X,2,平衡二叉树的构造,1.LL型调整过程:1)将BA向右旋转90度,把B的右孩子变为A的左孩子2)A变为B的右孩子,B带替A的位置。,A,B,BL,BR,AR,X,2,A,B,BL,BR,AR,h-1,X,0,平衡二叉树的构造,2.LR型新结点插在左重结点A(A是离新结点插入位置最近的左重结点地址)的左孩子的右孩子的左分支上。如下图棕色代表新结点,称LR型。,1,B,CR,A,B,BL,AR,C,CL,h-2,B,CR,A,B,BL,AR,C,CL,X,2,平衡二叉树的构造,2.LR型调整过程-
5、:1.将CB向左旋转90度,把CL变为B的右子树,把B变为C的左孩子;,B,CR,A,B,BL,AR,C,CL,2,CR,A,B,BL,AR,C,CL,X,2,X,平衡二叉树的构造,2.LR型调整过程-:2)将BCA向右旋转90度,把C的右孩子变为A的左孩子,A变为C的右孩子;C带替A的位置。,CR,A,B,BL,AR,C,CL,X,2,CR,A,B,BL,AR,C,CL,X,0,平衡二叉树的构造,3.RR型新结点插在右重结点A(A是离新结点插入位置最近的右重结点地址)的右孩子的右分支上。如下图棕色代表新结点,称 RR型。,-1,A,AL,h-1,BR,A,B,BL,A,AL,h-1,-2,B
6、R,A,B,BL,h,X,平衡二叉树的构造,3.RR型调整过程:将BA向左旋转90度,把B的左孩子变为A的右孩子,A变为B的左孩子,B带替A的位置。,A,AL,h-1,-2,BR,A,B,BL,h,X,AL,h-1,0,BR,A,B,BL,h,X,平衡二叉树的构造,4.RL型新结点插在右重结点A(A是离新结点插入位置最近的右重结点地址)的右孩子的左孩子的右分支上。如下图棕色代表新结点,称RL型。,-1,A,AL,h-1,BR,A,B,CL,CR,C,h-2,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,平衡二叉树的构造,4.RL型调整过程-:1)将CB向右旋转90度,把CR
7、变为B的 左子树,把B变为C 的右孩子,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,平衡二叉树的构造,4.RL型调整过程-:2)将BCA向左旋转90 度,把C的左孩子变为A 的右孩子,A变为C的左孩子;最后,C带替A的位置。,A,AL,h-1,BR,A,B,CL,CR,C,X,h-1,-2,AL,h-1,BR,A,B,CL,CR,C,X,h-1,0,平衡二叉树的构造,平衡二叉树的构造,例如:依次插入关键字5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向
8、左旋转,平衡二叉树的构造,9,向左旋转一次,继续插入关键字 9,5,平衡二叉树的查找性能分析,在平衡树上进行查找的过程和二叉查找树相同,因此,查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。,问:含 n 个关键字的二叉平衡树可能达到的最大深度是多少?,平衡二叉树的查找性能分析,n=0,空树,最大深度为0,n=1,最大深度为1,n=2,最大深度为2,平衡二叉树的查找性能分析,n=4,最大深度为3,n=7,最大深度为 4,平衡二叉树的查找性能分析,反过来问,深度为h 的二叉平衡树中所含结点的最小值Nh是多少?,h=0,N0=0,h=1,h=2,h=3,N1=1,N2=2,N3=4,一般
9、情况下,,Nh=Nh-1+Nh-2+1,利用归纳法可证得,,Nh=Fh+2-1,平衡二叉树的查找性能分析,3)因此,在二叉平衡树上进行查找时,查找过程中和给定值进行比较的关键字的个数和 log(n)相当。,1)由此推得,深度为 h 的二叉平衡树中所含结点的最小值 Nh=h+2/5-1,2)反之,含有 n 个结点的二叉平衡树能达到的最大深度 hn=log(5(n+1)-2,课堂练习,2、按次序输入关键字:e,i,p,k,m,l,b,试画出AVL树的构造和调整过程。,1、按次序输入关键字:1,2,3,4,5,6,7,试画出AVL树的构造和调整过程。,程序讲解-结点构造,typedef struct
10、 BSTNodeElemTypedata;intbf;/平衡因子struct BSTNode*lchild,*rchild BSTNode,*BSTree,程序讲解-右旋转,void R-Rotate(BSTree,A,B,X,2,p,lc,A,B,p,1,AR,h-1,BL,AR,BR,BR,X,BL,0,0,程序讲解-左旋转,void L-Rotate(BSTree,A,B,-2,A,B,X,p,rc,p,AL,BL,BR,h-1,-1,X,BR,BL,AL,0,0,程序讲解-主程序,Status InsertVAL(BSTree return ERRORif(LT(e.key,T-dat
11、a.key)/插入到左子树else/插入到右子树,程序讲解-主程序,/插入到T的左子树if(!InsertVAL(T-lchild,e,Taller)return ERROR;/子树中已有eif(taller)switch(T-bf)case LH:/原来左子树高,插入左子树后更高,需要平衡 LeftBalance(T);taller=FALSE;break;case EH:/原来平衡,插入左子树后,则长高 T-bf=LH;taller=TRUE;break;case RH:/原来右子树重,左子树长高后,则平衡 T-bf=EH;taller=FALSE;break;/switch/if(tal
12、ler),程序讲解-左平衡,void LeftBalance(BSTree,A,B,AR,h-1,BR,0,0,程序讲解-左平衡,A,B,AR,T,lc,h-1,CR,2,-1,C,BL,rd,1,A,B,AR,CR,C,BL,CL,0,-1,0,CL,h-2,(a),A,B,AR,CR,C,BL,CL,0,2,2,程序讲解-左平衡,A,B,AR,T,lc,h-1,2,-1,C,BL,rd,-1,A,B,AR,CL,C,BL,CR,1,0,0,CR,CL,(b),A,B,AR,CL,C,BL,CR,1,2,1,程序讲解-左平衡,A,B,AR,T,lc,h-1,CR,2,-1,C,BL,CL,r
13、d,0,A,B,AR,CR,C,BL,CL,0,0,0,(c),A,B,AR,CR,C,BL,CL,0,2,1,程序讲解-左平衡,rd=lc-rchild;switch(rd-bf)case LH:T-bf=RH;lc-bf=EH;break;case EH:T-bf=lc-bf=EH;break;case RH:T-bf=EH;lc-bf=LH;break;rd-bf=EH;L_Rotate(T-lchild)R_Rotate(T);/switch(lc-bf)/LeftBalance,小结和作业,平衡二叉树,1.平衡二叉树的概念,2.如何建立平衡二叉树,3.构造平衡二叉树的基本操作,4.平衡二叉树查找的性能分析,1.LL,2.LR,3.RR,4.RL,作业:9.9(3),9.11,