平衡二叉树学习.ppt

,平衡二叉树(AVL),结点的平衡因子（balancd factor用bf表示） :二叉树中某结点左子树的高度与右子树的高度之差称为该结点的平衡因子. 平衡二叉树是另一种形式的二叉查找树。其特点是： 左右子树深度之差的绝对值不大于1 称有这种特性的二叉树为平衡二叉树。 在算法中，可以通过平衡因子来具体实现平衡二叉树的定义。 从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于1，则该树称为平衡二叉树。,96,38,24,88,28,11,25,98,0,1,0,1,1,1,0,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的原右子树则作为A结点的左子树。,B,A,d,e,f,lc=p-lchild; /*lc指向B p-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的右子树*/ 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=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,例1 输入关键字序列16,3,7,11,9,26,18,14,15,给出构造一棵AVL树的步骤。,16,0,3,1,0,7,0,1,2,属于“型,应该进行LR调整 先左旋转后右旋转平衡,LR调整后,7,3,16,0,0,0,11,0,1,-1,9,0,1,2,-2,属于”/”型,应该进行LL调整 单向右旋转,LL调整后,7,3,11,9,16,26,0,-1,0,-1,0,-2,属于”型,应该进行RR调整 单向左旋平衡,RR调整后,11,7,16,3,9,26,18,0,1,-2,-1,0,0,0,属于”型,应该进行RL调整 先右旋转后左旋转平衡,RL调整后,11,7,18,3,9,16,26,14,-1,2,0,1,-1,0,0,0,15,1,属于“型,应该进行LR调整 先左旋转后右旋转平衡,LR调整后,11,7,18,3,9,15,26,14,16,从上述例题可以看出,每插入一个结点至多调整一次,全树都能达到平衡.,平衡二叉树的删除,例:对下列AVL树,给出删除结点11,9,15的步骤.,删除结点11,待删除的结点同时有左子树和右子树，则根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或者从其右子树中选择关键字最小的结点放在被删去结点的位置。,7,18,3,9,15,26,14,16,11,9,void Delete1(BSTNode *p,BSTNode * /* 找到了最右下的结点,将其关键字赋给待删除结点,并将其左子树的根结点放在被删结点的位置上*/ ,7,18,15,26,14,16,9,7,-