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、已知