第四章樹與樹的表示(三)

4.5平衡二叉樹假定二叉搜索樹中每個結(jié)點(diǎn)的查找概率都是相同的，稱查找所有結(jié)點(diǎn)的比較次數(shù)的平均值為樹的“平均查找長度”（ASL)。一、什么是平衡二叉樹〖例〗搜索樹結(jié)點(diǎn)不同插入次序，將導(dǎo)致不同的深度和平均查找長度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),所以，二叉搜索樹在最好情況下的查找復(fù)雜度是O（logN)。上述ASL的計(jì)算結(jié)果表明，一棵樹的ASL值越小，它的結(jié)構(gòu)越好，與完全二叉樹越接近，其查找時間復(fù)查度也越接近O（logN)。因此，為了保證二叉搜索樹查找的對數(shù)級時間效率，應(yīng)盡可能創(chuàng)建枝繁葉茂的樹，而避免樹枝過長、過少。最好的結(jié)構(gòu)是完美二叉樹，從根到葉的各條路徑都是相同的，稱這種樹為完全平衡的。

二、定義

“平衡因子（BalanceFactor，簡稱BF）:BF(T)=hL-hR， 其中hL和hR分別為T的左、右子樹的高度。

平衡二叉樹（BalancedBinaryTree）（AVL樹）

①空樹，或者

②任一結(jié)點(diǎn)左、右子樹高度差的絕對值不超過1，即|BF(T)|≤1

因此，平衡二叉樹上每個結(jié)點(diǎn)的平衡因子只可能是-1、0和1，否則，只要有一個結(jié)點(diǎn)的平衡因子的絕對值大于1，該二叉樹就不是平衡二叉樹。三、平衡二叉樹的調(diào)整

一般的二叉排序樹是不平衡的，若能通過某種方法使其既保持有序性，又具有平衡性，就找到了構(gòu)造平衡二叉排序樹的方法，該方法稱為平衡化旋轉(zhuǎn)。

在對AVL樹進(jìn)行插入或刪除一個結(jié)點(diǎn)后，通常會影響到從根結(jié)點(diǎn)到插入(或刪除)結(jié)點(diǎn)的路徑上的某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的子樹可能發(fā)生變化。這時就需要做“平衡化”處理，即相應(yīng)的局部“旋轉(zhuǎn)”調(diào)整，使得調(diào)整后的樹達(dá)到平衡。1000MarMayNov

2Mar1右單旋

MayMay0

0Mar

0Nov

Nov

不平衡的“發(fā)現(xiàn)者”是Mar，“麻煩結(jié)點(diǎn)”Nov在發(fā)現(xiàn)者右子樹的右邊， 因而叫RR插入，需要RR旋轉(zhuǎn)（右單旋）AL1

A0BRR插入AL2

A1

BRR旋轉(zhuǎn)0A0BBRBLBRBLBRALBL1.單旋調(diào)整cc1010011AugApr2

2May0

LL旋轉(zhuǎn)左單旋1

2May0

0AugMarNov

0AprAug

0MarNov

0

Apr“發(fā)現(xiàn)者”是Mar，“麻煩結(jié)點(diǎn)”Apr在發(fā)現(xiàn)者左子樹的左邊，因而叫LL插入，需要LL旋轉(zhuǎn)（左單旋）0B1AAR

LL插入1B2AAR

LL旋轉(zhuǎn)BL0B0ABLBRBLBRBRARcc001000110001Jan

0

Apr

1Aug

0

2May

1Mar

0Nov

LR左-右雙旋

0

Apr

1Aug

2Mar

0Jan

1May

0NovJan旋轉(zhuǎn)“發(fā)現(xiàn)者”是May，“麻煩結(jié)點(diǎn)”Jan在左子樹的右邊，因而叫LR插入，需要LR旋轉(zhuǎn)

LR2LR0B0A插入1

B

A1旋轉(zhuǎn)0or1

0C1or0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.雙旋調(diào)整DDDDD0Apr200110110200011010001DecJulyFeb

0Apr

1Aug

1Dec

2

Mar

0

Jan0

1May

0July

2

0NovRL

右-左雙旋旋轉(zhuǎn)1

Dec

1

Aug

0

Feb

2Mar

1Jan

1May

0July

0Nov

Feb一般情況調(diào)整如下:

RL2RLA00B插入A

11B旋轉(zhuǎn)0or1

0C1or0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD101Jan110012110DecMarMay110100AprApr0Feb0July0112020010202011Nov00JuneOctSeptAprJune

110

DecDecMar AugAugFebJanJuly AugFebJuly000

11

JanMar110001June

2May Nov

0May June

1Nov0

Oct

0

Oct0

Sept

注意：有時候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計(jì)算 一些平衡因子。typedefstructAVLNode*Position;typedefPositionAVLTree;

/*AVL樹類型*/typedefstructAVLNode{

ElementTypeData;

/*結(jié)點(diǎn)數(shù)據(jù)*/AVLTreeLeft;/*指向左子樹*/AVLTreeRight;/*指向右子樹*/intHeight;/*樹高*/}四、AVL樹的插入intMax(inta,intb){returna>b?a:b;}AVLTreeInsert(AVLTreeT,ElementTypeX){/*將X插入AVL樹T中，并且返回調(diào)整后的AVL樹*/if(!T)

{/*若插入空樹，則新建包含一個結(jié)點(diǎn)的樹*/

T=(AVLTree)malloc(sizeof(structAVLNode));T->Data=X;

T->Height=0;

T->Left=T->Right=NULL;}/*if(插入空樹)結(jié)束*/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(插入左子樹)結(jié)束*/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(插入右子樹)結(jié)束*//*elseX==T->Data，無須插入*/T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1;

/*別忘了更新樹高*/returnT;}AVLTreeSingleLeftRotation(AVLTreeA)16.{/*注意：A必須有一個左子結(jié)點(diǎn)B*/17./*將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點(diǎn)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必須有一個左子結(jié)點(diǎn)B，且B必須有一個右子結(jié)點(diǎn)C*/30./*將A、B與C做兩次單旋，返回新的根結(jié)點(diǎn)C*/31.32./*將B與C做右單旋，C被返回*/33.A->Left=SingleRightRotation(A->Left);34./*將A與C做左單旋，C被返回*/35.returnSingleLeftRotation(A);36.}37.38./*************************************/39./*對稱的右單旋與右-左雙旋請自己實(shí)現(xiàn)*/40./*************************************/41.AVLTreeSingleLeftRotation(AVLTreeA){/*注意：A必須有一個左子結(jié)點(diǎn)B*//*將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點(diǎn)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必須有一個左子結(jié)點(diǎn)B，且B必須有一個右子結(jié)點(diǎn)C*//*將A、B與C做兩次單旋，返回新的根結(jié)點(diǎn)C*/A->Left=SingleRightRotation(A->Left);/*將B與C做右單旋，C被返回*/returnSingleLeftRotation(A);/*將A與C做左單旋，C被返回*/}

作業(yè)：1、在分量1~11的數(shù)組中按從小到大順序存放11個元素，如果用順序查找和二分查找分別查找這11個元素，哪個位置的元素在這兩種方法的查找中總次數(shù)最少？..A.1B.2C.3D.62、在分量1~11的數(shù)組中按從小到大順序存放11個元素，如果進(jìn)行二分查找，查找次數(shù)最少的元素位于什么位置？..A.1B.5C.6D.11測驗(yàn)：1.設(shè)有如圖6-27所示的二叉樹。①分別用順序存儲方法和鏈接存儲方法畫出該二叉樹的存儲結(jié)構(gòu)。②寫出該二叉樹的先序、中序、后序遍歷序列。2.已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GDHBAECIF，請畫出這棵二叉樹，然后給出該樹的后序遍歷序列。圖6-27二叉樹adebfgchkmn3、一棵度為m的樹有n個節(jié)點(diǎn)。若每個節(jié)點(diǎn)直接用m個鏈指向相應(yīng)的兒子，則表示這個樹所需要的總空間是n*(m+1)(假定每個鏈以及表示節(jié)點(diǎn)的數(shù)據(jù)域都是一個單位空間).。當(dāng)采用兒子/兄弟（FirstChild/NextSibling）表示法時，所需的總空間是：..A.3nB.2nC.n*mD.n*(m-1)4、如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結(jié)點(diǎn)，那么該完全二叉樹共有多少個結(jié)點(diǎn)？..A.31B.39C.63D.715、若有一二叉樹的總結(jié)點(diǎn)數(shù)為98，只有一個兒子的結(jié)點(diǎn)數(shù)為48，則該樹的葉結(jié)點(diǎn)數(shù)是多少？..A.25B.50C.不確定D.這樣的樹不存在6、設(shè)深度為d（只有一個根結(jié)點(diǎn)時，d為1）的二叉樹只有度為0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)數(shù)至少為2d-1..A.√B.×7、假定只有四個結(jié)點(diǎn)A、B、C、D的二叉樹，其前序遍歷序列為ABCD，則下面哪個序列是不可能的中序遍歷序列？..A.ABCDB.ACDBC.DCBAD.DABC8、對于二叉樹，如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣，那么可以斷定該二叉樹________..A.是完全二叉樹B.所有結(jié)點(diǎn)都沒有左兒子C.所有結(jié)點(diǎn)都沒有右兒子D.這樣的樹不存在9、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么？..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG10、假定只有四個結(jié)點(diǎn)A、B、C、D的二叉樹，其前序遍歷序列為ABCD，則下面哪個序列是不可能的中序遍歷序列？..A.ABCDB.ACDBC.DCBAD.DABC11、對于二叉樹，如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣，那么可以斷定該二叉樹________..A.是完全二叉樹B.所有結(jié)點(diǎn)都沒有左兒子C.所有結(jié)點(diǎn)都沒有右兒子D.這樣的樹不存在12、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么？..A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG13、非遞歸方法中序遍歷下面這顆二叉樹，其堆棧操作序列（P代表為push,O代表為pop)是什么？..A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知