平衡二叉树学习.ppt
平衡二叉树平衡二叉树(AVL)(AVL)结点的结点的平衡因子平衡因子（balancd factorbalancd factor用用bfbf表示）表示）:二叉树中某结点左二叉树中某结点左子树的高度与右子树的高度之差称为该结点的平衡因子子树的高度与右子树的高度之差称为该结点的平衡因子.平衡二叉树是另一种形式的二叉查找树。其特点是：平衡二叉树是另一种形式的二叉查找树。其特点是：左右子树深度之差的绝对值不大于左右子树深度之差的绝对值不大于1 1 称有这种特性的二叉树为称有这种特性的二叉树为平衡二叉树平衡二叉树。在算法中，可以通过平衡因子来具体实现平衡二叉树的定义。在算法中，可以通过平衡因子来具体实现平衡二叉树的定义。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子的绝对值小于或等于对值小于或等于1 1，则该树称为平衡二叉树。，则该树称为平衡二叉树。963824882811259801011100-1-201 1、平衡二叉树插入结点的调整方法、平衡二叉树插入结点的调整方法 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，首先从根结点到该新插入结点的路径之逆向根结点方向找第一个失去平首先从根结点到该新插入结点的路径之逆向根结点方向找第一个失去平衡的结点，然后以该失衡结点和它相邻的刚查找过的两个结点构成调整衡的结点，然后以该失衡结点和它相邻的刚查找过的两个结点构成调整子树子树(最小不平衡子树最小不平衡子树)，即调整子树是指以离插入结点最近，即调整子树是指以离插入结点最近,且平衡因子且平衡因子绝对值大于绝对值大于1的结点为根结点的子树的结点为根结点的子树,使之成为新的平衡子树。使之成为新的平衡子树。96382488281125982(1)LL型调整型调整ABfdehh 01h 12调整方法：调整方法：单向右旋平衡，即将单向右旋平衡，即将A的左孩子的左孩子B 向右上旋转代替向右上旋转代替A成为根结点，成为根结点，将将A结点向右下旋转成为结点向右下旋转成为B的右的右子树的根结点，而子树的根结点，而B的原右子树的原右子树则作为则作为A结点的左子树。结点的左子树。BAdeflc=p-lchild;/*lc指向指向B p-lchild=lc-rchild;/*把把B结点的右子树挂接为结点的右子树挂接为A的左子树的左子树lc-rchild=p;/*A结点成为结点成为B的右孩子的右孩子p=lc;/*p指向新的根结点指向新的根结点 pp(2)RR型调整型调整AaBbchh01调整方法：调整方法：单向左旋平衡：即将单向左旋平衡：即将A的右孩子的右孩子B向向左上旋转代替左上旋转代替A成为根结点，将成为根结点，将A结结点向左下旋转成为点向左下旋转成为B的左子树的根的左子树的根结点，而结点，而B的原左子树则作为的原左子树则作为A结点结点的右子树。的右子树。BAcab-1-2lc=p-rchild;/*lc指向指向B*/p-rchild=lc-lchild;/*把把B结点的左子树挂接为结点的左子树挂接为A的右子树的右子树*/lc-lchild=p;/*A结点成为结点成为B的左孩子的左孩子*/p=lc;/*p指向新的根结点指向新的根结点*/pp(3)LR型调整型调整ABCnmie hh1h1001112CBAnmie调整方法：先左旋转后右旋调整方法：先左旋转后右旋转平衡转平衡,即将即将A结点的左孩子结点的左孩子（即（即B结点）的右子树的根结结点）的右子树的根结点（即点（即C结点）向左上旋转提结点）向左上旋转提升到升到B结点的位置，然后再把结点的位置，然后再把该该C结点向右上旋转提升到结点向右上旋转提升到A结点的位置。结点的位置。pbcp-lchild=c-rchild;/*把把C的右子树挂接成的右子树挂接成A的左子树的左子树*/b-rchild=c-lchild;/*把把C的左子树挂接成的左子树挂接成B的右子树的右子树*/c-lchild=b;/*把把B挂接成挂接成C的左子树的左子树*/c-rchild=p;/*把把A挂接成挂接成C的右子树的右子树*/（4）RL型调整型调整ABmCfntCABmntfh1hh1调整方法：先右旋转后左调整方法：先右旋转后左旋转平衡旋转平衡,即先将即先将A结点的结点的右孩子右孩子B结点的左子树的根结点的左子树的根结点结点C结点向右上旋转提升结点向右上旋转提升到到B结点的位置，然后再把结点的位置，然后再把该该C结点向左上旋转提升到结点向左上旋转提升到A结点的位置。结点的位置。001-11-2p-rchild=c-lchild;/*把把C的左子树挂接成的左子树挂接成A的右子树的右子树*/b-lchild=c-rchild;/*把把C的右子树挂接成的右子树挂接成B的左子树的左子树*/c-rchild=b;/*把把B挂接成挂接成C的右子树的右子树*/c-lchild=p;/*把把A挂接成挂接成C的左子树的左子树*/pbc例例1 1 输入关键字序列输入关键字序列16,3,7,11,9,26,18,14,15,16,3,7,11,9,26,18,14,15,给给出构造一棵出构造一棵AVLAVL树的步骤。树的步骤。1603107012属于属于“”型型,应该进行应该进行RL调调整整先右旋转后左旋转平衡先右旋转后左旋转平衡RL调整后调整后1171839162614-1201-1000151属于属于“rchild!=NULL)Delete1(p,r-rchild);/*找左子树最右下的结点找左子树最右下的结点*/else p-key=r-key;q=r;r=r-lchild;free(q);/*找到了最右下的结点找到了最右下的结点,将其关键字赋给待删除结点将其关键字赋给待删除结点,并将其左子树的根结点放在并将其左子树的根结点放在被删结点的位置上被删结点的位置上*/7183152614169 7-2110000pp1p2if(p2-bf=1)p-bf=0;p1-bf=-1;p2-bf=0;p=p2;需作需作RLRL调整调整RLRL调整后调整后7183141626删除结点删除结点15151514
