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

4.5平衡二叉树假定二叉搜索树中每个结点的查找概率都是相同的，称查找所有结点的比较次数的平均值为树的“平均查找长度”（ASL)。一、什么是平衡二叉树〖例〗搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL

Jan AprAprFeb

MarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov

(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,Dec

ASL(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树进行插入或删除一个结点后，通常会影响到从根结点到插入(或删除)结点的路径上的某些结点，这些结点的子树可能发生变化。这时就需要做“平衡化”处理，即相应的局部“旋转”调整，使得调整后的树达到平衡。1000MarMayNov

2Mar1右单旋

MayMay0

0Mar

0Nov

Nov

不平衡的“发现者”是Mar，“麻烦结点”Nov在发现者右子树的右边， 因而叫RR插入，需要RR旋转（右单旋）AL1

A0BRR插入AL2

A1

BRR旋转0A0BBRBLBRBLBRALBL1.单旋调整cc1010011AugApr2

2May0

LL旋转左单旋1

2May0

0AugMarNov

0AprAug

0MarNov

0

Apr“发现者”是Mar，“麻烦结点”Apr在发现者左子树的左边，因而叫LL插入，需要LL旋转（左单旋）0B1AAR

LL插入1B2AAR

LL旋转BL0B0ABLBRBLBRBRARcc001000110001Jan

0

Apr

1Aug

0

2May

1Mar

0Nov

LR左-右双旋

0

Apr

1Aug

2Mar

0Jan

1May

0NovJan旋转“发现者”是May，“麻烦结点”Jan在左子树的右边，因而叫LR插入，需要LR旋转

LR2LR0B0A插入1

B

A1旋转0or1

0C1or0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.双旋调整DDDDD0Apr200110110200011010001DecJulyFeb

0Apr

1Aug

1Dec

2

Mar

0

Jan0

1May

0July

2

0NovRL

右-左双旋旋转1

Dec

1

Aug

0

Feb

2Mar

1Jan

1May

0July

0Nov

Feb一般情况调整如下:

RL2RLA00B插入A

11B旋转0or1

0C1or0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD101Jan110012110DecMarMay110100AprApr0Feb0July0112020010202011Nov00JuneOctSeptAprJune

110

DecDecMar AugAugFebJanJuly AugFebJuly000

11

JanMar110001June

2May Nov

0May June

1Nov0

Oct

0

Oct0

Sept

注意：有时候插入元素即便不需要调整结构，也可能需要重新计算 一些平衡因子。typedefstructAVLNode*Position;typedefPositionAVLTree;

/*AVL树类型*/typedefstructAVLNode{

ElementTypeData;

/*结点数据*/AVLTreeLeft;/*指向左子树*/AVLTreeRight;/*指向右子树*/intHeight;/*树高*/}四、AVL树的插入intMax(inta,intb){returna>b?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(X<T->Data){/*插入T的左子树*/T->Left=Insert(T->Left,X);

/*如果需要左旋*/

if(GetHeight(T->Left)-GetHeight(T->Right)==2)

if(X<T->Left->Data)

T=SingleLeftRotation(T);/*左单旋*/

else

T=DoubleLeftRightRotation(T);/*左-右双旋*/}/*elseif(插入左子树)结束*/elseif(X>T->Data){/*插入T的右子树*/T->Right=Insert(T->Right,X);/*如果需要右旋*/if(GetHeight(T->Left)-GetHeight(T->Right)==-2)

if(X>T->Right->Data)T=SingleRightRotation(T);/*右单旋*/

else

T=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.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG13、非递归方法中序遍历下面这颗二叉树，其堆栈操作序列（P代表为push,O代表为pop)是什么？..A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知