平衡二叉树10.3.2.ppt

1、平衡二叉树(AVL),平衡二叉树的概念,平衡二叉树的查找,平衡二叉树中结点的插入与建立,平衡二叉树中结点的删除,平衡二叉树(AVL),结点的平衡因子（balancdfactor用bf表示）:二叉树中某结点左子树的高度与右子树的高度之差称为该结点的平衡因子.平衡二叉树是另一种形式的二叉查找树。其特点是：左右子树深度之差的绝对值不大于1称有这种特性的二叉树为平衡二叉树。在算法中，可以通过平衡因子来具体实现平衡二叉树的定义。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，则该树称为平衡二叉树。,96,38,24,88,28,11,25,98,0,1,0,1,1,1,0,

2、0,-1,-2,0,1、平衡二叉树插入结点的调整方法,若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，首先从根结点到该新插入结点的路径之逆向根结点方向找第一个失去平衡的结点，然后以该失衡结点和它相邻的刚查找过的两个结点构成调整子树(最小不平衡子树)，即调整子树是指以离插入结点最近,且平衡因子绝对值大于1的结点为根结点的子树,使之成为新的平衡子树。,96,38,24,88,28,11,25,98,2,(1)LL型调整,A,B,f,d,e,h,h,0,1,h,1,2,调整方法：单向右旋平衡，即将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子

3、树则作为A结点的左子树。,B,A,d,e,f,lc=p-lchild;/*lc指向Bp-lchild=lc-rchild;/*把B结点的右子树挂接为A的左子树lc-rchild=p;/*A结点成为B的右孩子p=lc;/*p指向新的根结点,p,p,(2)RR型调整,A,a,B,b,c,h,h,0,1,调整方法：单向左旋平衡：即将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。,B,A,c,a,b,-1,-2,lc=p-rchild;/*lc指向B*/p-rchild=lc-lchild;/*把B结点的左子树挂接为A的右子树*/

4、lc-lchild=p;/*A结点成为B的左孩子*/p=lc;/*p指向新的根结点*/,p,p,(3)LR型调整,A,B,C,n,m,i,e,h,h1,h1,0,0,1,1,1,2,C,B,A,n,m,i,e,调整方法：先左旋转后右旋转平衡,即将A结点的左孩子（即B结点）的右子树的根结点（即C结点）向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。,p,b,c,p-lchild=c-rchild;/*把C的右子树挂接成A的左子树*/b-rchild=c-lchild;/*把C的左子树挂接成B的右子树*/c-lchild=b;/*把B挂接成C的左子树*/c-rchild

5、=p;/*把A挂接成C的右子树*/,（4）RL型调整,A,B,m,C,f,n,t,C,A,B,m,n,t,f,h1,h,h1,调整方法：先右旋转后左旋转平衡,即先将A结点的右孩子B结点的左子树的根结点C结点向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。,0,0,1,-1,1,-2,p-rchild=c-lchild;/*把C的左子树挂接成A的右子树*/b-lchild=c-rchild;/*把C的右子树挂接成B的左子树*/c-rchild=b;/*把B挂接成C的右子树*/c-lchild=p;/*把A挂接成C的左子树*/,p,b,c,平衡二叉树的查找,BSTNod

6、e*SearchBST(BSTNode*bt,KeyTypek)/在以bt为根的平衡二叉树中,查找关键字为k的结点,找到返回指向该结点的/指针,否则返回NULLif(bt=NULL|bt-key=k)returnbt;if(kkey)returnSearchBST(bt-lchild,k);elsereturnSearchBST(bt-rchild,k);,平均查找长度为：O(log2n),平衡二叉树中结点的插入与建立,在平衡二叉树BBST中插入一个结点x的大体步骤如下：像一般的二叉排序树那样插入x；,若BBST为空树，则插入一个数据元素为x的新结点作为BBST的根结点；若x的关键字和BBST

7、的根结点的关键字相等，不能进行插入；若x的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和x有相同关键字的结点，则将x插入在BBST的左子树上；若x的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和x有相同关键字的结点，则将x插入在BBST的右子树上；,沿着插入x的路线返回，逐层回溯，必要时修改x祖先的平衡因子，因为插入x后会使某些子树的高度增加。回溯途中，一旦发现x的某个祖先p失衡，即由pbf=1变成p-bf=2或由p-bf=-1变成p-bf=-2,则旋转以*p为根的子树结构,使之平衡。,例1输入关键字序列16,3,7,11,9,26,18,14,15

8、,给出构造一棵AVL树的步骤。,16,0,3,1,0,7,0,1,2,属于“”型,应该进行RL调整先右旋转后左旋转平衡,RL调整后,11,7,18,3,9,16,26,14,-1,2,0,1,-1,0,0,0,15,1,属于“lchild;If(p1-bf=1)p-lchild=p1-rchild;p1-rchild=p;p-bf=p1-bf=0;p=p1;elseif(p1-bf=-1)p2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)p-bf=p1-bf=0;els

9、eif(p2-bf=1)p1-bf=0;p-bf=-1;elsep1-bf=1;p-bf=0;p=p2;p-bf=0;Taller=0;,P-bf=1,要作LL调整,要作LR调整,平衡二叉树中结点的删除,在平衡二叉树上删除结点x（假定平衡二叉树有且仅有一个结点的值等于x）的大体步骤如下：用一般的二叉排序树的删除算法找到并删除结点x；沿根到被删除结点的路线之逆逐层向上回溯，必要时，修改x祖先结点的平衡因子；回溯途中，一旦发现x的某个祖先p失衡，就要找到并调整其最小不平衡子树，使之平衡；如果旋转之后，子树的总高度（比旋转前）降低了，回溯不能停止。即在平衡二叉树上删除一个结点有可能引起多次旋转。,若

10、x结点为叶子结点，由于删去叶子结点不破坏整棵树的结构，则可直接删去该结点；若x结点只有左子树而无右子树，根据二叉排序树的特点，可以直接将其左子树的根结点放在被删去的结点的位置；若x结点只有右子树而无左子树，同样根据二叉排序树的特点，可以直接将其右子树的根结点放在被删去的结点的位置；若x结点同时有左子树和右子树，则根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或者从其右子树中选择关键字最小的结点放在被删去结点的位置。,平衡二叉树的删除,p,1,h,h,1,0,（a）,（a）pbf=1时在左子树中删除结点,删除后,p-bf变为0.这时,*p结点仍平衡,但*p的高度降低,需要继续向上回溯

11、;,(b),p,0,-1,h,-1,(b)p-bf=0时在左子树中删除结点,删除后,p-bf变成-1,*p仍平衡,且*p高度不变,回溯至此停止;,(c),p,-1,-2,h,-1,h+1,平衡二叉树的删除,例:对下列AVL树,给出删除结点11,9,15的步骤.,删除结点11,待删除的结点同时有左子树和右子树，则根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或者从其右子树中选择关键字最小的结点放在被删去结点的位置。,7,18,3,9,15,26,14,16,11,9,voidDelete1(BSTNode*p,BSTNode*/*找到了最右下的结点,将其关键字赋给待删除结点,并将其左

12、子树的根结点放在被删结点的位置上*/,7,18,15,26,14,16,9,7,-2,1,1,0,0,0,0,p,p1,p2,if(p2-bf=1)p-bf=0;p1-bf=-1;p2-bf=0;p=p2;,需作RL调整,RL调整后,7,18,3,14,16,26,删除结点15,15,14,平衡二叉树,#include#includetypedefintKeyType;/*定义关键字类型*/typedefcharInfoType;typedefstructnode/*记录类型*/KeyTypekey;/*关键字项*/intbf;/*平衡因子*/InfoTypedata;/*其他数据域*/str

13、uctnode*lchild,*rchild;/*左右孩子指针*/BSTNode;,voidLeftProcess(BSTNode*,else/*原本左子树比右子树高,需作左子树的平衡处理*/p1=p-lchild;/*p指向*p的左子树根结点*/if(p1-bf=1)/*新结点插入在*b的左孩子的左子树上,要作LL调整*/p-lchild=p1-rchild;p1-rchild=p;p-bf=p1-bf=0;p=p1;elseif(p1-bf=-1)/*新结点插入在*b的左孩子的右子树上,要作LR调整*/p2=p1-rchild;p1-rchild=p2-lchild;p2-lchild=p

14、1;p-lchild=p2-rchild;p2-rchild=p;if(p2-bf=0)/*新结点插在*p2处作为叶子结点的情况*/p-bf=p1-bf=0;elseif(p2-bf=1)/*新结点插在*p2的左子树上的情况*/p1-bf=0;p-bf=-1;else/*新结点插在*p2的右子树上的情况*/p1-bf=1;p-bf=0;p=p2;p-bf=0;/*仍将p指向新的根结点,并置其bf值为0*/taller=0;,voidRightProcess(BSTNode*,elseif(p1-bf=1)/*新结点插入在*p的右孩子的左子树上,要作RL调整*/p2=p1-lchild;p1-l

15、child=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)/*新结点插在*p2处作为叶子结点的情况*/p-bf=p1-bf=0;elseif(p2-bf=-1)/*新结点插在*p2的右子树上的情况*/p1-bf=0;p-bf=1;else/*新结点插在*p2的左子树上的情况*/p1-bf=-1;p-bf=0;p=p2;p-bf=0;/*仍将p指向新的根结点,并置其bf值为0*/taller=0;,intInsertAVL(BSTNode*,voidDispBSTree(BSTNode*b)/*以括号表示法输出A

16、VL*/if(b!=NULL)printf(%d,b-key);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBSTree(b-lchild);if(b-rchild!=NULL)printf(,);DispBSTree(b-rchild);printf();,voidLeftProcess1(BSTNode*,else/*需作RL调整*/p2=p1-lchild;p1-lchild=p2-rchild;p2-rchild=p1;p-rchild=p2-lchild;p2-lchild=p;if(p2-bf=0)p-bf=0;p1-bf=0;els

17、eif(p2-bf=-1)p-bf=1;p1-bf=0;elsep-bf=0;p1-bf=-1;p2-bf=0;p=p2;taller=1;,voidRightProcess1(BSTNode*,voidDelete2(BSTNode*q,BSTNode*,intDeleteAVL(BSTNode*,voidmain()BSTNode*b=NULL;inti,j,k;KeyTypea=16,3,7,11,9,26,18,14,15,n=9;/*例10.5*/printf(创建一棵AVL树:n);for(i=0;in;i+)printf(第%d步,插入%d元素:,i+1,ai);InsertAVL(b,ai,j);DispBSTree(b);printf(n);printf(AVL:);DispBSTre