湘潭大學(xué) 數(shù)據(jù)結(jié)構(gòu) Ch04 Trees

第四章樹編輯ppt§1預(yù)備知識客觀世界中許多事物存在層次關(guān)系人類社會家譜社會組織結(jié)構(gòu)圖書信息管理編輯ppt哲學(xué)宗教文學(xué)醫(yī)藥衛(wèi)生農(nóng)業(yè)科學(xué)工業(yè)技術(shù)哲學(xué)理論世界哲學(xué)歐洲哲學(xué)宗教宗教分析研究宗教理論與概況佛教宗教與社會政治宗教與科學(xué)破除迷信綜合電工技術(shù)計算機(jī)建筑科學(xué)水利工程………一般性技術(shù)計算機(jī)軟件電子模擬計算機(jī)微型計算機(jī)計算機(jī)的應(yīng)用圖書……軟件工程程序語言編譯程序操作系統(tǒng)………編輯ppt§1預(yù)備知識【定義】樹是一些節(jié)點的集合。這個集合可以是空集；若非空，則樹包含：(1)一個被稱為根的特殊節(jié)點

r;(2)以及0個或多個非空（子）樹

T1,,Tk，每一棵子樹的根都被來自根r的一條有向邊（edge）所連接。Note:子樹是不相交的。因此樹中的每一個節(jié)點都是一棵子樹的根。一棵有N個節(jié)點的樹中有條邊。根節(jié)點通常畫在上方。N

1編輯pptACBDGFEHIJMLK節(jié)點的度（Degree）::=節(jié)點的子樹個數(shù)。

例如,degree(A)=3,degree(F)=0.樹的度::=

例如,degreeofthistree=3.葉節(jié)點（leaf）:=度為0的節(jié)點(沒有孩子)。父節(jié)點（Parent）::=有子樹的節(jié)點是其子樹根節(jié)點的父節(jié)點。子節(jié)點（Child）::=若A節(jié)點是B節(jié)點的父節(jié)點，則B節(jié)點是A節(jié)點的子節(jié)點，也叫孩子節(jié)點。兄弟節(jié)點（sibling）

::=具有同一父節(jié)點的各節(jié)點彼此是兄弟節(jié)點?！?預(yù)備知識1.術(shù)語編輯ppt§1預(yù)備知識ACBDGFEHIJMLK祖先結(jié)點(Ancestor)::=沿樹根到某一結(jié)點路徑上的所有結(jié)點都是這個結(jié)點的祖先結(jié)點。子孫結(jié)點(Descendant)::=某一結(jié)點的子樹中的所有結(jié)點是這個結(jié)點的子孫。ni的深度::=從根到ni唯一的路徑的長度。

Depth(root)=0.ni的高度::=從ni

到一片葉子的最長路徑的長度。Height(leaf)=0,height(D)=2.樹的高度（深度）::=height(root)=depth(deepestleaf).從n1

到

nk的路徑::=從結(jié)點n1到nk的路徑被定義為一個結(jié)點序列n1,n2,…,nk

，對于1ik,ni是ni+1的父結(jié)點。路徑長度::=一條路徑的長度為這條路徑所包含的邊（分支）的個數(shù)。編輯ppt2.樹的實現(xiàn)

鏈表表示法ACBDGFEHIJMLKABCDEFGHIJKLM因此，每個節(jié)點的大小取決于子樹數(shù)目。噢，這樣并不太好！§1預(yù)備知識編輯ppt

兒子-兄弟表示法FirstChildNextSiblingElementACBDGFEHIJMLKNACBNDENKNNFNNGHNINNJNNLNNMNote:這種表示法并非唯一的，因為樹的節(jié)點的孩子順序是不固定的?！?預(yù)備知識編輯ppt

樹的遍歷——訪問每個節(jié)點恰好一次

前序遍歷voidpreorder(tree_ptrtree){if(tree){visit(tree);

for(eachchildCoftree)preorder(C);}}編輯ppt〖例1〗列出分級文件系統(tǒng)中的目錄。輸出格式:

深度為di

的文件的名字將被di次跳格(tab)縮進(jìn)后打印出來。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectory編輯ppt/usrmarkbook Ch1.c Ch2.c Ch3.ccourse cop3530 fall96 syl.r spr97 syl.r sum97 syl.rhw.calexhw.cbillworkcourse cop3212 fall96 grades p1.r p2.r fall97 p2.r p1.r gradesstaticvoidListDir(DirOrFileD,intDepth){

if(Disalegitimateentry){PrintName(D,Depth);

if(Disadirectory)

for(eachchildCofD)ListDir(C,Depth+1);}}Note:

深度(Depth)是一個內(nèi)部簿記變量，而不是主調(diào)例程能夠期望知道的那種參數(shù)，因此，驅(qū)動例程ListDirectory用于將遞歸例程和外界連接起來。voidListDirectory(DirOrFileD){ ListDir(D,0);}T(N)=O(N)編輯ppt

后序遍歷voidpostorder(tree_ptrtree){if(tree){for(eachchildCoftree)postorder(C);visit(tree);}}編輯ppt〖例2〗計算一個目錄的大小。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectorywithfilesizes11111111111111132468152341279staticintSizeDir(DirOrFileD){

intTotalSize;TotalSize=0;if(Disalegitimateentry){TotalSize=FileSize(D);if(Disadirectory)

for(eachchildCofD)TotalSize+=SizeDir(C);}/*endifDislegal*/

returnTotalSize;}T(N)=O(N)編輯ppt

層序遍歷voidlevelorder(tree_ptrtree){enqueue(tree);while(queueisnotempty){visit(T=dequeue());

for(eachchildCofT)enqueue(C);}}245367111232453674567編輯ppt§2二叉樹【定義】一棵二叉樹T是一個有窮的結(jié)點集合。這個集合可以為空，若不為空，則它是由根結(jié)點和稱為其左子樹TL和右子樹TR的兩個不相交的二叉樹組成?？梢娮笞訕浜陀易訕溥€是二叉樹。二叉樹具體五種基本形態(tài)（1）空二叉樹；（2）只有根結(jié)點的二叉樹；（3）只有根結(jié)點和左子樹TL的二叉樹；（4）只有根結(jié)點和右子樹TR的二叉樹；（5）具有根結(jié)點、左子樹TL和右子樹TR的二叉樹。ФTLTRTLTR(a)(b)(c)(d)(e)遞歸的定義形式二叉樹與樹不同，除了每個結(jié)點至多有兩棵子樹外，子樹有左右順序之分。例如，下面兩個樹按一般樹的定義它們是同一個樹；而對于二叉樹來講，它們是不同的兩個樹。編輯ppt特殊二叉樹二叉樹的深度小于結(jié)點數(shù)N，可以證明平均深度是

“完美二叉樹(PerfectBinaryTree)”。（也稱為滿二叉樹）。BACBCDEHIJFG一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為“完全二叉樹(CompleteBinaryTree)”。1211KL151413MNO

“斜二叉樹(SkewedBinaryTree)”（也稱為退化二叉樹）BCDEHKJFG§2二叉樹16編輯ppt二叉樹的幾個重要的性質(zhì)一個二叉樹第i層的最大結(jié)點數(shù)為：2

i-1，i

1。對任何非空的二叉樹

T，若n0表示葉結(jié)點的個數(shù)、n2是度為2的非葉結(jié)點個數(shù)，那么兩者滿足關(guān)系n0=n2+1。深度為k的二叉樹有最大結(jié)點總數(shù)為：2

k-1，k

1。ABCDEKJFHn0=4，n1=2n2=3n0=n2+1證明:

設(shè)

n1

是度為1結(jié)點數(shù),n

是總的結(jié)點數(shù).那么

n=設(shè)

B

是全部分枝數(shù).則

n~B?n=B+1.因為所有分枝都來自度為1或2的結(jié)點,所以B~n1

&n2

?B=n1

+

2n2.

123n0=n2+1

n個結(jié)點的完全二叉樹的深度為k為

：§2二叉樹17編輯ppt二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)完全二叉樹最適合這種存儲結(jié)構(gòu)。n個結(jié)點的完全二叉樹的結(jié)點父子關(guān)系，簡單地由序列號決定：(b)完全二叉樹(a)相應(yīng)的順序存儲結(jié)構(gòu)1、非根結(jié)點（序號i>1）的父結(jié)點的序號是i/2;2、結(jié)點（序號為i）的左孩子結(jié)點的序號是2i，

（若2

i<=n，否則沒有左孩子）;3、結(jié)點（序號為i）的右孩子結(jié)點的序號是2i+1，

（若2

i+1<=n，否則沒有右孩子）。數(shù)據(jù)ABOCSMQWK編號123456789§2二叉樹18編輯pptABOMC137654982ABOM13111012C數(shù)據(jù)ABO∧∧M∧∧∧∧∧∧C編號12345678910111213

(a)一般二叉樹(b)對應(yīng)(a)的完全二叉樹造成空間嚴(yán)重浪費！一般二叉樹采用這種結(jié)構(gòu)將造成空間浪費§2二叉樹19編輯ppt2.二叉樹的鏈表存儲typedef

structTreeNode*BinTree;typedefBinTreePosition;structTreeNode{ ElementTypeData; BinTreeLeft; BinTreeRight;}；LeftDataRightdataLeftRightHEDFGIACBFCBDGIHEA§2二叉樹20編輯ppt§2二叉樹

表達(dá)式樹(語法樹)〖例1〗一棵表達(dá)式樹：

A+BCD+ADBC樹葉是操作數(shù)，而其他結(jié)點是操作符。編輯ppt表達(dá)式樹的構(gòu)造〖例〗給定中綴表達(dá)式:

現(xiàn)在從對應(yīng)的后綴表達(dá)式構(gòu)建語義樹ab+cde+**abT2aT1b+cdec+T1T2de+abc+deT1T2*+abc+deT1T2**〖Example〗(a

+

b)*

(

c

*(d

+

e

))=編輯ppt§2二叉樹voidinorder(tree_ptrtree){if(tree){inorder(tree->Left);visit(tree->Element);inorder(tree->Right);}}中序遍歷IterativeProgramvoiditer_inorder(tree_ptrtree){Stack

S=CreateStack(MAX_SIZE);

for(;;){

for(;tree;tree=tree->Left)Push(tree,S);tree=Top(S);Pop(S);

if(!tree)break;visit(tree->Element);tree=tree->Right;}}

二叉樹的遍歷編輯ppt編輯pptvoidpreorder(tree_ptrtree){if(tree){visit(tree->Element);preorder(tree->Left);preorder(tree->Right);}}先序遍歷voidpostorder(tree_ptrtree){if(tree){postorder(tree->Left);postorder(tree->Right);visit(tree->Element);}}后序遍歷編輯ppt〖例〗對表達(dá)式樹進(jìn)行遍歷:A+BCD+ADBC中序遍歷

A+BCD

后序遍歷ABCD

+

先序遍歷+

A

BCD編輯ppt§3查找樹ADT–二叉查找樹【定義】二叉查找樹是一棵二叉樹?？赡転榭?，若非空，則滿足以下性質(zhì)：每個結(jié)點有一個整數(shù)關(guān)鍵字，且關(guān)鍵字互異。非空左子樹上的結(jié)點關(guān)鍵字的值必須小于子樹的根結(jié)點的關(guān)鍵字值。非空右子樹上的結(jié)點關(guān)鍵字的值必須大于子樹的根結(jié)點的關(guān)鍵字值。

左右子樹也是二叉查找樹。305240201512251022607080651.定義編輯ppt§3二叉查找樹2.ADT數(shù)據(jù)元素集:一個有0個或多個元素的有窮結(jié)點集合。操作集:SearchTreeMakeEmpty(SearchTreeT);PositionFind(ElementTypeX,SearchTreeT);PositionFindMin(SearchTreeT);PositionFindMax(SearchTreeT);SearchTreeInsert(ElementTypeX,SearchTreeT);SearchTreeDelete(ElementTypeX,SearchTreeT);ElementTypeRetrieve(PositionP);編輯ppt§3二叉查找樹3.實現(xiàn)FindPositionFind(ElementTypeX,SearchTreeT){

if(T==NULL)

returnNULL;/*notfoundinanemptytree*/

if(X<T->Element)/*ifsmallerthanroot*/

returnFind(X,T->Left);/*searchleftsubtree*/

elseif(X>T->Element)/*iflargerthanroot*/

returnFind(X,T->Right);/*searchrightsubtree*/

else/*ifX==root*/ returnT;/*found*/}T(N)=S(N)=O(d)d

是X的深度這個測試必須首先進(jìn)行嗎?它們是尾遞歸。如何消除？編輯ppt§3二叉查找樹PositionIter_Find(ElementTypeX,SearchTreeT){

/*iterativeversionofFind*/

while(T){

if(X==T->Element)

returnT;/*found*/

if(X<T->Element)T=T->Left;/*movedownalongleftpath*/

else T=T->Right;/*movedownalongrightpath*/}/*endwhile-loop*/

returnNULL;/*notfound*/}編輯ppt查找最大和最小元素最大元素一定是在樹的最右分枝的端結(jié)點上最小元素一定是在樹的最左分枝的端結(jié)點上181015207229最左端點最右端點§3二叉查找樹編輯ppt§3二叉查找樹FindMinPositionFindMin(SearchTreeT){

if(T==NULL)

returnNULL;/*notfoundinanemptytree*/

elseif(T->Left==NULL)returnT;/*foundleftmost*/

elsereturnFindMin(T->Left);/*keepmovingtoleft*/}

FindMaxPositionFindMax(SearchTreeT){

if(T!=NULL)

while(T->Right!=NULL) T=T->Right;/*keepmovingtofindrightmost*/

returnT;/*returnNULLortherightmost*/}

T(N)=O(d)T(N)=O(d)編輯ppt§3二叉查找樹Insert305240算法梗概:Insert80檢查80

是否已在樹中；80>40,所以它必定是40的右孩子。80Insert35檢查35

是否在樹中；35<40,所以它必定是40的左孩子。35Insert25檢查25

是否在樹中；25>5,所以它必定是5的右孩子。25這是我們搜索關(guān)鍵值時遇到的最后一個結(jié)點。它必定是這個新結(jié)點的父結(jié)點。〖分析〗將元素X插入二叉搜索樹中，關(guān)鍵是要找到元素應(yīng)該插入的位置。位置的確定可以利用與查找函數(shù)Find類似的方法，如果在樹中找到X，說明要插入的元素已存在，可放棄插入操作。如果沒找到X，查找終止的位置就是X應(yīng)插入的位置。編輯ppt§3二叉查找樹SearchTreeInsert(ElementTypeX,SearchTreeT){if(T==NULL){/*Createandreturnaone-nodetree*/

T=malloc(sizeof(structTreeNode));

if(T==NULL)

FatalError("Outofspace!!!");

else{

T->Element=X;

T->Left=T->Right=NULL;}}/*Endcreatingaone-nodetree*/

else

/*Ifthereisatree*/

if(X<T->Element)

T->Left=Insert(X,T->Left);

else

if(X>T->Element)

T->Right=Insert(X,T->Right);

/*ElseXisinthetreealready;we'lldonothing*/

returnT;/*Donotforgetthisline!!*/

}怎么處理重復(fù)值?T(N)=O(d)編輯ppt§3二叉查找樹Delete二叉搜索樹的刪除操作比其它操作更為復(fù)雜，有三種情況需要考慮：要刪除的是葉結(jié)點——可以直接刪除，然后再修改其父結(jié)點的指針。圖1二叉搜索樹葉結(jié)點的刪除301541335035要刪除結(jié)點〖例1〗：刪除35編輯ppt圖2具有一個子樹的結(jié)點刪除要刪除的結(jié)點只有一個孩子結(jié)點——刪除之前需要改變其父結(jié)點的指針，指向要刪除結(jié)點的孩子結(jié)點。要刪除結(jié)點（只有一個孩子）3015415035333015415035〖例2〗：刪除33§3二叉查找樹36編輯ppt圖3具有兩個子樹的結(jié)點刪除要刪除的結(jié)點有左、右兩棵子樹——為了保持二叉搜索樹的有序性，替代被刪除的元素的位置可以有兩種選擇：一種是取其右子樹中的最小元素；另一個是取其左子樹中的最大元素。41503015333534〖例3〗：刪除41(a)取右子樹中的最小元素替代41353450301533(b)取左子樹中的最大元素替代37編輯ppt§3二叉查找樹SearchTreeDelete(ElementTypeX,SearchTreeT){PositionTmpCell;

if(T==NULL)Error("Elementnotfound");

elseif(X<T->Element)/*Goleft*/

T->Left=Delete(X,T->Left);

elseif(X>T->Element)/*Goright*/

T->Right=Delete(X,T->Right);

else

/*Foundelementtobedeleted*/

if(T->Left&&T->Right){/*Twochildren*/

/*Replacewithsmallestinrightsubtree*/

TmpCell=FindMin(T->Right); T->Element=TmpCell->Element; T->Right=Delete(T->Element,T->Right);}/*Endif*/

else{/*Oneorzerochild*/

TmpCell=T;

if(T->Left==NULL)/*Alsohandles0child*/

T=T->Right;

elseif(T->Right==NULL)T=T->Left;

free(TmpCell);}/*Endelse1or0child*/

returnT;}T(N)=O(h)h

是樹的高度。編輯ppt§3二叉查找樹Note:

如果刪除次數(shù)不多，那么懶惰刪除是可行的：為每個結(jié)點添加一個標(biāo)識域，標(biāo)記結(jié)點是可用還是已被刪除。因此我們可以刪除一個結(jié)點而不實際地釋放結(jié)點空間。如果被刪除的結(jié)點重新插入，就不需要再次調(diào)用malloc了。當(dāng)樹中被刪除的結(jié)點數(shù)目和活躍結(jié)點的數(shù)目相當(dāng)時，操作的效率會受到很大的影響嗎？編輯ppt§3二叉查找樹4.平均情形分析問題:

若一棵二叉查找樹中包含

n

個元素，這棵樹有多高？答案:

樹的高度依賴于插入的次序?！祭浇o定元素1,2,3,4,5,6,7.將它們按以下順序插入一棵二叉查找樹：4,2,1,3,6,5,7和1,2,3,4,5,6,74567213h=22314567h=6編輯ppt§3二叉查找樹【定義】一棵包含N個結(jié)點的樹的內(nèi)部路徑長被定義為：d(i)

是結(jié)點i

的深度【定理】假設(shè)所有的二叉查找樹是等概率出現(xiàn)的，那么平均的

D(N)

(包括所有可能的輸入序列)是

O(NlogN)。

因此任意結(jié)點的期望深度是

O(logN).證明:

D(N)=D(i)+D(Ni1)+N

1rooti

nodesNi1

nodes+1由于所有的子樹大小是等概率的，因此

D(i)和

D(Ni1)的平均值都是=p.212-213=O(NlogN)編輯ppt§4AVL樹目標(biāo):

加速搜索（包括插入和刪除）。工具:

二叉查找樹rootsmalllarge問題:

雖然

Tp=O(height),但是height最壞情況下可能高達(dá)O(N)。編輯ppt§4AVL樹〖例〗不同的插入次序，將導(dǎo)致不同的深度和平均查找長度ASL。(a)按一月到十二月的自然月份序列輸入所生成的；

(b)輸入序列為（July,Feb,May,Mar,Aug,Jan,Apr,Jun,Oct,Sept,Nov,Dec）

(c)輸入序列則是按月份字符串從小到大的順序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept按ASL的定義，可以分別計算出三棵二叉搜索樹的平均查找長度：ASL(a)=(1+2×2+3×3+4×3+5×2+6×1)/12=3.5；ASL(b)=(1+2×2+3×4+4×5)/12=3.0；ASL(c)=(1+2×1+3×1+4×1+5×1+6×1+7×1+8×1+9×1+10×1+11×1+12×1)/12=6.5；編輯ppt§4AVL樹Adelson-Velskii-Landis(AVL)Trees(1962)【定義】一棵空的二叉樹是高度平衡的。如果T

是一棵非空二叉樹，有左子樹

TL

和右子樹

TR,那么T是高度平衡的（AVL樹），當(dāng)且僅當(dāng)：

(1)

TL

和

TR

是高度平衡的,而且

(2)|hL

hR|1，hL

和

hR

是

TL

和

TR

各自的高度。【定義】平衡因子BF(node)=hL

hR

。在一棵AVL樹中,

BF(node)=1,0,或1。582143778214354563217空樹的高度定義為–1.編輯ppt§4AVL樹〖例1〗輸入月份MarMar01MayMay0NovNov012May01Nov0021Mar000首個不平衡的“發(fā)現(xiàn)者”是Mar（未必是根結(jié)點），它是調(diào)整起點位置。而“麻煩結(jié)點”Nov在發(fā)現(xiàn)者右子樹的右邊，因而叫RR插入，需要RR旋轉(zhuǎn)（右單旋）；一般情況:A1B0BLBRALRR插入RR旋轉(zhuǎn)A2B1BLBRALBLB0AALBR0A不一定是樹的根Singlerotation編輯ppt§4AVL樹AugMay01Nov0021Mar011Aug0AprApr0122LL旋轉(zhuǎn)May01Nov0021Aug0111Mar00Apr0一般情況:A1B0BRBLARLL插入A2B1BRBLARLL旋轉(zhuǎn)B0AARBLBR0

首個“發(fā)現(xiàn)者”是Mar；“麻煩結(jié)點”Apr在發(fā)現(xiàn)者左子樹的左邊，因而叫LL插入；編輯ppt§4AVL樹May01Nov0021Aug0111Mar00Apr0JanJan0112LR旋轉(zhuǎn)Mar01May0121Aug0101Jan00Apr0Nov0一般情況:A1B0BLARC0CRCLLR插入A2B1BLARC1CRCLORLR旋轉(zhuǎn)BLARC0A1or0CRB0or1CLOR雙旋轉(zhuǎn)首個“發(fā)現(xiàn)者”是May；“麻煩結(jié)點”Jan在左子樹的右邊，因而叫LR插入；編輯ppt§4AVL樹DecJulyMar01May0121Aug0111Jan0Apr0Nov0July0Dec0FebFeb01122RL旋轉(zhuǎn)July0Dec01Aug0121Jan0101Feb00Apr0Mar01May01211Nov0一般情況:A1B0BRALC0CLCRRL插入A2B1BRALC1CLCRORRL旋轉(zhuǎn)BRALC0A0or1CLB1or0CROR編輯ppt§4AVL樹July0Dec01Aug0121Jan0101Feb00Apr0Mar01May01211Nov0JuneOctSeptJune01112Nov0Dec01Aug121Feb01July1Apr0Mar0May1June0Jan0Oct01211Oct0Dec01Aug121Feb01July1Apr0Mar0Nov0June0Jan0May0Sept01111Note:有時候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計算一些平衡因子。另一個方法是為每一個結(jié)點保存一個

height

信息。編輯ppt§4AVL樹AvlTreeInsert(ElementTypeX,AvlTreeT){if(T==NULL){/*Createandreturnaone-nodetree*/T=malloc(sizeof(structAvlNode));

if(T==NULL)FatalError("Outofspace!!!");

else{T->Element=X;T->Height=0;T->Left=T->Right=NULL;}}/*Endcreatingaone-nodetree*/

else if(X<T->Element){/*handleleftinsertion*/ T->Left=Insert(X,T->Left);

if(Height(T->Left)-Height(T->Right)==2)/*notbalanced*/

if(X<T->Left->Element)/*LLRotation*/ T=SingleRotateWithLeft(T);

else

/*LRRotation*/ T=DoubleRotateWithLeft(T);}/*Endleft*/

elseif(X>T->Element){/*handlerightinsertion*/ T->Right=Insert(X,T->Right);

if(Height(T->Right)-Height(T->Left)==2)/*notbalanced*/

if(X>T->Right->Element)/*RRRotation*/ T=SingleRotateWithRight(T);

else

/*RLRotation*/ T=DoubleRotateWithRight(T);}/*Endright*/

/*ElseXisinthetreealready;we'lldonothing*/T->Height=Max(Height(T->Left),Height(T->Right))+1;

returnT;}編輯ppt§4AVL樹最后一個問題:查找和插入的時間復(fù)雜性Tp=O(h)

其中

h

是二叉樹的高度，但是，

h=?設(shè)

nh

為高度為h的平衡二叉樹的最小結(jié)點數(shù).二叉樹看起來應(yīng)該是如下結(jié)構(gòu)形式：Ah2h1Ah2h1或nh=nh1+nh2+1

斐波那契序列:F0=0,F1=1,Fi=Fi1+Fi2fori>1nh=Fh+21,forh0斐波那契序列的理論值是：編輯pptnh=nh1+nh2+1設(shè)

nh

是高度為h的平衡二叉樹的最小結(jié)點數(shù).h

nhFh011121242373412552086331375421888349………………nh=Fh+21,（對

h0）給定結(jié)點數(shù)為

n的AVL樹的最大高度為O(log2n)！

從而保證了AVL樹的查找時間性能為O(log2n)！

§4AVL樹編輯ppt§5伸展樹目標(biāo):

任意

M

次從空樹開始連續(xù)的操作最多花費O(MlogN)的時間。

這是否意味著每個操作只需花費O(logN)時間?不，這意味著攤還時間是O(logN).

所以單次操作可能仍需要

花費O(N)時間?

那么，重點是什么？這個界是很弱的，但效果是相同的：不存在壞的輸入序列。

但是，如果一個結(jié)點需要

O(N)時間去訪問，我們可以持續(xù)訪問它

M

次,對嗎？

我們當(dāng)然可以–那只是意味著

任何時候結(jié)點被訪問后必須被移動。Idea:

一個結(jié)點被訪問后，它將通過一系列的AVL樹的旋轉(zhuǎn)操作被推至根處。編輯pptk5Fk4Ek3Dk2Ak1CB§5伸展樹k5Fk4Ek3Dk2BAk1Ck5Fk4Ek2BAk1k3DCk5Fk4Ek2BAk1k3DCk4Ek5Fk2BAk1k3DC沒起作用!編輯ppt§5伸展樹更壞的情況:12213321Insert:1,2,3,…N321NFind:1321NFind:2312N……Find:N321NT(N)=O(N2)編輯ppt§5伸展樹另想辦法–對任意非根結(jié)點

X,用P

指代它的父結(jié)點，

G

代表它的祖父結(jié)點:情況1:

P

是根結(jié)點旋轉(zhuǎn)

X

和

P情況2:

P

不是根結(jié)點之字形GDPAXBCXGCDPAB雙旋轉(zhuǎn)一字形GDPCXAB單旋轉(zhuǎn)XAPBGDC編輯ppt§5伸展樹k5Fk4Ek3Dk2Ak1CBk5Fk4Ek1k3DCk2BAk1k2BAk4k5FEk3DC伸展操作不僅將被訪問結(jié)點移到根處，而且整體上將路徑上大部分結(jié)點的深度減少了將近一半。編輯ppt§5伸展樹Insert:1,2,3,4,5,6,771654327654132Find:176145321674532一個32個結(jié)點的例子在圖4.52–4.60編輯ppt§5伸展樹Deletions:步驟1:FindX;X