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

1、4.5平衡二叉树平衡二叉树 假定二叉搜索树中每个结点的查找概率都是相同的，称查找所有结点的比较次数的平均值为树的“平均查找长度”（ASL)。一、什么是平衡二叉树例搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASLJanAprAprFebMarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov(a) 自然月份序列ASL(a)=(1+22+33+43+52+61)/12 = 3.5(b) 按July, Feb, May, Mar,Aug, Jan, Apr, Jun, Oct, Sept

2、,Nov, DecASL(b)=3.0(c)月份字符串月份字符串大小顺序ASL(c)= 6.5 树深在最好的情况下是O（logN),所以，二叉搜索树在最好情况下的查找复杂度是O（logN)。 上述ASL的计算结果表明，一棵树的ASL值越小，它的结构越好，与完全二叉树越接近，其查找时间复查度也越接近O（logN)。因此，为了保证二叉搜索树查找的对数级时间效率，应尽可能创建枝繁叶茂的树，而避免树枝过长、过少。 最好的结构是完美二叉树，从根到叶的各条路径都是相同的，称这种树为完全平衡的。 二、定义“平衡因子（Balance Factor，简称BF）: BF(T) = hL-hR，其中hL和hR分别为

3、T的左、右子树的高度。 平衡二叉树（Balanced Binary Tree）（AVL树）空树，或者任一结点左、右子树高度差的绝对值不超过1，即|BF(T) | 1 因此，平衡二叉树上每个结点的平衡因子只可能是-1、0和1，否则，只要有一个结点的平衡因子的绝对值大于1， 该二叉树就不是平衡二叉树。三、平衡二叉树的调整 一般的二叉排序树是不平衡的，若能通过某种方法使其既保持有序性，又具有平衡性，就找到了构造平衡二叉排序树的方法，该方法称为平衡化旋转。 在对AVL树进行插入或删除一个结点后，通常会影响到从根结点到插入(或删除)结点的路径上的某些结点，这些结点的子树可能发生变化。这时就需要做“平衡化

4、”处理，即相应的局部“旋转”调整，使得调整后的树达到平衡。1000MarMayNov2Mar1右单旋 MayMay00Mar0NovNov 不平衡的“发现者”是Mar，“麻烦结点”Nov 在发现者右子树的右边，因而叫 RR 插入，需要RR 旋转（右单旋）AL1A0BRR插入AL2A1BRR旋转0A0BBRBLBRBLBRALBL1.单旋调整cc1010011AugApr22May0LL旋转左单旋12May00AugMarNov0AprAug0MarNov0Apr“发现者”是Mar，“麻烦结点”Apr 在发现者左子树的左边，因而叫 LL 插入，需要LL 旋转（左单旋）0B1AARLL插入1B2A

5、ARLL旋转BL0B0ABLBRBLBRBRARcc001000110001Jan0Apr1Aug02May1Mar0NovLR左-右双旋0Apr1Aug2Mar0Jan1May0NovJan旋转“发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫 LR 插入，需要LR 旋转LR2LR0B0A插入1BA1旋转0 or 10C1 or 0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.双旋调整DDDDD0Apr200110110200011010001DecJulyFeb0Apr1Aug1Dec2Mar0Jan01May0July20NovRL右-左双旋旋转 1Dec

6、1Aug0Feb2Mar1Jan1May0July0NovFeb一般情况调整如下:RL2RLA00B插入A11B旋转0 or 10C1 or 0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD1 01Jan1 10 01 2110Dec MarMay110100AprApr0 Feb 0 July0112 020 010 2020 11Nov00JuneOctSeptApr June1 1 0Dec Dec MarAugAug Feb JanJulyAug Feb July0 0 011JanMar1 1 0 00 1June2MayNov0MayJune1Nov 0

7、Oct0Oct 0Sept注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子。typedef struct AVLNode *Position;typedef Position AVLTree; /* AVL树类型 */typedef struct AVLNode ElementType Data; /* 结点数据 */ AVLTree Left; /* 指向左子树 */ AVLTree Right; /* 指向右子树 */ int Height; /* 树高 */四、AVL树的插入int Max ( int a, int b ) return a b ? a : b;AV

8、LTree Insert( AVLTree T, ElementType X ) /* 将X插入AVL树T中，并且返回调整后的AVL树 */if ( !T ) /* 若插入空树，则新建包含一个结点的树 */ T = (AVLTree)malloc(sizeof(struct AVLNode); T-Data = X; T-Height = 0; T-Left = T-Right = NULL; /* if (插入空树) 结束 */ else if ( X Data ) /* 插入T的左子树 */ T-Left = Insert( T-Left, X); /* 如果需要左旋 */ if ( Ge

9、tHeight(T-Left)-GetHeight(T-Right) = 2 ) if ( X Left-Data ) T = SingleLeftRotation(T); /* 左单旋 */ else T = DoubleLeftRightRotation(T); /* 左-右双旋 */ /* else if (插入左子树) 结束 */ else if ( X T-Data ) /* 插入T的右子树 */ T-Right = Insert( T-Right, X ); /* 如果需要右旋 */ if ( GetHeight(T-Left)-GetHeight(T-Right) = -2 )

10、if ( X T-Right-Data ) T = SingleRightRotation(T); /* 右单旋 */ else T = DoubleRightLeftRotation(T); /* 右-左双旋 */ /* else if (插入右子树) 结束 */ /* else X = T-Data，无须插入 */T-Height = Max( GetHeight(T-Left), GetHeight(T-Right) ) + 1; /* 别忘了更新树高 */return T;AVLTree SingleLeftRotation ( AVLTree A )16. /* 注意：A必须有一个左

11、子结点B */17. /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */ 18. 19. AVLTree B = 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. return B;26.27. 28.AVLTree DoubleLeftRightRotation ( AVLTree A )29

12、. /* 注意：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. return SingleLeftRotation(A);36.37. 38./*/39./* 对称的右单旋与右-左双旋请自己实现 */40./*/41. AVLTree SingleLeftRotation ( AVLTree A ) /* 注意：A必须有一个左子结点B */

13、/* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */ AVLTree B = 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; return B; AVLTree DoubleLeftRightRotation ( AVLTree A ) /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */ /* 将A、B与C做两次单旋

14、，返回新的根结点C */A-Left = SingleRightRotation(A-Left); /* 将B与C做右单旋，C被返回 */ return SingleLeftRotation(A);/* 将A与C做左单旋，C被返回 */ 作业：1、在分量111的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？.A.1 B.2 C.3 D.62、在分量111的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？.A.1 B.5 C.6 D.11测验：1.1.设有如图设有如图6-27所

15、示的二叉树。所示的二叉树。 分别用顺序存储方法和链接存储方法画出该二叉树的存分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。储结构。 写出该二叉树的先序、中序、后序遍历序列。写出该二叉树的先序、中序、后序遍历序列。2.2.已知一棵二叉树的先序遍历序列和中序遍历序列分别为已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和和GDHBAECIF，请画出这棵二叉树，然后给出该，请画出这棵二叉树，然后给出该树的后序遍历序列。树的后序遍历序列。图图6-27 二叉树二叉树adebfgchkmn3、一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的

16、总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是：.A.3n B.2n C.n*m D.n*(m-1)4、如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？.A.31 B.39 C.63 D.715、若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？.A.25 B.50 C.不确定 D.这样的树不存在6、设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点

17、数至少为2d-1.A. B.7、假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？.A. ABCD B. ACDB C. DCBA D. DABC8、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树_.A.是完全二叉树 B.所有结点都没有左儿子C.所有结点都没有右儿子 D.这样的树不存在9、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D. ABCDEFG10、假定只有四个结点A、B、C、D

18、的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？.A. ABCD B. ACDB C. DCBA D. DABC11、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树_.A.是完全二叉树 B.所有结点都没有左儿子C.所有结点都没有右儿子 D.这样的树不存在12、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D.ABCDEFG13、非递归方法中序遍历下面这颗二叉树，其堆栈操作序列（P代表为push,O代表为pop)是什么？.A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知有颗5个结点的二叉树，其前序遍历序列是a?，中序遍历序列是a?，可以断定：.A.该树根结点是a，且没有左子树 B.该树根结点是a，且没有右子树C.该树最左边的结点