数据结构-二叉平衡树.ppt

动态查找树表平衡二叉树,平衡二叉树的定义,如何构造平衡二叉树,平衡二叉树的查找性能分析,小结和作业,课堂练习,程序讲解,动态查找树表平衡二叉树,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+1）/2 与顺序查找相同。,所以，含有n个结点的二叉查找树的平均查找长度和树的形态有关。在某些情况下，需要将二叉查找树进行平衡化处理，将其调整为平衡二叉树时，来提高它的查找性能。,平衡二叉树,平衡二叉树,二叉平衡树：,树中每个结点的左、右子树深度之差的绝对值不大于1，即。,平衡二叉树,结点的平衡因子：该结点的左子树的深度减去它的右子树的深度,平衡二叉树所有结点的平衡因子只可能为：-1，0，1。,平衡二叉树,非平衡树,0,1,2,2,0,0,0,1,1,平衡树,平衡二叉树的构造,1）新结点插在平衡因子值为0的结点左或右都不会造成不平衡。,平衡结点,50,左重结点,右重结点,50,40,55,50,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,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型调整过程-：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,BR,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变为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,向右旋转一次,先向右旋转再向左旋转,平衡二叉树的构造,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,一般情况下，,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 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-data.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(taller),程序讲解-左平衡,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,rd,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,