第四章树与树的表示(三).

4.5平衡二叉树假定二叉搜索树中每个结点的查找概率都是相同的，称查找所有结点的比较次数的平均值为树的“平均查找长度”（ASL)。一、什么是平衡二叉树〖例〗搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASLJanAprAprFebMarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov(a)自然月份序列ASL(a)=(1+2×2+3×3+4×3+5×2+6×1)/12=3.5(b)按July,Feb,May,Mar,Aug,Jan,Apr,Jun,Oct,Sept,Nov,DecASL(b)=3.0(c)月份字符串大小顺序ASL(c)=6.5树深在最好的情况下是O（logN),所以，二叉搜索树在最好情况下的查找复杂度是O（logN)。上述ASL的计算结果表明，一棵树的ASL值越小，它的结构越好，与完全二叉树越接近，其查找时间复查度也越接近O（logN)。因此，为了保证二叉搜索树查找的对数级时间效率，应尽可能创建枝繁叶茂的树，而避免树枝过长、过少。最好的结构是完美二叉树，从根到叶的各条路径都是相同的，称这种树为完全平衡的。二、定义“平衡因子（BalanceFactor，简称BF）:BF(T)=hL-hR，其中hL和hR分别为T的左、右子树的高度。平衡二叉树（BalancedBinaryTree）（AVL树）①空树，或者②任一结点左、右子树高度差的绝对值不超过1，即|BF(T)|≤1因此，平衡二叉树上每个结点的平衡因子只可能是-1、0和1，否则，只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树。三、平衡二叉树的调整一般的二叉排序树是不平衡的，若能通过某种方法使其既保持有序性，又具有平衡性，就找到了构造平衡二叉排序树的方法，该方法称为平衡化旋转。在对AVL树进行插入或删除一个结点后，通常会影响到从根结点到插入(或删除)结点的路径上的某些结点，这些结点的子树可能发生变化。这时就需要做“平衡化”处理，即相应的局部“旋转”调整，使得调整后的树达到平衡。1000MarMayNov2Mar1右单旋MayMay00Mar0NovNov不平衡的“发现者”是Mar，“麻烦结点”Nov在发现者右子树的右边，因而叫RR插入，需要RR旋转（右单旋）AL1A0BRR插入AL2A1BRR旋转0A0BBRBLBRBLBRALBL1.单旋调整cc1010011AugApr22May0LL旋转左单旋12May00AugMarNov0AprAug0MarNov0Apr“发现者”是Mar，“麻烦结点”Apr在发现者左子树的左边，因而叫LL插入，需要LL旋转（左单旋）0B1AARLL插入1B2AARLL旋转BL0B0ABLBRBLBRBRARcc001000110001Jan0Apr1Aug02May1Mar0NovLR左-右双旋0Apr1Aug2Mar0Jan1May0NovJan旋转“发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫LR插入，需要LR旋转LR2LR0B0A插入1BA1旋转0or10C1or0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.双旋调整DDDDD0Apr200110110200011010001DecJulyFeb0Apr1Aug1Dec2Mar0Jan01May0July20NovRL右-左双旋旋转1Dec1Aug0Feb2Mar1Jan1May0July0NovFeb一般情况调整如下:RL2RLA00B插入A11B旋转0or10C1or0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD101Jan110012110DecMarMay110100AprApr0Feb0July0112020010202011Nov00JuneOctSeptAprJune110DecDecMarAugAugFebJanJulyAugFebJuly00011JanMar110001June2MayNov0MayJune1Nov0Oct0Oct0Sept注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子。typedefstructAVLNode*Position;typedefPositionAVLTree;/*AVL树类型*/typedefstructAVLNode{ElementTypeData;/*结点数据*/AVLTreeLeft;/*指向左子树*/AVLTreeRight;/*指向右子树*/intHeight;/*树高*/}四、AVL树的插入intMax(inta,intb){returnab?a:b;}AVLTreeInsert(AVLTreeT,ElementTypeX){/*将X插入AVL树T中，并且返回调整后的AVL树*/if(!T){/*若插入空树，则新建包含一个结点的树*/T=(AVLTree)malloc(sizeof(structAVLNode));T-Data=X;T-Height=0;T-Left=T-Right=NULL;}/*if(插入空树)结束*/elseif(XT-Data){/*插入T的左子树*/T-Left=Insert(T-Left,X);/*如果需要左旋*/if(GetHeight(T-Left)-GetHeight(T-Right)==2)if(XT-Left-Data)T=SingleLeftRotation(T);/*左单旋*/elseT=DoubleLeftRightRotation(T);/*左-右双旋*/}/*elseif(插入左子树)结束*/elseif(XT-Data){/*插入T的右子树*/T-Right=Insert(T-Right,X);/*如果需要右旋*/if(GetHeight(T-Left)-GetHeight(T-Right)==-2)if(XT-Right-Data)T=SingleRightRotation(T);/*右单旋*/elseT=DoubleRightLeftRotation(T);/*右-左双旋*/}/*elseif(插入右子树)结束*//*elseX==T-Data，无须插入*/T-Height=Max(GetHeight(T-Left),GetHeight(T-Right))+1;/*别忘了更新树高*/returnT;}AVLTreeSingleLeftRotation(AVLTreeA)16.{/*注意：A必须有一个左子结点B*/17./*将A与B做左单旋，更新A与B的高度，返回新的根结点B*/18.19.AVLTreeB=A-Left;20.A-Left=B-Right;21.B-Right=A;22.A-Height=Max(GetHeight(A-Left),GetHeight(A-Right))+1;23.B-Height=Max(GetHeight(B-Left),A-Height)+1;24.25.returnB;26.}27.28.AVLTreeDoubleLeftRightRotation(AVLTreeA)29.{/*注意：A必须有一个左子结点B，且B必须有一个右子结点C*/30./*将A、B与C做两次单旋，返回新的根结点C*/31.32./*将B与C做右单旋，C被返回*/33.A-Left=SingleRightRotation(A-Left);34./*将A与C做左单旋，C被返回*/35.returnSingleLeftRotation(A);36.}37.38./*************************************/39./*对称的右单旋与右-左双旋请自己实现*/40./*************************************/41.AVLTreeSingleLeftRotation(AVLTreeA){/*注意：A必须有一个左子结点B*//*将A与B做左单旋，更新A与B的高度，返回新的根结点B*/AVLTreeB=A-Left;A-Left=B-Right;B-Right=A;A-Height=Max(GetHeight(A-Left),GetHeight(A-Right))+1;B-Height=Max(GetHeight(B-Left),A-Height)+1;returnB;}AVLTreeDoubleLeftRightRotation(AVLTreeA){/*注意：A必须有一个左子结点B，且B必须有一个右子结点C*//*将A、B与C做两次单旋，返回新的根结点C*/A-Left=SingleRightRotation(A-Left);/*将B与C做右单旋，C被返回*/returnSingleLeftRotation(A);/*将A与C做左单旋，C被返回*/}作业：1、在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？..A.1B.2C.3D.62、在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？..A.1B.5C.6D.11测验：1.设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。2.已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。图6-27二叉树adebfgchkmn3、一棵度为m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1)(假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（FirstChild/NextSibling）表示法时，所需的总空间是：..A.3nB.2nC.n*mD.n*(m-1)4、如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？..A.31B.39C.63D.715、若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？..A.25B.50C.不确定D.这样的树不存在6、设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1..A.√B.×7、假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？..A.ABCDB.ACDBC.DCBAD.DABC8、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树________..A.是完全二叉树B.所有结点都没有左儿子C.所有结点都没有右儿子D.这样的树不存在9、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA和FDBEACG,那么该二叉树的前序遍历结果是什么？..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG10、假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？..A.ABCDB.ACDBC.DCBAD.DABC11、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树________..A.是完全二叉树B.所有结点都没有左儿子C.所有结点都没有右儿子D.这样的树不存在12、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA和FDBEACG,那么该二叉树的前序遍历结果是什么？..A.ABDFE