数据结构二叉平衡树

数据结构二叉平衡树第1页，课件共40页，创作于2023年2月动态查找树表—平衡二叉树LL型LR型RR型RL型应用举例造成不平衡的原因总结第2页，课件共40页，创作于2023年2月平衡二叉树由关键字序列3，1，2，5，4构造而得的二叉查找树由关键字序列1，2，3，4，5构造而得的二叉查找树，ASL=（1+2+3+4+5）/5=3ASL=（1+2+2+3+3）/5=2.2(a)(b)2134535412第3页，课件共40页，创作于2023年2月根据不同的关键字输入序列，可以生成各种不同形态的二叉查找树，其性能差别很大从（a）图知，其已蜕变成单分支树，平均查找时间为（N+1）/2与顺序查找相同。所以，含有n个结点的二叉查找树的平均查找长度和树的形态有关。在某些情况下，需要将二叉查找树进行平衡化处理，将其调整为平衡二叉树时，来提高它的查找性能。平衡二叉树第4页，课件共40页，创作于2023年2月平衡二叉树二叉平衡树：树中每个结点的左、右子树深度之差的绝对值不大于1，即。hL-hR<=1第5页，课件共40页，创作于2023年2月平衡二叉树结点的平衡因子：该结点的左子树的深度减去它的右子树的深度平衡二叉树所有结点的平衡因子只可能为：-1，0，1。第6页，课件共40页，创作于2023年2月平衡二叉树54821非平衡树平衡因子>10122054820011平衡因子<=1平衡树第7页，课件共40页，创作于2023年2月平衡二叉树的构造1）新结点插在平衡因子值为0的结点左或右都不会造成不平衡。平衡结点50左重结点右重结点5040555035602）新结点插在平衡因子值为1的结点的右分支，或者-1的结点的左分支，该结点也不会造成不平衡。1-10005014050-160第8页，课件共40页，创作于2023年2月平衡二叉树的构造3）新结点插在平衡因子值为1的结点的左分支上，或者为-1的结点的右分支上，此时，该结点的平衡因子的绝对值大于1，造成二叉查找树不平衡。506040453520插入结点20后，根结点的平衡因子由1变为210000000112第9页，课件共40页，创作于2023年2月平衡二叉树的构造插入结点70后，根结点的平衡因子由-1变为-2506040655570-10000000-1-1-2第10页，课件共40页，创作于2023年2月平衡二叉树的构造1.LL型新结点插在左重结点A（A是离新结点插入位置最近的左重结点地址）的左孩子的左分支上。如下图棕色代表新结点，称LL型。ABBLBRARABBLARh-1h-1h-1h-1平衡二叉查找树插入x后不再平衡1ABBLBRARhh-1X2第11页，课件共40页，创作于2023年2月平衡二叉树的构造1.LL型调整过程：1）将BA向右旋转90度，把B的右孩子变为A的左孩子2）A变为B的右孩子，B带替A的位置。ABBLBRARhh-1X2ABBLBRARhh-1X0第12页，课件共40页，创作于2023年2月平衡二叉树的构造2.LR型

新结点插在左重结点A（A是离新结点插入位置最近的左重结点地址）的左孩子的右孩子的左分支上。如下图棕色代表新结点，称LR型。1BCRABBLARh-1CCLh-2h-1BCRABBLARh-1CCLX2第13页，课件共40页，创作于2023年2月平衡二叉树的构造2.LR型调整过程----①：

1.将CB向左旋转90度，把CL变为B的右子树，把B变为C的左孩子；h-1BCRABBLARh-1CCL2h-1CRABBLARh-1CCLX2X第14页，课件共40页，创作于2023年2月平衡二叉树的构造2.LR型调整过程----②：

2)将BCA向右旋转90度，把C的右孩子变为A的左孩子，A变为C的右孩子；C带替A的位置。h-1CRABBLARh-1CCLX2h-1CRABBLARh-1CCLX0第15页，课件共40页，创作于2023年2月平衡二叉树的构造3.RR型

新结点插在右重结点A（A是离新结点插入位置最近的右重结点地址）的右孩子的右分支上。如下图棕色代表新结点，称RR型。-1AALh-1BRABBLh-1AALh-1-2BRABBLhX第16页，课件共40页，创作于2023年2月平衡二叉树的构造3.RR型调整过程：

将BA向左旋转90度，把B的左孩子变为A的右孩子，A变为B的左孩子，B带替A的位置。AALh-1-2BRABBLhXALh-10BRABBLhX第17页，课件共40页，创作于2023年2月平衡二叉树的构造4.RL型

新结点插在右重结点A（A是离新结点插入位置最近的右重结点地址）的右孩子的左孩子的右分支上。如下图棕色代表新结点，称RL型。-1AALh-1BRABCLCRCh-2AALh-1BRABCLCRCXh-1-2第18页，课件共40页，创作于2023年2月平衡二叉树的构造4.RL型调整过程-----①：

1)将CB向右旋转90度，把CR变为B的左子树，把B变为C的右孩子AALh-1BRABCLCRCXh-1-2AALh-1BRABCLCRCXh-1-2第19页，课件共40页，创作于2023年2月平衡二叉树的构造4.RL型调整过程-----②：

2)将BCA向左旋转90度，把C的左孩子变为A的右孩子，A变为C的左孩子；最后，C带替A的位置。AALh-1BRABCLCRCXh-1-2ALh-1BRABCLCRCXh-10第20页，课件共40页，创作于2023年2月平衡二叉树的构造ABCX2LLABCX2LRABCX-2RRABCX-2RL第21页，课件共40页，创作于2023年2月平衡二叉树的构造例如:依次插入关键字5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转第22页，课件共40页，创作于2023年2月平衡二叉树的构造42658942689向左旋转一次继续插入关键字95第23页，课件共40页，创作于2023年2月平衡二叉树的查找性能分析

在平衡树上进行查找的过程和二叉查找树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。问：含n

个关键字的二叉平衡树可能达到的最大深度是多少？第24页，课件共40页，创作于2023年2月平衡二叉树的查找性能分析n=0空树最大深度为0n=1最大深度为1n=2最大深度为2第25页，课件共40页，创作于2023年2月平衡二叉树的查找性能分析n=4最大深度为3n=7最大深度为4第26页，课件共40页，创作于2023年2月平衡二叉树的查找性能分析反过来问，深度为h

的二叉平衡树中所含结点的最小值Nh是多少？h=0N0=0h=1h=2h=3N1=1N2=2N3=4一般情况下，Nh=Nh-1+Nh-2+1利用归纳法可证得，Nh=Fh+2-1第27页，课件共40页，创作于2023年2月平衡二叉树的查找性能分析3）因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和

log(n)

相当。1）由此推得，深度为

h的二叉平衡树中所含结点的最小值Nh=h+2/5-12）反之，含有n

个结点的二叉平衡树能达到的最大深度hn=log(5(n+1))-2第28页，课件共40页，创作于2023年2月课堂练习2、按次序输入关键字：e,i,p,k,m,l,b，试画出AVL树的构造和调整过程。1、按次序输入关键字：1,2,3,4,5,6,7，试画出AVL树的构造和调整过程。第29页，课件共40页，创作于2023年2月程序讲解-结点构造typedefstructBSTNode{ ElemType data;

int bf;//平衡因子

structBSTNode *lchild,*rchild}BSTNode,*BSTree第30页，课件共40页，创作于2023年2月程序讲解-右旋转voidR-Rotate(BSTree&p){ lc=p->lchild p->lchild=lc->rchild; lc->rchild=p; p=lc;}ABX2plcABp1ARh-1BLARBRBRXBL00第31页，课件共40页，创作于2023年2月程序讲解-左旋转voidL-Rotate(BSTree&p){ rc=p->rchild p->rchild=rc->lchild; rc->lchild=p; p=rc;}AB-2ABXprcpALBLBRh-1-1XBRBLAL00第32页，课件共40页，创作于2023年2月程序讲解-主程序StatusInsertVAL(BSTree&T,ElemTypee,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;returnOK; } if(EQ(e.key,T->data.key){Taller=FALSE;returnERROR} if(LT(e.key,T->data.key) //插入到左子树

else //插入到右子树第33页，课件共40页，创作于2023年2月程序讲解-主程序//插入到T的左子树if(!InsertVAL(T->lchild,e,Taller))returnERROR;//子树中已有eif(taller){ switch(T->bf){ caseLH://原来左子树高，插入左子树后更高，需要平衡

LeftBalance(T);taller=FALSE;break; caseEH://原来平衡，插入左子树后，则长高

T->bf=LH;taller=TRUE;break; caseRH://原来右子树重，左子树长高后，则平衡

T->bf=EH;taller=FALSE;break; }//switch}//if(taller)第34页，课件共40页，创作于2023年2月程序讲解-左平衡voidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH://插入到左子树的左子树中

T->bf=lc->bf=EH;R_Rotate(T);break; ABARTlch-1BRh21ABARh-1BRh00第35页，课件共40页，创作于2023年2月程序讲解-左平衡ABARTlch-1CR2-1CBLrd1ABARCRCBLCL0-10CLh-2(a)ABARCRCBLCL022第36页，课件共40页，创作于2023年2月程序讲解-左平衡ABARTlch-12-1CBLrd-1ABARCLCBLCR100CRCLh-2(b)ABARCLCBLCR121第37页，课件共40页，创作于2023年2月程序讲解-左平衡ABART