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+1
2、/2 与顺序查找相同。,所以，含有n个结点的二叉查找树的平均查找长度和树的形态有关。,在某些情况下，需要将二叉查找树进行,平衡化,处理，将其调整为,平衡二叉树,时，来提高它的查找性能。,平衡二叉树,平衡二叉树,二叉平衡树：,树中每个结点的左、右子树深度之差的绝对值不大于1，即 。,h,L,-h,R,1,0,1,2,2,0,5,4,8,2,0,0,1,1,平衡因子 lchild,p-lchild=lc-rchild;,lc-rchild=p;,p=lc;,A,B,X,2,p,lc,A,B,p,1,AR,h-1,BL,AR,BR,BR,X,BL,0,0,程序讲解-左旋转,void L-Rotat
3、e(BSTree&p),rc=p-rchild,p-rchild=rc-lchild;,rc-lchild=p;,p=rc;,A,B,-2,A,B,X,p,rc,p,AL,BL,BR,h-1,-1,X,BR,BL,AL,0,0,程序讲解-主程序,Status InsertVAL(BSTree&T,ElemType e,Boolean&taller),if(!T)/空树,T=(BSTree)malloc(sizeof(BSTNode);,if(!T)exit(1);/内存出错,T-data=e;T-lchild=T-rchild=NULL;,T-bf=EH;taller=TRUE;,return
4、 OK;,if(EQ(e.key,T-data.key)Taller=FALSE;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=
5、TRUE;break;,case RH:/原来右子树重，左子树长高后，则平衡,T-bf=EH;taller=FALSE;break;,/switch,/if(taller),程序讲解-左平衡,void LeftBalance(BSTree&T),lc=T-lchild;,switch(lc-bf),case LH:/插入到左子树的左子树中,T-bf=lc-bf=EH;,R_Rotate(T);break;,A,B,AR,T,lc,h-1,BR,h,2,1,A,B,AR,h-1,BR,h,0,0,程序讲解-左平衡,A,B,AR,T,lc,h-1,CR,2,-1,C,BL,rd,1,A,B,AR,
6、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,h-2,(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,
浙ICP备2021020529号-1 | 浙B2-20240490 
