数据结构-二叉平衡树.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 BSTNode ElemType data; int bf;/平衡因子 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 ERROR if(LT(e.key, T-data.key) /插入到左子树 else /插入到右子树,程序讲解-主程序,/插入到T的左子树 if(!InsertVAL(T-lchild, e, Taller) return ERROR;/子树中已有e if(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,程序讲解-左平衡,case RH:/插入到左子树的右子树中 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,