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

4.5平衡二叉樹(shù)假定二叉搜索樹(shù)中每個(gè)結(jié)點(diǎn)的查找概率都是相同的，稱查找所有結(jié)點(diǎn)的比較次數(shù)的平均值為樹(shù)的“平均查找長(zhǎng)度”（ASL)。一、什么是平衡二叉樹(shù)〖例〗搜索樹(shù)結(jié)點(diǎn)不同插入次序，將導(dǎo)致不同的深度和平均查找長(zhǎng)度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

樹(shù)深在最好的情況下是O（logN),所以，二叉搜索樹(shù)在最好情況下的查找復(fù)雜度是O（logN)。上述ASL的計(jì)算結(jié)果表明，一棵樹(shù)的ASL值越小，它的結(jié)構(gòu)越好，與完全二叉樹(shù)越接近，其查找時(shí)間復(fù)查度也越接近O（logN)。因此，為了保證二叉搜索樹(shù)查找的對(duì)數(shù)級(jí)時(shí)間效率，應(yīng)盡可能創(chuàng)建枝繁葉茂的樹(shù)，而避免樹(shù)枝過(guò)長(zhǎng)、過(guò)少。最好的結(jié)構(gòu)是完美二叉樹(shù)，從根到葉的各條路徑都是相同的，稱這種樹(shù)為完全平衡的。

二、定義

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

平衡二叉樹(shù)（BalancedBinaryTree）（AVL樹(shù)）

①空樹(shù)，或者

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

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

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

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

2Mar1右單旋

MayMay0

0Mar

0Nov

Nov

不平衡的“發(fā)現(xiàn)者”是Mar，“麻煩結(jié)點(diǎn)”Nov在發(fā)現(xiàn)者右子樹(shù)的右邊， 因而叫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)者左子樹(shù)的左邊，因而叫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在左子樹(shù)的右邊，因而叫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

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

/*AVL樹(shù)類型*/typedefstructAVLNode{

ElementTypeData;

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

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

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

T->Height=0;

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

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