《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述》課件第8章

第8章搜索樹(shù)8.1二叉搜索樹(shù)8.2*二叉平衡樹(shù)8.3B-樹(shù)8.4*鍵樹(shù)8.5*伸展樹(shù)習(xí)題88.1二叉搜索樹(shù)

二叉搜索樹(shù)(binarysearchtree)也稱二叉排序樹(shù)(binarysorttree)，是一種最容易實(shí)現(xiàn)的搜索樹(shù)。下面討論二叉搜索樹(shù)的定義，搜索、插入和刪除運(yùn)算以及這些運(yùn)算的效率。8.1.1二叉搜索樹(shù)的定義設(shè)結(jié)點(diǎn)由關(guān)鍵字值表征，假定所有結(jié)點(diǎn)的關(guān)鍵字值各不相同，那么二叉搜索樹(shù)或者是一棵空二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

(1)若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值；

(2)若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值；

(3)左、右子樹(shù)也分別是二叉搜索樹(shù)。

圖8－1二叉搜索樹(shù)若以中序遍歷一棵二叉搜索樹(shù)，將得到一個(gè)以關(guān)鍵字值遞增排列的有序序列。所以二叉搜索樹(shù)也稱二叉排序樹(shù)。二叉搜索樹(shù)的存儲(chǔ)結(jié)構(gòu)與普通的二叉樹(shù)完全相同，并假定集合的元素為Entry類型。8.1.2二叉搜索樹(shù)的搜索在一棵二叉搜索樹(shù)上，搜索指定關(guān)鍵字值為k的元素的遞歸算法是：若二叉樹(shù)為空，則搜索失敗，否則，將k與根結(jié)點(diǎn)的關(guān)鍵字值比較，若k小于該關(guān)鍵字值，則用同樣的方法搜索左子樹(shù)，而不必搜索右子樹(shù)；若k大于該關(guān)鍵字值，則用同樣的方法搜索右子樹(shù)，而不必搜索左子樹(shù)；若k等于該關(guān)鍵字值，則搜索成功終止。只有搜索到達(dá)空子樹(shù)時(shí)，搜索算法才失敗終止。程序8－1為二叉搜索樹(shù)搜索的遞歸算法。

二叉搜索樹(shù)搜索的迭代算法使用while循環(huán)，從根結(jié)點(diǎn)開(kāi)始搜索。它將待查關(guān)鍵字值k與根結(jié)點(diǎn)的關(guān)鍵字值比較；若k小于該關(guān)鍵字值，則繼續(xù)搜索左子樹(shù)，否則繼續(xù)搜索右子樹(shù)；若k等于該關(guān)鍵字值，則搜索成功終止。只有搜索到達(dá)空子樹(shù)時(shí)，搜索才失敗終止。程序8－2是二叉搜索樹(shù)搜索的迭代算法。8.1.3二叉搜索樹(shù)的插入在二叉搜索樹(shù)上插入一個(gè)新元素，首先應(yīng)搜索新元素的插入位置。搜索插入位置的方法與BtSearch2函數(shù)的做法類似，但要求在從根結(jié)點(diǎn)往下搜索的過(guò)程中，要記錄下當(dāng)前元素的雙親結(jié)點(diǎn)，并以指針q指示。如果在搜索中遇到相同關(guān)鍵字值的元素，則表明有重復(fù)元素，那么顯示“Duplicate”信息。搜索到達(dá)空子樹(shù)時(shí)結(jié)束，表示二叉搜索樹(shù)中不包含待插入的新元素x，此時(shí)，指針q指向新元素插入后的雙親結(jié)點(diǎn)。算法構(gòu)造一個(gè)新結(jié)點(diǎn)用以存放新元素x，設(shè)新結(jié)點(diǎn)由指針r指示。如果原二叉搜索樹(shù)是空樹(shù)，則新結(jié)點(diǎn)*r成為新二叉搜索樹(shù)的根；否則新結(jié)點(diǎn)*r將成為結(jié)點(diǎn)*q的孩子。如果新元素x的關(guān)鍵字值小于q結(jié)點(diǎn)的關(guān)鍵字值，則*r將成為*q的左孩子，否則成為其右孩子。程序8－3給出了二叉搜索樹(shù)的插入算法，函數(shù)NewNode2見(jiàn)程序2－4。圖8－2顯示了在二叉搜索樹(shù)中，插入43的執(zhí)行過(guò)程。【程序8－3】二叉搜索樹(shù)的插入運(yùn)算。BOOLInsert(BTree*Bt,Kx){ BTNode*r,*p=Bt->Root,*q;KeyTypek=x.Key;while(p){ q=p; if(k<p->Element.Key)p=p->LChild; elseif(k>p->Element.Key)p=p->RChild; else{ printf("Duplicate\n");returnFALSE; /*插入失敗*/ }}r=NewNode2(x); /*程序2－4*/if(Bt->Root) if(k<q->Element.Key)q->LChild=r;elseq->RChild=r;elseBt->Root=r;returnTRUE; /*插入成功*/}圖8－2二叉搜索樹(shù)的插入運(yùn)算(X.Key=43)(a)p=Bt->Root;(b)q=p;p=p->Rchild;(c)q=p;p=p->Rchild;(d)r=NewNode2(x);q->Rchild=r圖8－3二叉搜索樹(shù)的構(gòu)造過(guò)程

(a)空樹(shù)；(b)插入28；(c)插入21；(d)插入25；(e)插入36；(f)插入33；(g)插入438.1.4二叉搜索樹(shù)的刪除在二叉搜索樹(shù)上刪除一個(gè)結(jié)點(diǎn)也很方便。首先應(yīng)搜索被刪除的元素。搜索刪除元素的方法與Insert函數(shù)的做法類似，要求在從根結(jié)點(diǎn)往下搜索的過(guò)程中，記錄下當(dāng)前元素的雙親結(jié)點(diǎn)，并用指針q指示。如果不存在該元素，那么顯示“Noelementwithkey”信息。如果存在待刪除的結(jié)點(diǎn)，設(shè)其由指針p指示，則刪除結(jié)點(diǎn)*p的操作可分下面兩種情況討論。(1)若結(jié)點(diǎn)*p有兩棵非空子樹(shù)，這時(shí)需搜索*p的中序遍歷下的直接后繼(或前驅(qū))結(jié)點(diǎn)*s，將*s的值復(fù)制到*p中，也稱為替代(replace)，因?yàn)?s最多只有一棵非空子樹(shù)，這樣一來(lái)，問(wèn)題就轉(zhuǎn)化為刪除最多只有一棵非空子樹(shù)的問(wèn)題。下面考慮*p只有一棵非空子樹(shù)和*p是葉子的情況。

(2)若結(jié)點(diǎn)*p只有一棵非空子樹(shù)或*p是葉子，若p->LChild非空，則由p->LChild取代p，否則由p->Rchild取代p。事實(shí)上，若*p是葉子，將以NULL取代p。

程序中用以取代*p的結(jié)點(diǎn)由指針c指示，c可以為空指針。若被刪除的結(jié)點(diǎn)原來(lái)是根結(jié)點(diǎn)，則刪除后，用來(lái)取代它的結(jié)點(diǎn)(可以是空樹(shù))成為新的根。一個(gè)被刪除的結(jié)點(diǎn)，如果原來(lái)是其雙親的左孩子，則取代它的結(jié)點(diǎn)(子樹(shù))也應(yīng)成為該雙親的左孩子(左子樹(shù))，反之亦然。最后需要使用free語(yǔ)句釋放結(jié)點(diǎn)*p所占用的空間。程序8－4給出了二叉搜索樹(shù)的刪除算法。圖8－4表明了在二叉搜索樹(shù)上，刪除一個(gè)有左右孩子的結(jié)點(diǎn)的執(zhí)行過(guò)程。圖8－5為在不同情況下從一棵二叉搜索樹(shù)上刪除元素的例子。圖8－4刪除一個(gè)有左右孩子的結(jié)點(diǎn)圖8－5二叉搜索樹(shù)的刪除運(yùn)算(a)二叉搜索樹(shù)；(b)刪除23；(c)刪除21；(d)刪除28【程序8－4】二叉搜索樹(shù)的刪除運(yùn)算。BOOLRemove(BTree*Bt,KeyTypek,T*x){

BTNode*c,*r,*s,*p=Bt->Root,*q;while(p&&p->Element.Key!=k) /*搜索待刪除的結(jié)點(diǎn)*p，q指示其雙親*/

{ q=p; if(k<p->Element.Key)p=p->LChild; elsep=p->RChild;

}if(!p){

/*不存在給定關(guān)鍵字的元素*/ printf("\nNoelementwithkeyk");

returnFALSE;

/*刪除失敗*/}8.1.5二叉搜索樹(shù)的高度一棵有n個(gè)元素的二叉搜索樹(shù)的高度最高可以到n。例如從空樹(shù)開(kāi)始，依次將關(guān)鍵字序列(20，30，40，50，60，70)插入二叉搜索樹(shù)中，得到的樹(shù)的高度為n=6。因此最壞情況下，對(duì)樹(shù)的搜索、插入和刪除操作的時(shí)間為O(n)。但是當(dāng)進(jìn)行隨機(jī)插入和刪除時(shí)，二叉搜索樹(shù)的平均高度為O(lbn)。因此，對(duì)樹(shù)的搜索、插入和刪除操作的平均時(shí)間為O(lbn)。

假設(shè)在一個(gè)有n(n≥1)個(gè)關(guān)鍵字的序列中，有i個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，n－i－1個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字。由此序列構(gòu)成的二叉搜索樹(shù)，其左子樹(shù)上有i個(gè)結(jié)點(diǎn)，而右子樹(shù)上有n－i－1個(gè)結(jié)點(diǎn)。設(shè)pi(n)就是在這樣一棵二叉搜索樹(shù)上以等概率進(jìn)行搜索，成功搜索一個(gè)元素的平均比較次數(shù)，設(shè)p(n)是在一棵有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)上成功搜索一個(gè)元素的平均比較次數(shù)，那么我們有：(8－1)式中，這樣，(8－3)(8－2)可以用數(shù)學(xué)歸納法證明：(n≥2)(8－4)

由此可見(jiàn)，在隨機(jī)情況下，二叉搜索樹(shù)操作的平均時(shí)間為O(lbn)，但在特定情況下，會(huì)產(chǎn)生形同線性鏈表的退化了的二叉搜索樹(shù)形，從而使搜索時(shí)間加大。8.2二叉平衡樹(shù)8.2.1二叉平衡樹(shù)的定義二叉平衡樹(shù)(balancedbinarytree)又稱AVL樹(shù)(G.M.Adel'son-Vel'skii和E.M.Landis)。它或者是一棵空二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

(1)它的左、右子樹(shù)高度之差的絕對(duì)值不超過(guò)1；

(2)它的左、右子樹(shù)都是二叉平衡樹(shù)。

二叉樹(shù)上結(jié)點(diǎn)的平衡因子(balancefactor)定義為該結(jié)點(diǎn)的左子樹(shù)的高度減去右子樹(shù)的高度?？梢?jiàn)二叉平衡樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是－1、0和1。只要二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該樹(shù)就不是二叉平衡樹(shù)。圖8－6(a)是AVL樹(shù)，而圖8－6(b)不是AVL樹(shù)。圖中結(jié)點(diǎn)中的值是平衡因子。圖8－6二叉平衡樹(shù)與非二叉平衡樹(shù)

(a)AVL樹(shù)；(b)非AVL樹(shù)AVL樹(shù)可采用二叉鏈表存儲(chǔ)。為簡(jiǎn)化插入和刪除操作，可以為每個(gè)結(jié)點(diǎn)增加一個(gè)平衡因子域Bf，這樣，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如下：么二叉平衡樹(shù)的結(jié)點(diǎn)類型為：typedefstructavlnode{KElement;intBf;structavlnode*LChild,*RChild;}AVLNode;8.2.2二叉平衡樹(shù)的平衡旋轉(zhuǎn)二叉平衡樹(shù)的插入可先按普通二叉搜索樹(shù)的插入方法進(jìn)行，但插入新結(jié)點(diǎn)后的新樹(shù)可能不再是AVL樹(shù)，這時(shí)需要重新平衡，使之仍具平衡性和排序性。圖8－7是一棵二叉平衡樹(shù)，結(jié)點(diǎn)內(nèi)是關(guān)鍵字值，結(jié)點(diǎn)邊上注明該結(jié)點(diǎn)的平衡因子值。我們將在這棵樹(shù)上分別插入四個(gè)結(jié)點(diǎn)14、25、35和44。虛線圈指明這四個(gè)結(jié)點(diǎn)如果按照普通二叉搜索樹(shù)的插入運(yùn)算插入的話，它們的預(yù)定插入位置。圖中四個(gè)元素的插入分別代表如下四種不同情況。圖8－7二叉平衡樹(shù)以及待插入的結(jié)點(diǎn)

(1)插入25：從根到25的路徑上，所有結(jié)點(diǎn)的平衡因子均為0，插入新元素25后，這棵樹(shù)仍然是二叉平衡樹(shù)，但整棵樹(shù)高度加1。

(2)插入35：從根到35的路徑上，43的平衡因子不為0，新元素35被插在36的較矮的子樹(shù)上，插入后，該樹(shù)仍然是二叉平衡樹(shù)。

(3)插入14：從根到14的路徑上，12的平衡因子不為0，新元素14被插在12的較高的子樹(shù)上，即14被插在12的右孩子的左子樹(shù)(theleftsubtreeoftherightchild)上，插入后，原樹(shù)不再是二叉平衡樹(shù)。(4)插入44：從根到44的路徑上，43和56的平衡因子都不為0，其中56是離44最近的平衡因子值不為零的結(jié)點(diǎn)。新元素44被插在56的較高的那棵子樹(shù)上，即44被插在56的左孩子的左子樹(shù)(theleftsubtreeoftheleftchild)上。插入后，原樹(shù)不再是二叉平衡樹(shù)。一般地，一個(gè)新結(jié)點(diǎn)插入后，會(huì)影響從根到新結(jié)點(diǎn)的路徑上所有結(jié)點(diǎn)的平衡因子值。如果新結(jié)點(diǎn)插在這條路徑上某個(gè)結(jié)點(diǎn)的左子樹(shù)上，那么該結(jié)點(diǎn)的平衡因子將加1，否則將減1。

如果插入前從根結(jié)點(diǎn)到新結(jié)點(diǎn)的插入位置的路徑上所有結(jié)點(diǎn)的平衡因子均為0，那么插入后這棵樹(shù)仍然是二叉平衡樹(shù)，而整棵樹(shù)的高度加1。如果在這條路徑上，某個(gè)結(jié)點(diǎn)(設(shè)其為s)的平衡因子不為0，但自它以下直至新結(jié)點(diǎn)的所有結(jié)點(diǎn)的平衡因子原先都為0，那么，插入新結(jié)點(diǎn)后，以結(jié)點(diǎn)s為根的子樹(shù)將是有可能不平衡的最小子樹(shù)，如圖8－7中的12和56。我們希望將重新平衡的范圍局限于以s為根的這棵子樹(shù)上。為了討論方便，我們將這棵最小子樹(shù)的根稱為s結(jié)點(diǎn)(spectialnode)。

另外，為了便于插入算法的討論，我們作以下假定：

(1)結(jié)點(diǎn)s是新結(jié)點(diǎn)q的具有非零平衡因子值(插入前的值)的最近的祖先。

(2)新結(jié)點(diǎn)q已插在結(jié)點(diǎn)s的左子樹(shù)上。

(3)從結(jié)點(diǎn)s到新結(jié)點(diǎn)q的路徑上所有結(jié)點(diǎn)(不含s)的平衡因子值均已修正。上面只假定新結(jié)點(diǎn)q插在結(jié)點(diǎn)s的左子樹(shù)上的情況，顯然還有一種對(duì)偶的情況，新結(jié)點(diǎn)q插在s的右子樹(shù)上的情況，其分析方法完全相同。

1.情況一若插入前，從根結(jié)點(diǎn)到新結(jié)點(diǎn)q的插入位置的路徑上，所有結(jié)點(diǎn)的平衡因子值均為0，則插入q后，只需將根結(jié)點(diǎn)的平衡因子改為1，并將AVL樹(shù)的高度加1，插入操作就完成了，見(jiàn)圖8－8。圖8－8二叉平衡樹(shù)的插入：情況一

(a)舉例；(b)一般情況

2.情況二若新結(jié)點(diǎn)q插在結(jié)點(diǎn)s較矮的子樹(shù)上(s的平衡因子Bf為－1，并假定q插在s的左子樹(shù)上)，則插入后只需令s的平衡因子Bf為0，插入算法就終止了。圖8－9中，s指向39，插入前結(jié)點(diǎn)39的平衡因子為－1，插入后應(yīng)修正為0。新結(jié)點(diǎn)q的平衡因子總是0，因它是葉子。圖8－9二叉平衡樹(shù)的插入：情況二(a)舉例；(b)一般情況

3.情況三新結(jié)點(diǎn)q插在結(jié)點(diǎn)s的較高的子樹(shù)上。根據(jù)前面的假定，此時(shí)，s自身的平衡因子值尚未修改，而從s到新結(jié)點(diǎn)q的路徑上，其余結(jié)點(diǎn)的平衡因子都是修改以后的值。情況三又可細(xì)分為兩種不同情況。(1)情況三之一：LL旋轉(zhuǎn)。新結(jié)點(diǎn)q插在結(jié)點(diǎn)s的左孩子的左子樹(shù)上，設(shè)r是s的左孩子，這時(shí)s的平衡因子Bf為1且r的平衡因子Bf為1。這里s的平衡因子Bf為1是插入前的值，而r的平衡因子Bf為1是已修正后的值。顯然，插入q后，以s為根的子樹(shù)的平衡性被破壞了。在這種情況下，用以恢復(fù)平衡的操作稱為L(zhǎng)L旋轉(zhuǎn)。LL旋轉(zhuǎn)是當(dāng)新結(jié)點(diǎn)被插在s的左孩子的左子樹(shù)上時(shí)，為重新恢復(fù)二叉樹(shù)的平衡性而執(zhí)行的操作。重新平衡的操作及對(duì)結(jié)點(diǎn)s和r的平衡因子值的修正如圖8－10所示，圖中關(guān)鍵字值按字典次序確定大小順序。與這一情況相對(duì)應(yīng)的平衡操作是RR旋轉(zhuǎn)，RR旋轉(zhuǎn)是新結(jié)點(diǎn)插在s的右孩子的右子樹(shù)上時(shí)使用的平衡操作。在圖8－10(a)中，插入新結(jié)點(diǎn)apr后，必須使用LL旋轉(zhuǎn)操作，重新平衡以結(jié)點(diǎn)s(mar)為根的子樹(shù)。執(zhí)行LL旋轉(zhuǎn)后，結(jié)點(diǎn)r(aug)成為新子樹(shù)的根，它取代結(jié)點(diǎn)s，鏈接至原結(jié)點(diǎn)s的雙親結(jié)點(diǎn)may上。執(zhí)行LL旋轉(zhuǎn)后，得到的以r為根的新子樹(shù)是二叉平衡樹(shù)，且它與以s為根的原子樹(shù)有相同的高度，由它取代以s為根的子樹(shù)，可以使得插入新結(jié)點(diǎn)后的二叉樹(shù)仍然是二叉平衡樹(shù)。圖8－10情況三之一：LL旋轉(zhuǎn)(a)舉例；(b)一般情況

下面的程序段說(shuō)明了LL旋轉(zhuǎn)以及修正結(jié)點(diǎn)平衡因子的做法(設(shè)(*s)是指向前面定義的s結(jié)點(diǎn)的指針):r=(*s)->LChild; if(r->Bf==1){ /*LL旋轉(zhuǎn)*/(*s)->LChild=r->RChild;r->RChild=*s;(*s)->Bf=0;*s=r;

}LL旋轉(zhuǎn)首先將r的右子樹(shù)(改接成s的左子樹(shù)((*s)->LChild=r->RChild;)，再使s成為r的右孩子(r->RChild=*s;)，并將s的平衡因子值修改為0((*s)->Bf=0;)。r是新子樹(shù)的根，它的平衡因子為0，放在稍后修改，最后將指針(*s)指向新子樹(shù)的根r。(2)情況三之二：LR旋轉(zhuǎn)。若新結(jié)點(diǎn)插在結(jié)點(diǎn)s的左子樹(shù)的右子樹(shù)上，這時(shí)s的平衡因子值為+1且r的平衡因子值為－1(請(qǐng)注意，根據(jù)假定，此時(shí)s的平衡因子值尚未修改，r的平衡因子值已作了修改)。這種情況下，執(zhí)行的重新平衡的操作稱為L(zhǎng)R旋轉(zhuǎn)，它是一種所謂的雙重旋轉(zhuǎn)。

在圖8－11(a)中，新元素jun被插在結(jié)點(diǎn)s的左子樹(shù)的右子樹(shù)上，其中，mar是從根結(jié)點(diǎn)到j(luò)un的路徑上離jun最近的平衡因子不為零的結(jié)點(diǎn)，所以結(jié)點(diǎn)mar可確定為結(jié)點(diǎn)s，r是s的左孩子。經(jīng)過(guò)LR旋轉(zhuǎn)，重新調(diào)整以s為根的子樹(shù)的樹(shù)形，得到圖中以u(píng)為根的新子樹(shù)。該新子樹(shù)自身是二叉平衡樹(shù)，并且它的高度與s子樹(shù)插入前的高度相同，因而由它取代s子樹(shù)，可以保證插入新結(jié)點(diǎn)后的二叉樹(shù)仍是二叉平衡樹(shù)。圖8－11情況三之二：LR旋轉(zhuǎn)(a)舉例；(b)一般情況

執(zhí)行LR旋轉(zhuǎn)后，必須修改結(jié)點(diǎn)s、r和u的平衡因子值。它們的修改需要根據(jù)u的平衡因子值確定。圖8－11(b)只列出了一種可能的情況，即新結(jié)點(diǎn)q插在結(jié)點(diǎn)u的右邊，還可以有插在左邊，以及q就是u這樣兩種不同的情況。圖8－12顯示了LR旋轉(zhuǎn)中，修改平衡因子值的三種不同情況。圖8－12LR旋轉(zhuǎn)中的平衡因子修正

下面的程序段說(shuō)明了LR旋轉(zhuǎn)以及修正s、r和u三個(gè)結(jié)點(diǎn)的平衡因子的做法。語(yǔ)句：u=r->RChild;、r->RChild=u->LChild;、u->LChild=r;、(*s)->LChild=u->RChild;、u->Rchild=*s;用于重新鏈接子樹(shù)，恢復(fù)子樹(shù)的平衡性。switch語(yǔ)句根據(jù)u->Bf的值，分三種情況修改s和r的平衡因子值。u是新子樹(shù)的根，其平衡因子值稍后修改為0。最后，u成為新子樹(shù)的根(*s=u;)。else{ /*LR旋轉(zhuǎn)*/u=r->RChild;r->RChild=u->LChild;u->LChild=r;(*s)->LChild=u->RChild;u->RChild=*s;switch(u->Bf){ case1:(*s)->Bf=－1;r->Bf=0;break; case0:(*s)->Bf=r->Bf=0;break; case－1:(*s)->Bf=0;r->Bf=1;}*s=u;}

我們已經(jīng)看到，當(dāng)一個(gè)結(jié)點(diǎn)插在s的左子樹(shù)上時(shí)，需要通過(guò)LL或LR旋轉(zhuǎn)來(lái)恢復(fù)其平衡性。程序8－5是實(shí)現(xiàn)這一目標(biāo)的C語(yǔ)言程序，被稱為左旋轉(zhuǎn)(LeftRotation)函數(shù)，它在處理情況三時(shí)，當(dāng)新結(jié)點(diǎn)插在結(jié)點(diǎn)s的左子樹(shù)上時(shí)的重新平衡事項(xiàng)，涉及LL和LR旋轉(zhuǎn)。其對(duì)偶的情況是當(dāng)新結(jié)點(diǎn)插在結(jié)點(diǎn)s的右子樹(shù)上的情況，讀者可比照上面的討論自行分析。LL旋轉(zhuǎn)和RR旋轉(zhuǎn)合稱單一旋轉(zhuǎn)，LR旋轉(zhuǎn)和RL旋轉(zhuǎn)合稱雙重旋轉(zhuǎn)?！境绦?－5】左旋轉(zhuǎn)函數(shù)。voidLeftRotation(AVLNode**s,int*unbalanced){ AVLNode*u,*r; r=(*s)->LChild;if(r->Bf==1){ /*LL旋轉(zhuǎn)*/ (*s)->LChild=r->RChild;r->RChild=*s; (*s)->Bf=0;*s=r;}else{ u=r->RChild; r->RChild=u->LChild;u->LChild=r; (*s)->LChild=u->RChild;u->RChild=*s; switch(u->Bf){ case1:(*s)->Bf=－1;r->Bf=0;break; case0:(*s)->Bf=r->Bf=0;break; case－1:(*s)->Bf=0;r->Bf=1; } *s=u;}(*s)->Bf=0;*unbalanced=FALSE;}8.2.3二叉平衡樹(shù)的插入下面是二叉平衡樹(shù)插入的遞歸算法。在集合上定義的Insert函數(shù)調(diào)用AVLIst遞歸函數(shù)，實(shí)現(xiàn)在集合中插入元素x的運(yùn)算。

AVLIst遞歸函數(shù)的主要步驟有：

(1)搜索新元素x的插入位置，構(gòu)造新結(jié)點(diǎn)并插入之；

(2)修正從新結(jié)點(diǎn)到結(jié)點(diǎn)s的平衡因子；

(3)如果是情況一和情況二，則算法結(jié)束，否則調(diào)用LeftRotation函數(shù)或RightRotation函數(shù)，完成以s為根的子樹(shù)的重新平衡，包括適當(dāng)修正平衡因子。

函數(shù)AVLIst最初從根結(jié)點(diǎn)起，以遞歸方式搜索新元素的插入位置，直至到達(dá)空子樹(shù)為止，此時(shí)，構(gòu)造一個(gè)新結(jié)點(diǎn)，由指針變量*p指示(參數(shù)p是指向一個(gè)指針變量的指針)，并對(duì)unbalanced賦初值TRUE。這次函數(shù)的遞歸調(diào)用，將向上一層的調(diào)用函數(shù)返回指向新結(jié)點(diǎn)的指針*p。如果新結(jié)點(diǎn)是其雙親的左孩子，則新結(jié)點(diǎn)將被鏈接至其雙親的LChild域，否則將鏈接至Rchild域。如果調(diào)用函數(shù)在執(zhí)行調(diào)用語(yǔ)句AVLIst(&(*p)->LChild,x,unbalanced);后到達(dá)空子樹(shù)，則新結(jié)點(diǎn)將成為其雙親的左孩子；如果調(diào)用函數(shù)在執(zhí)行調(diào)用語(yǔ)句AVLIst(&(*p)->RChild,x,unbalanced);后到達(dá)空子樹(shù)，則新結(jié)點(diǎn)成為雙親的右孩子。注意語(yǔ)句中實(shí)在參數(shù)的類型必須正確。

在創(chuàng)建新結(jié)點(diǎn)后，遞歸函數(shù)的執(zhí)行將逐層返回其調(diào)用函數(shù)。在返回到上一層后，將根據(jù)當(dāng)前結(jié)點(diǎn)的平衡因子值，確定應(yīng)作何操作。例如，從函數(shù)調(diào)用AVLIst(&(*p)->LChild,x,unbalanced)返回后(從左子樹(shù)返回)，在*unbalanced為TRUE條件下，算法將根據(jù)當(dāng)前結(jié)點(diǎn)的平衡因子值，執(zhí)行下列不同操作：

switch((*p)->Bf){ case－1:(*p)->Bf=0;*unbalanced=FALSE;break; case0:(*p)->Bf=1;break; case1:LeftRotation(p,unbalanced); }

如果當(dāng)前結(jié)點(diǎn)(由*p指示)的平衡因子為0，則執(zhí)行(*p)->Bf=1后繼續(xù)返回上一層；如果為－1，表示是情況二，執(zhí)行(*p)->Bf=0后，將*unbalanced變量置成FALSE，表示處理應(yīng)當(dāng)結(jié)束，在以后的返回過(guò)程中，將不再作任何處理；如果為+1，表示是情況三，應(yīng)執(zhí)行左旋轉(zhuǎn)函數(shù)LeftRotation。至于是LL旋轉(zhuǎn)，還是LR旋轉(zhuǎn)，將由LeftRotation函數(shù)確定。程序8－6為二叉平衡樹(shù)的插入運(yùn)算函數(shù)Insert，它調(diào)用遞歸函數(shù)AVLIst。函數(shù)AVLIst中使用函數(shù)LeftRotation和RightRotation實(shí)現(xiàn)情況三的旋轉(zhuǎn)平衡，包括LL、RR、LR和RL四種不同的旋轉(zhuǎn)方法。函數(shù)RightRotation見(jiàn)程序8－7。【程序8－6】二叉平衡樹(shù)的插入。BOOLAVLIst(AVLNode**p,Kx,BOOL*unbalanced){BOOLresult=TURE;if(!*p){*unbalanced=TRUE;*p=NewNode2(x);}elseif(x.Key<(*p)->Element.Key){ /*x.Key<(*p)->Element.Key*/result=AVLIst(&(*p)->LChild,x,unbalanced);if(*unbalanced) switch((*p)->Bf){case－1:(*p)->Bf=0;*unbalanced=FALSE;break;case0:(*p)->Bf=1;break;case1:LeftRotation(p,unbalanced);}}elseif(x.Key==(*p)->Element.Key){ /*x.Key==(*p)->Element.Key*/*unbalanced=FALSE; printf("\nThekeyisalreadyinthetree\n"); result=FALSE;}else{ /*x.Key>(*p)->Element.Key*/ result=AVLIst(&(*p)->RChild,x,unbalanced); if(*unbalanced) switch((*p)->Bf){ case1:(*p)->Bf=0;*unbalanced=FALSE;break; case0:(*p)->Bf=-1;break; case－1:RightRotation(p,unbalanced);}}returnresult;}BOOLInsert(BTree*Bt,Kx){ BOOLunbalanced; returnAVLIst(&Bt->Root,x,&unbalanced);}【程序8－7】函數(shù)RightRotation。voidRightRotation(AVLNode**s,int*unbalanced){ AVLNode*u,*r; r=(*s)->RChild; if(r->Bf==－1){ (*s)->RChild=r->LChild;r->LChild=*s; (*s)->Bf=0;*s=r; } else{u=r->LChild;r->LChild=u->RChild;u->RChild=r;(*s)->RChild=u->LChild;u->LChild=*s; switch(u->Bf){ case1:(*s)->Bf=0;r->Bf=－1;break; case0:(*s)->Bf=r->Bf=0;break; case－1:(*s)->Bf=1;r->Bf=0;} *s=u;}(*s)->Bf=0; *unbalanced=FALSE;}圖8－13二叉平衡樹(shù)的插入過(guò)程

(a)插入45；(b)插入28;(c)插入15；(d)LL旋轉(zhuǎn)后；(e)插入12；

(f)插入14；(g)LR旋轉(zhuǎn)后；(h)插入23；(i)LR旋轉(zhuǎn)后8.2.4二叉平衡樹(shù)的刪除從二叉平衡樹(shù)上刪除一個(gè)結(jié)點(diǎn)可用與插入一個(gè)結(jié)點(diǎn)相同的思路，即通過(guò)旋轉(zhuǎn)實(shí)現(xiàn)重新平衡。與二叉搜索樹(shù)刪除一樣，需先將刪除一個(gè)結(jié)點(diǎn)k的問(wèn)題簡(jiǎn)化為“當(dāng)被刪除的結(jié)點(diǎn)k最多只有一個(gè)孩子”的情形。當(dāng)k有兩個(gè)孩子時(shí)，尋找該結(jié)點(diǎn)在中序遍歷次序下的后繼結(jié)點(diǎn)(或前驅(qū)結(jié)點(diǎn))q，結(jié)點(diǎn)q必定只有一個(gè)孩子。用q的元素值替代k的元素值?，F(xiàn)在問(wèn)題成為“從一棵二叉平衡樹(shù)中刪除最多只有一個(gè)孩子的結(jié)點(diǎn)q”的問(wèn)題。

刪除最多只有一個(gè)孩子的結(jié)點(diǎn)q，只需將q的雙親p指向q的那個(gè)孩子。如果q是葉子，則p將指向空子樹(shù)。這樣一來(lái)，原先以q為根的子樹(shù)由它的孩子取代后，該子樹(shù)變矮。這種高度的改變會(huì)影響q的祖先結(jié)點(diǎn)的平衡性。我們從q的雙親p開(kāi)始考察一棵子樹(shù)的平衡性。如果該子樹(shù)的平衡性被破壞，則應(yīng)重新平衡之。對(duì)一棵子樹(shù)進(jìn)行重新平衡的操作可能使該子樹(shù)變矮，從而影響其雙親的平衡性?？梢允褂靡粋€(gè)布爾變量shorter記錄對(duì)其雙親的平衡性的影響。如果shorter為FALSE，則表示當(dāng)前考慮的子樹(shù)高度不變，因此不會(huì)影響其雙親的平衡性。shorter的初值為TRUE?，F(xiàn)分三種情況加以討論。

1.情況一：p的平衡因子為0

從p的子樹(shù)上刪除結(jié)點(diǎn)后，該子樹(shù)變矮，但以p為根的子樹(shù)的高度不變，只需適當(dāng)修改p的平衡因子，刪除過(guò)程就可完成。所以可令shorter為FALSE，表示算法可終止，見(jiàn)圖8－14。圖8－14二叉平衡樹(shù)的刪除：情況一

圖8－15是情況一的一個(gè)例子。為了刪除15，首先必須尋找15的中序遍歷下的后繼結(jié)點(diǎn)(也可以是前驅(qū)結(jié)點(diǎn))，現(xiàn)為16。用16取代15后，只需實(shí)際刪除原結(jié)點(diǎn)16即可，這樣被實(shí)際刪除的結(jié)點(diǎn)最多只有一棵子樹(shù)。由于結(jié)點(diǎn)q(即16)的雙親p的平衡因子為0，刪除結(jié)點(diǎn)q后，以p為根的子樹(shù)仍然是平衡的，并且它的高度不變，因此，刪除過(guò)程可以結(jié)束(shorter＝FALSE)。圖8－15二叉平衡樹(shù)的刪除：情況一舉例

2.情況二：從p的較高的子樹(shù)上刪除一個(gè)結(jié)點(diǎn)從p的較高的子樹(shù)上刪除結(jié)點(diǎn)后，該子樹(shù)變矮，以p為根的子樹(shù)也隨之變矮，但該子樹(shù)本身仍然是平衡樹(shù)。此時(shí)：一方面，應(yīng)將p的平衡因子置成0；另一方面，由于以p為根的子樹(shù)變矮，可能會(huì)影響以p的雙親結(jié)點(diǎn)為根的子樹(shù)的平衡性。因此，應(yīng)繼續(xù)考慮以p的雙親為根的子樹(shù)的平衡問(wèn)題，shorter保持TRUE不變，表示需檢查以p的雙親為根的子樹(shù)的平衡性是否因子樹(shù)p變矮而被破壞，見(jiàn)圖8－16。

圖8－16二叉平衡樹(shù)的刪除：情況二

在圖8－17的例子中，為了刪除20，必須先用25替代它，然后刪除原結(jié)點(diǎn)25。刪除25的操作是用它的惟一的孩子取代它，鏈接至25的雙親30上。由于q在p的較高的子樹(shù)上，q被刪除后，該子樹(shù)變矮。雖然此時(shí)以p為根的子樹(shù)是平衡的，但它變矮了。這種變矮可能會(huì)影響以p的雙親為根的子樹(shù)的平衡性，所以還需進(jìn)一步檢查以p的雙親為根的子樹(shù)。從圖中可見(jiàn)，p的雙親p'原先的平衡因子值為0，它的右子樹(shù)變矮只是使它的平衡因子值從0改為＋1，但它仍然是平衡樹(shù)，無(wú)須作其它調(diào)整，即對(duì)p'而言，它屬于情況一，可按情況一對(duì)待。圖8－17二叉平衡樹(shù)的刪除：情況二舉例

3.情況三：從p的較矮的子樹(shù)上刪除一個(gè)結(jié)點(diǎn)

從p的較矮的子樹(shù)上刪除一個(gè)結(jié)點(diǎn)，則以p為根的子樹(shù)的平衡性被破壞，要通過(guò)旋轉(zhuǎn)來(lái)恢復(fù)這棵子樹(shù)的平衡性。設(shè)r是p的較高的子樹(shù)的根。根據(jù)r的平衡因子的值，可以進(jìn)一步細(xì)分為以下三種不同處理方式：

(1)r的平衡因子為0時(shí)，應(yīng)采用單一旋轉(zhuǎn)，并修改p和r的平衡因子的值。重新平衡之后，新子樹(shù)與原子樹(shù)有相同的高度，不會(huì)影響二叉平衡樹(shù)的其余部分，令shorter為FALSE，算法終止，見(jiàn)圖8－18。圖8－18二叉平衡樹(shù)的刪除：情況三之一(單一旋轉(zhuǎn))(2)r的平衡因子與p的平衡因子同號(hào)時(shí)，仍采用單一旋轉(zhuǎn)。旋轉(zhuǎn)后p和r的平衡因子均為0，重新平衡之后，新子樹(shù)變矮，故shorter仍為TRUE，應(yīng)繼續(xù)考察原p的雙親結(jié)點(diǎn)的平衡性，見(jiàn)圖8－19。

(3)r的平衡因子與p的平衡因子異號(hào)時(shí)，應(yīng)采用雙重旋轉(zhuǎn)。令u是r的較高的一棵子樹(shù)的根，它將成為新子樹(shù)的根，取代以p為根的子樹(shù)，u的平衡因子為0，p和r的平衡因子作相應(yīng)的修正。這棵以u(píng)為根的子樹(shù)是平衡的，但高度變矮，故shorter仍為TRUE，應(yīng)繼續(xù)向樹(shù)根方向考察，見(jiàn)圖8－20。圖8－19二叉平衡樹(shù)的刪除：情況三之二(單一旋轉(zhuǎn))圖8－20二叉平衡樹(shù)的刪除：情況三之三(雙重旋轉(zhuǎn))8.2.5二叉平衡樹(shù)的高度當(dāng)用二叉搜索樹(shù)表示集合時(shí)，對(duì)于給定的數(shù)據(jù)可以構(gòu)造一棵最佳樹(shù)形，即它具有最小高度，但也可能得到一棵退化的樹(shù)。要始終保持最佳樹(shù)形是極其困難的，AVL搜索樹(shù)是最佳二叉搜索樹(shù)和任意二叉搜索樹(shù)之間的折衷。因?yàn)閷?duì)于二叉平衡樹(shù)，我們有以下結(jié)論。

假定Nh是一棵高度為h的具有最少結(jié)點(diǎn)數(shù)的AVL樹(shù)的結(jié)點(diǎn)數(shù)目。根據(jù)平衡性要求，它的左、右子樹(shù)的高度必然一棵為h－1，另一棵為h－1或h－2?？梢詳喽ㄋ鼈円彩窍嗤叨鹊亩嫫胶鈽?shù)中結(jié)點(diǎn)數(shù)目最少的(不然，可以用同樣高度的但結(jié)點(diǎn)數(shù)目更少的二叉平衡樹(shù)取代之)。因此有：N0=0，N1=1，Nh=Nh－1+Nh－2+1(h≥2)(8－5)可以看到，Nh的定義與斐波那契級(jí)數(shù)的定義：

F0=0，F(xiàn)1=1，F(xiàn)h=Fh－1+Fh－2

(8－6)非常相似，因此有：

Nh=Fh+2－1(h≥0)(8－7)

因?yàn)镕h≈

h/，其中，

(1+)/2，則有Nh≈

h+2/－1。如果樹(shù)中有n個(gè)結(jié)點(diǎn)，那么樹(shù)的最大高度為log

((n+1))－2＝O(lbn)

二叉平衡樹(shù)的搜索與二叉搜索樹(shù)沒(méi)有任何不同。搜索時(shí)間取決于樹(shù)的高度。因此，在二叉平衡樹(shù)上進(jìn)行搜索的最壞情況下的時(shí)間復(fù)雜度是O(lbn)。8.3B－樹(shù)

當(dāng)集合足夠小，可以駐留在內(nèi)存中時(shí)，相應(yīng)的搜索方法稱為內(nèi)搜索(internalsearch)。內(nèi)存中的集合用AVL樹(shù)表示能夠獲得很好的性能。如果文件很大，以至計(jì)算機(jī)的內(nèi)存容納不下時(shí)，它們必須存放在外存中(如磁盤、磁帶等)。在外存中搜索給定關(guān)鍵字的元素的方法稱為外搜索(externalsearch)。8.3.1m叉搜索樹(shù)對(duì)于磁盤上的大文件，我們也可以用樹(shù)形結(jié)構(gòu)表示，但此時(shí)的鏈接域(即指針域)的值已不是內(nèi)存地址，而是磁盤存儲(chǔ)器的地址。如果將一個(gè)有N＝106個(gè)記錄組成的磁盤文件組織成一棵二叉搜索樹(shù)(或二叉平衡樹(shù))，其高度約為lbN＝lb106≈20。這也就是說(shuō)，為了查找一個(gè)記錄，可能需要存取磁盤20次，這是不能承受的。我們知道磁盤的讀寫時(shí)間遠(yuǎn)慢于內(nèi)存訪問(wèn)的時(shí)間，因此，設(shè)法減少磁盤存取操作的次數(shù)是設(shè)計(jì)算法時(shí)應(yīng)充分考慮的問(wèn)題。采用多叉樹(shù)代替二叉樹(shù)，在一個(gè)結(jié)點(diǎn)中存放多個(gè)元素而不是一個(gè)元素是明智的做法。例如，我們可以將7個(gè)元素組織在一個(gè)結(jié)點(diǎn)中(也稱一頁(yè))，如圖8－21所示。圖8－21二叉搜索樹(shù)的分頁(yè)

下面給出m叉搜索樹(shù)的定義。

m叉搜索樹(shù)或者是一棵空樹(shù)，或者是一棵滿足下列特性的樹(shù)：

(1)根結(jié)點(diǎn)最多有m棵子樹(shù)，并具有如下結(jié)構(gòu)：

n，P0，(K1，P1)，(K2，P2)，…，(Kn，Pn)其中，Pi是指向子樹(shù)的指針，Ki是元素的關(guān)鍵字值，1≤i≤n＜m。

(2)?Ki<Ki+1,1≤i＜n。

(3)子樹(shù)Pi上的所有關(guān)鍵字值都大于Ki，小于Ki+1,0＜i＜n。

(4)子樹(shù)P0上的所有關(guān)鍵字值都小于K1，子樹(shù)Pn上的所有關(guān)鍵字值都大于Kn。

(5)子樹(shù)Pi，0≤i≤n也是m叉搜索樹(shù)。

由上述定義可知，一個(gè)多叉搜索樹(shù)的結(jié)點(diǎn)中，最多存放m－1個(gè)元素和m個(gè)指向子樹(shù)的指針。每個(gè)結(jié)點(diǎn)中元素按關(guān)鍵字值遞增排序，一個(gè)元素的關(guān)鍵字值大于它的左子樹(shù)上所有結(jié)點(diǎn)中的元素的關(guān)鍵字值，小于它的右子樹(shù)上所有結(jié)點(diǎn)中的元素的關(guān)鍵字值。每個(gè)結(jié)點(diǎn)中包含的元素個(gè)數(shù)總是比它所包含的指針數(shù)少一，空樹(shù)除外。所以這是一種搜索樹(shù)。

圖8－22是一個(gè)多叉搜索樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)。圖8－23給出了一棵四叉搜索樹(shù)，圖中的小方塊代表空樹(shù)。空樹(shù)也稱為失敗結(jié)點(diǎn)(failurenode)，因?yàn)檫@是當(dāng)搜索某個(gè)關(guān)鍵字值x不在樹(shù)中時(shí)到達(dá)的子樹(shù)。失敗結(jié)點(diǎn)不包含元素。圖8－23中，根結(jié)點(diǎn)有兩個(gè)孩子，樹(shù)中結(jié)點(diǎn)內(nèi)的關(guān)鍵字有序排列，孩子數(shù)最多為4，所以它是四叉搜索樹(shù)。圖8－22多叉搜索樹(shù)結(jié)點(diǎn)

(a)多叉搜索樹(shù)結(jié)點(diǎn)舉例；(b)多叉搜索樹(shù)結(jié)點(diǎn)

要從圖8－23的四叉搜索樹(shù)中搜索關(guān)鍵字值為53的元素，應(yīng)先從根結(jié)點(diǎn)開(kāi)始，首先從磁盤讀入根結(jié)點(diǎn)，并在該結(jié)點(diǎn)中進(jìn)行搜索，53比35大，則沿著35右邊的子樹(shù)向下搜索，并再?gòu)?3和78中間的子樹(shù)上找到53。圖8－23四叉搜索樹(shù)

設(shè)一棵m叉搜索樹(shù)的高度為h，則該樹(shù)上最多的結(jié)點(diǎn)數(shù)目(不包含失敗結(jié)點(diǎn))為(8－9)

每個(gè)結(jié)點(diǎn)最多有m－1個(gè)元素，則m叉搜索樹(shù)最多有mh－1個(gè)元素。由于高度為h的搜索樹(shù)中元素的個(gè)數(shù)在h到mh－1之間，所以，一棵有N個(gè)元素的m叉搜索樹(shù)的高度在logm(N+1)～N之間。一棵高度為5的200叉搜索樹(shù)最多能容納32*1010－1個(gè)元素，也可以只有5個(gè)元素。同樣一棵有32*1010－1個(gè)元素的200叉搜索樹(shù)的高度可以是5，也可以是32*1010－1。所以，這里定義的m叉搜索樹(shù)也會(huì)像普通的二叉搜索樹(shù)一樣，產(chǎn)生退化的樹(shù)形。由于對(duì)存儲(chǔ)在磁盤上的搜索樹(shù)進(jìn)行搜索、插入和刪除操作的時(shí)間主要取決于訪問(wèn)磁盤的次數(shù)，所以，應(yīng)當(dāng)避免產(chǎn)生退化樹(shù)形。B－樹(shù)就是一種多叉平衡樹(shù)。8.3.2B－樹(shù)的定義

1970年，R.BayerE.Mereight提出了一種外搜索樹(shù)，稱為B－樹(shù)，這是一種多叉平衡樹(shù)，它在修改(插入和刪除)過(guò)程中有簡(jiǎn)單的平衡算法。B－樹(shù)的一些改進(jìn)形式已成為索引文件的一種有效結(jié)構(gòu)，得到了廣泛的應(yīng)用。一棵m階B－樹(shù)是一棵m叉搜索樹(shù)，它或者是空樹(shù)，或者是滿足下列特性的樹(shù)：

(1)根結(jié)點(diǎn)至少有兩個(gè)孩子。

(2)除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外的所有結(jié)點(diǎn)至少有(m/2(個(gè)孩子。(3)所有失敗結(jié)點(diǎn)均在同一層上。上述定義表明，B－樹(shù)是一棵多叉搜索樹(shù)，它通過(guò)限制每個(gè)結(jié)點(diǎn)中包含的元素的最少個(gè)數(shù)，以及要求所有的失敗結(jié)點(diǎn)(空子樹(shù))都在同一層上，來(lái)防止產(chǎn)生退化樹(shù)形。例如，圖8－24是一棵4階B－樹(shù)，結(jié)點(diǎn)中最少的元素個(gè)數(shù)為(m/2(－1=1個(gè)，最多的元素個(gè)數(shù)為m－1=3個(gè)。圖8－244階B－樹(shù)8.3.3B－樹(shù)的高度

B－樹(shù)具有這樣的性質(zhì)：設(shè)B－樹(shù)的失敗結(jié)點(diǎn)的總數(shù)是s，那么一棵B－樹(shù)的元素總數(shù)N是B－樹(shù)的失敗結(jié)點(diǎn)的總數(shù)減1，即N=s－1?，F(xiàn)在來(lái)說(shuō)明這一點(diǎn)。在B－樹(shù)中，每個(gè)非失敗結(jié)點(diǎn)中包含的元素的數(shù)目比它所包含的指針數(shù)少1。設(shè)非失敗結(jié)點(diǎn)的個(gè)數(shù)為n，則B－樹(shù)的元素總數(shù)N等于所有非失敗結(jié)點(diǎn)包含的指針總數(shù)t減去n，即N=t－n，而指針總數(shù)t等于除根結(jié)點(diǎn)以外，失敗結(jié)點(diǎn)數(shù)和非失敗結(jié)點(diǎn)數(shù)的總和，即t=n＋s－1，所以n＋s－1=N＋n，因此，N=s－1，即一棵B－樹(shù)所包含的元素總數(shù)是B－樹(shù)的失敗結(jié)點(diǎn)的總數(shù)減1。

結(jié)點(diǎn)所在的最大層次是B－樹(shù)的高度。那么，包含N個(gè)元素的m階B－樹(shù)的最大高度是多少呢？根據(jù)B－樹(shù)的定義，第一層為根結(jié)點(diǎn)。根結(jié)點(diǎn)至少有兩個(gè)孩子，所以，第二層至少有2個(gè)結(jié)點(diǎn)。除根以外，每個(gè)非失敗結(jié)點(diǎn)至少有

m/2

個(gè)孩子，所以第三層至少有2*

m/2

個(gè)結(jié)點(diǎn)……，依此類推，第h+1層至少有2*(

m/2

)h–1個(gè)結(jié)點(diǎn)。不妨設(shè)第h+1層是失敗結(jié)點(diǎn)，并設(shè)m階B－樹(shù)有N個(gè)元素，則失敗結(jié)點(diǎn)的個(gè)數(shù)為N+1，由此可見(jiàn)：

N+1≥2*(

m/2

)h–1(8－10)所以有：(8－11)

這就是說(shuō)，在含有N個(gè)元素的B－樹(shù)上搜索一個(gè)關(guān)鍵字，從根開(kāi)始到關(guān)鍵字所在的結(jié)點(diǎn)的路徑上，涉及的結(jié)點(diǎn)數(shù)不超過(guò)1＋log

m/2

((N+1)/2)，這也是B－樹(shù)的最大高度(不含失敗結(jié)點(diǎn))。8.3.4B-樹(shù)的搜索

B-樹(shù)的搜索算法與m叉搜索樹(shù)的搜索算法相同。在搜索過(guò)程中，磁盤被訪問(wèn)的次數(shù)最多是1+log

m/2

((N+1)/2)。B-樹(shù)的結(jié)點(diǎn)可以看成一個(gè)有序表，在一個(gè)B-樹(shù)結(jié)點(diǎn)中搜索是在內(nèi)存中的搜索，因此可以采用順序搜索和二分搜索等內(nèi)搜索算法進(jìn)行。8.3.5B－樹(shù)的插入將一個(gè)元素插入B－樹(shù)中，首先要檢查B－樹(shù)中是否包含相同關(guān)鍵字值的元素，如果存在，則插入運(yùn)算失敗終止，否則搜索必定終止在失敗結(jié)點(diǎn)處，此時(shí)，將新元素插入該失敗結(jié)點(diǎn)的上一層的葉子結(jié)點(diǎn)中。例如，為了在圖8－24的4階B－樹(shù)中插入59，首先搜索新元素的插入位置。搜索在葉子結(jié)點(diǎn)的元素53和64之間的失敗結(jié)點(diǎn)處失敗，此時(shí)，可將新元素59和一個(gè)代表失敗結(jié)點(diǎn)的空指針插入53和64之間。如果插入后該葉結(jié)點(diǎn)中包含的元素個(gè)數(shù)不超過(guò)m－1，則插入成功完成。但本例中，插入59后，葉結(jié)點(diǎn)q中包含4個(gè)元素，已超過(guò)了4階B－樹(shù)的結(jié)點(diǎn)容量(見(jiàn)圖8－25(a))，此時(shí)可創(chuàng)建一個(gè)新的B－樹(shù)結(jié)點(diǎn)q'，將圖8－25(a)的結(jié)點(diǎn)中后一半的元素和指針存放到新結(jié)點(diǎn)q'中，前半部分元素和指針仍然保存在q中，但位于(m/2(處的元素53，連同指向新結(jié)點(diǎn)的指針q'一起，將存放到它的雙親結(jié)點(diǎn)中(見(jiàn)圖8－25(b))。也就是說(shuō)，結(jié)點(diǎn)q被一分為三，拆分點(diǎn)在位置(m/2(處，位于該處的元素和指向新結(jié)點(diǎn)的指針，將一起存放到其雙親結(jié)點(diǎn)中，見(jiàn)圖8－25(c)。圖8－25在圖8－24的B－樹(shù)中插入59(a)插入59；(b)結(jié)點(diǎn)分裂；(c)插入59后的B－樹(shù)

下面給出另一個(gè)B－樹(shù)插入的例子。圖8－26(a)是在3階B－樹(shù)中插入53，搜索在q結(jié)點(diǎn)的47和64之間的失敗結(jié)點(diǎn)處失敗，因此在q結(jié)點(diǎn)的47和64之間插入元素53和一個(gè)代表失敗結(jié)點(diǎn)的空指針，見(jiàn)圖8－26(b)和(c)。結(jié)點(diǎn)q在插入新元素53以后已產(chǎn)生溢出，需要分裂，分裂出現(xiàn)在結(jié)點(diǎn)q的第二個(gè)元素53處。分裂后，原結(jié)點(diǎn)q分成三部分，前一部分元素仍留在結(jié)點(diǎn)q中，后一部分元素建立一個(gè)新結(jié)點(diǎn)q'來(lái)存儲(chǔ)它們，設(shè)q'是新結(jié)點(diǎn)的地址，那么元素53和指針q'將插入原q結(jié)點(diǎn)的雙親r中，見(jiàn)圖8－26(d)和(e)。結(jié)點(diǎn)r還要再分裂，產(chǎn)生新結(jié)點(diǎn)r'，元素53和指針r'將插入原r結(jié)點(diǎn)的雙親結(jié)點(diǎn)t中，即根結(jié)點(diǎn)中，見(jiàn)圖8－26(f)和(g)，插入后的B－樹(shù)見(jiàn)圖8－26(h)。圖8－26B－樹(shù)的插入舉例

從上面的例子我們可以得到如下的在B－樹(shù)中插入新元素的方法：

(1)在B－樹(shù)中搜索給定關(guān)鍵字值的元素，如果搜索成功，表示有重復(fù)元素，插入運(yùn)算失敗終止，否則將新元素和一個(gè)空指針插入搜索失敗處的葉結(jié)點(diǎn)中。

(2)若插入新元素(和一個(gè)指針)后，結(jié)點(diǎn)q未溢出，即結(jié)點(diǎn)中包含的元素個(gè)數(shù)未超過(guò)m－1(指針數(shù)未超過(guò)m)，則插入運(yùn)算成功終止。(3)若插入新元素(和一個(gè)指針)后，結(jié)點(diǎn)q已溢出，則必須進(jìn)行結(jié)點(diǎn)的分裂操作，將結(jié)點(diǎn)一分為三。分裂發(fā)生在位置

m/2

處。關(guān)鍵字值K

m/2

之前的元素保留在原來(lái)的結(jié)點(diǎn)中，在它之后的元素存放在新創(chuàng)建的結(jié)點(diǎn)(設(shè)地址為q')中，而關(guān)鍵字值為K

m/2

的元素和地址q'將插入結(jié)點(diǎn)q的雙親結(jié)點(diǎn)中。這意味著在該雙親結(jié)點(diǎn)中新增了一個(gè)元素和一個(gè)指針，因此，必須檢查此雙親結(jié)點(diǎn)的溢出問(wèn)題。這同樣可按(2)和(3)的原則，繼續(xù)檢查和處理該雙親結(jié)點(diǎn)。(4)如果按照(3)的原則，結(jié)點(diǎn)q產(chǎn)生分裂，而結(jié)點(diǎn)q是根結(jié)點(diǎn)。根結(jié)點(diǎn)沒(méi)有雙親，那么分裂產(chǎn)生的兩個(gè)結(jié)點(diǎn)的指針q和q‘以及關(guān)鍵字為K(m/2(的元素應(yīng)組成一個(gè)新的根結(jié)點(diǎn)。這時(shí)，B－樹(shù)會(huì)長(zhǎng)高。只要從根結(jié)點(diǎn)到新元素插入位置的路徑上至少有一個(gè)結(jié)點(diǎn)未滿，則B－樹(shù)不會(huì)長(zhǎng)高。圖8－27B－樹(shù)結(jié)點(diǎn)的分裂

(a)插入新元素后產(chǎn)生溢出的B－樹(shù)結(jié)點(diǎn)；(b)分裂后的前半部分元素結(jié)點(diǎn)；

(c)分裂后的后半部分元素構(gòu)成的新結(jié)點(diǎn)；(d)分裂元素和指向新結(jié)點(diǎn)的指針

設(shè)B－樹(shù)的高度為h,那么在自頂向下搜索失敗結(jié)點(diǎn)的過(guò)程中，需要進(jìn)行h次讀盤。插入操作常需要自底向上分裂結(jié)點(diǎn)。最壞情況下，從插入新元素的葉結(jié)點(diǎn)開(kāi)始，直到根結(jié)點(diǎn)的路徑上所有結(jié)點(diǎn)都發(fā)生分裂。分裂根結(jié)點(diǎn)需要向磁盤寫3個(gè)結(jié)點(diǎn)，而分裂一個(gè)非根的結(jié)點(diǎn)則需向磁盤寫2個(gè)結(jié)點(diǎn)。如果內(nèi)存工作區(qū)足夠大，使得在向下搜索時(shí)讀入的結(jié)點(diǎn)，在向上分裂時(shí)不必再次從磁盤讀入，那么，在執(zhí)行一次插入操作時(shí)有：讀和寫盤的總次數(shù)=搜索所需的讀盤次數(shù)＋分裂所需的寫盤次數(shù)=h+2(h－1)+3＝3h+1(8－12)

假定從空樹(shù)開(kāi)始建立一棵有N個(gè)元素的m階B－樹(shù)，最終得到有p個(gè)非失敗結(jié)點(diǎn)的B－樹(shù)。此p個(gè)結(jié)點(diǎn)最多經(jīng)過(guò)p－2次分裂得來(lái)，每次分裂在B－樹(shù)上新添一個(gè)非失敗結(jié)點(diǎn)，根結(jié)點(diǎn)分裂將新增兩個(gè)非失敗結(jié)點(diǎn)。p個(gè)非失敗結(jié)點(diǎn)的m階B－樹(shù)至少有1+(

m/2

－1)(p－1)個(gè)元素，所以p個(gè)結(jié)點(diǎn)的平均分裂次數(shù)s(當(dāng)p>2時(shí))為(8－13)

若m=200，則意味著結(jié)點(diǎn)分裂的平均次數(shù)小于1/99，因此讀和寫磁盤的平均次數(shù)為

h+2s+1＜h+2/99+1≈h+1(8－14)8.3.6B－樹(shù)的刪除從B－樹(shù)上刪除一個(gè)指定的元素的操作同插入時(shí)一樣，是從葉子結(jié)點(diǎn)開(kāi)始的。如果被刪除的元素不在葉子結(jié)點(diǎn)中，那么由它的右邊的子樹(shù)上的最小元素取代之，即由大于被刪除元素的最小元素取代之。這種“替代”使得刪除操作成為從B－樹(shù)的葉結(jié)點(diǎn)中刪除一個(gè)元素的操作。圖8－28是從圖8－24的4階B-樹(shù)上刪除一個(gè)關(guān)鍵字值為35的元素的過(guò)程。

由于35不在葉子結(jié)點(diǎn)中，必須首先用39替代35，見(jiàn)圖8－28(a)。替代以后，從結(jié)點(diǎn)r中刪除39和一個(gè)空指針(見(jiàn)圖8－28(b))。刪除后，結(jié)點(diǎn)r中的元素個(gè)數(shù)不足B－樹(shù)規(guī)定的下限數(shù)(即至少(m/2(－1個(gè)元素)，從而發(fā)生下溢。解決這一問(wèn)題的做法首先是檢查其左、右兩側(cè)的兄弟結(jié)點(diǎn)中的元素個(gè)數(shù)，若左側(cè)兄弟有多余的元素，則從左側(cè)兄弟“借”一個(gè)元素，若右側(cè)兄弟有多余的元素，則從右左側(cè)兄弟“借”一個(gè)元素。這種借是采用圖8－28(c)的旋轉(zhuǎn)方式實(shí)現(xiàn)的：將雙親結(jié)點(diǎn)p中的元素43移至結(jié)點(diǎn)r，r的右側(cè)兄弟中的元素47移至雙親結(jié)點(diǎn)p，元素47左側(cè)的指針應(yīng)移到結(jié)點(diǎn)r中，成為元素43的右側(cè)指針，顯然它也是結(jié)點(diǎn)r的最右邊的指針。我們可以這樣約定，當(dāng)一個(gè)結(jié)點(diǎn)在刪除元素后，結(jié)點(diǎn)發(fā)生下溢，先檢查其左側(cè)兄弟是否有多余元素(至少(m/2(個(gè)元素)，若有，則采用上述旋轉(zhuǎn)方式借元素，否則再檢查右側(cè)兄弟是否有多余元素，若有，則向其右側(cè)兄弟借，如圖8－28的做法。圖8－28從圖8－24的B－樹(shù)上刪除35(a)替代：以39取代35；(b)從r中刪除(39,|)；

(c)借：向兄弟借一個(gè)元素；(d)刪除35之后的B－樹(shù)

但如果一個(gè)B－樹(shù)結(jié)點(diǎn)發(fā)生下溢時(shí)，其左、右兩側(cè)兄弟都恰好只有(m/2(－1個(gè)元素，那么，只能采用“連接”的方式解決此類下溢問(wèn)題。圖8－29是從圖8－28的B－樹(shù)上刪除27的過(guò)程。從結(jié)點(diǎn)s中刪除27和一個(gè)空指針后，結(jié)點(diǎn)s發(fā)生下溢，其惟一的左側(cè)兄弟s'沒(méi)有多余元素，此時(shí)只能將結(jié)點(diǎn)s與s'，以及其雙親結(jié)點(diǎn)中分割它們的元素18，組成一個(gè)結(jié)點(diǎn)。不妨假定保留結(jié)點(diǎn)s'，而將18，以及結(jié)點(diǎn)s中全部元素和指針都移到結(jié)點(diǎn)s'中，然后撤銷結(jié)點(diǎn)s。這也意味著從結(jié)點(diǎn)u中刪除18和指向s的指針。由于18和一個(gè)指針被刪除，結(jié)點(diǎn)u發(fā)生下溢，此時(shí)需從其右側(cè)兄弟r借。我們已經(jīng)看到，借是旋轉(zhuǎn)進(jìn)行的，結(jié)點(diǎn)t的39移到結(jié)點(diǎn)u，結(jié)點(diǎn)r中的47移到結(jié)點(diǎn)t中，r的最左邊的子樹(shù)成為u的最右邊的子樹(shù)，如圖8－29(c)所示。圖8－29從圖8－28的B－樹(shù)上刪除27(a)刪除(27，|)；(b)連接結(jié)點(diǎn)s和左兄弟s'；(c)刪除27之后的B－樹(shù)

從上面的例子我們可以得到從B－樹(shù)刪除元素的方法：

(1)首先搜索被刪除的元素，如果不存在被刪除的元素，則刪除運(yùn)算失敗終止；如果搜索成功，且被刪除的元素在葉子結(jié)點(diǎn)中，則從該葉子結(jié)點(diǎn)中刪除該元素；如果被刪除的元素不在葉子結(jié)點(diǎn)中，那么由它的右側(cè)子樹(shù)上的最小元素取代之(必定在葉結(jié)點(diǎn)中)，然后從葉子結(jié)點(diǎn)中刪除該替代元素。

(2)如果刪除元素后，當(dāng)前結(jié)點(diǎn)中包含至少(m/2(－1個(gè)元素，刪除運(yùn)算成功結(jié)束。(3)如果刪除元素后，當(dāng)前結(jié)點(diǎn)中包含不足(m/2(－1個(gè)元素，則稱發(fā)生下溢。處理的方法首先是借元素：如果其左側(cè)兄弟包含多余(m/2(－1個(gè)元素，則可以向其左兄弟“借”一個(gè)元素；否則如果其右側(cè)兄弟有多余元素，則向其右側(cè)兄弟借。借元素是旋轉(zhuǎn)進(jìn)行的，具體做法如圖8－28(c)所示。(4)如果刪除元素后，當(dāng)前結(jié)點(diǎn)產(chǎn)生下溢，且左、右兩側(cè)兄弟結(jié)點(diǎn)都只有(m/2(－1個(gè)元素，則只能進(jìn)行“連接”。若當(dāng)前結(jié)點(diǎn)有左側(cè)兄弟，則將該結(jié)點(diǎn)與其左側(cè)兄弟連成一個(gè)結(jié)點(diǎn)，否則與右側(cè)兄弟連接。連接是將兩個(gè)結(jié)點(diǎn)中的元素，連同它們的雙親結(jié)點(diǎn)中用來(lái)分割它們的元素組合在一個(gè)結(jié)點(diǎn)中，另一個(gè)結(jié)點(diǎn)將撤消。這意味著從其雙親結(jié)點(diǎn)中刪除分割元素和一個(gè)指向被撤銷的結(jié)點(diǎn)的指針，這可能導(dǎo)致雙親結(jié)點(diǎn)的下溢，所以需繼續(xù)檢查其雙親結(jié)點(diǎn)。應(yīng)按(2)、(3)、(4)所述方法處理從雙親結(jié)點(diǎn)中刪除元素的問(wèn)題。(5)如果由于連接操作，導(dǎo)致根結(jié)點(diǎn)中的一個(gè)元素被刪除，并且該根結(jié)點(diǎn)只包含一個(gè)元素，則其中的元素被刪除后，根結(jié)點(diǎn)成為不含任何元素的空結(jié)點(diǎn)，那么兩結(jié)點(diǎn)連接后被保留的那個(gè)結(jié)點(diǎn)將成為B－樹(shù)新的根結(jié)點(diǎn)，這時(shí)，B－樹(shù)會(huì)變矮。如果B－樹(shù)本來(lái)就只有一個(gè)根結(jié)點(diǎn)，且該根結(jié)點(diǎn)只包含一個(gè)元素，那么當(dāng)這惟一的元素被刪除后，B－樹(shù)便成為空樹(shù)。8.4*鍵樹(shù)

在前面用來(lái)表示集合的數(shù)據(jù)結(jié)構(gòu)中，元素由主關(guān)鍵字惟一標(biāo)識(shí)，關(guān)鍵字值總是作為一個(gè)整體存于結(jié)點(diǎn)中。相應(yīng)的搜索操作都是建立在關(guān)鍵字值之間比較的基礎(chǔ)上，因而被稱為比較關(guān)鍵字的搜索。

如果一個(gè)關(guān)鍵字可以表示成字符的序列，即字符串，那么我們可以用鍵樹(shù)(又稱數(shù)字搜索樹(shù)或字符樹(shù))表示這樣的字符串的集合。鍵樹(shù)是一棵多叉樹(shù)，樹(shù)中每個(gè)結(jié)點(diǎn)并不代表一個(gè)關(guān)鍵字或元素，而只代表字符串中的一個(gè)字符。例如它可以表示數(shù)字串中的一個(gè)數(shù)位，或單詞中的一個(gè)字母，或C語(yǔ)言標(biāo)識(shí)符的一個(gè)字符等等。第一層的結(jié)點(diǎn)對(duì)應(yīng)于字符串的第一個(gè)字符，第二層的結(jié)點(diǎn)對(duì)應(yīng)于字符串的第二個(gè)字符......。每個(gè)字符串可由一個(gè)特殊的字符如“(”或“$”等作為字符串的結(jié)束符，用一個(gè)葉子結(jié)點(diǎn)表示該特殊字符。把從根到葉子的路徑上，所有結(jié)點(diǎn)(除根以外)對(duì)應(yīng)的字符連接起來(lái)，就得到一個(gè)字符串。因此，每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)關(guān)鍵字。在葉子結(jié)點(diǎn)還可以包含一個(gè)指針，指向該關(guān)鍵字所對(duì)應(yīng)的元素。整個(gè)字符串集合中的字符串的數(shù)目等于葉子結(jié)點(diǎn)的數(shù)目。如果一個(gè)集合中的關(guān)鍵字都具有這樣的字符串特性，那么該關(guān)鍵字集合便可采用一棵鍵樹(shù)來(lái)表示。事實(shí)上，我們還可以賦予“字符串”更廣泛的含義，它可以是任何類型的對(duì)象組成的串。

為了搜索和插入方便，我們假定鍵樹(shù)是有序樹(shù)，即同一層中兄弟結(jié)點(diǎn)的序號(hào)自左向右有序，并約定結(jié)束符小于任何字符，它在最左邊。設(shè)有一個(gè)由13個(gè)關(guān)鍵字組成的集合：

{a,and,are,be,but,by,for,from,had,have,he,her,here}圖8－30鍵樹(shù)

如果除去鍵樹(shù)的根結(jié)點(diǎn)，鍵樹(shù)便成為森林。鍵樹(shù)本質(zhì)上是森林結(jié)構(gòu)。在鍵樹(shù)中，每一棵子樹(shù)代表具有相同前綴的關(guān)鍵字值的子集合。如圖8－31所示的子樹(shù)代表具有相同前綴“ha-”的關(guān)鍵字值的子集合{had,have}。通常鍵樹(shù)有兩種存儲(chǔ)結(jié)構(gòu)：雙鏈樹(shù)和Trie樹(shù)。下面兩小節(jié)，我們將介紹這兩種樹(shù)結(jié)構(gòu)。圖8－31子樹(shù)及其代表的關(guān)鍵字值的子集合8.4.2雙鏈樹(shù)我們可以采用前面討論的將森林和樹(shù)轉(zhuǎn)換成二叉樹(shù)的方法將圖8－30的鍵樹(shù)轉(zhuǎn)換成二叉樹(shù)形，然后采用二叉鏈表存儲(chǔ)之，這時(shí)向下是第一個(gè)孩子，向右是下一個(gè)兄弟。圖8－32給出圖8－30所示鍵樹(shù)的雙鏈樹(shù)的部分樹(shù)形。

圖8－32雙鏈樹(shù)示例

雙鏈樹(shù)的搜索可以這樣進(jìn)行：從雙鏈樹(shù)的根結(jié)點(diǎn)開(kāi)始，將關(guān)鍵字(字符串)的第一個(gè)字符與該結(jié)點(diǎn)的字符比較，若相同，則沿孩子結(jié)點(diǎn)往下再比較下一個(gè)字符，否則沿兄弟結(jié)點(diǎn)順序搜索，直到某個(gè)結(jié)點(diǎn)的值等于待比較的字符，或者某個(gè)結(jié)點(diǎn)的字符大于待查字符，或者不再有兄弟為止，則搜索失敗。若比較在葉子結(jié)點(diǎn)處終止，則搜索成功，葉子結(jié)點(diǎn)包含指向該關(guān)鍵字值所標(biāo)識(shí)的元素的指針。

雙鏈樹(shù)的插入方法是：首先進(jìn)行搜索，如插入關(guān)鍵字age，搜索在第二層的$與n字符間失敗。插入位置通常由三個(gè)指針指示：r、q和p。本例中，我們將在q和p之間插入子樹(shù){g,e$}，如圖8－33所示。在雙鏈樹(shù)上刪除一個(gè)元素的做法與插入類似，它將刪除一棵不同后綴的子樹(shù)。圖8－33雙鏈樹(shù)上插入子樹(shù){g,e$}(a)插入前；(b)插入后8.4.3Trie樹(shù)若鍵樹(shù)以多重鏈表表示，則樹(shù)中每個(gè)結(jié)點(diǎn)含有d個(gè)指針域，d是鍵樹(shù)的度，它與關(guān)鍵字值的“基”有關(guān)。基就是每一位字符所有可取的值的數(shù)目，包括結(jié)束符。若關(guān)鍵字為英文單詞，則d=27。此時(shí)的鍵樹(shù)又稱Trie(retrieval的中間四個(gè)字母)樹(shù)。若從鍵樹(shù)的某個(gè)結(jié)點(diǎn)開(kāi)始到葉子結(jié)點(diǎn)的路徑上的每個(gè)結(jié)點(diǎn)中都只有一個(gè)孩子，則可將該路徑上的所有結(jié)點(diǎn)壓縮成一個(gè)“葉子”，且在該葉子結(jié)點(diǎn)中存儲(chǔ)關(guān)鍵字值及指向該元素的指針等信息。Trie樹(shù)上有兩類結(jié)點(diǎn)：分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)。每個(gè)分支結(jié)點(diǎn)包含d個(gè)指針域和一個(gè)指示該結(jié)點(diǎn)非空指針域個(gè)數(shù)的整數(shù)。分支結(jié)點(diǎn)不包括實(shí)際字符，它所代表的字符由其雙親結(jié)點(diǎn)中指向它的指針在該雙親結(jié)點(diǎn)中的位置隱含確定。葉子結(jié)點(diǎn)包括關(guān)鍵字域和指向元素的指針域。圖8－34Trie樹(shù)示例

在Trie樹(shù)上進(jìn)行搜索的過(guò)程為：從根結(jié)點(diǎn)開(kāi)始，沿著待查關(guān)鍵字值相應(yīng)的指針逐層往下比較，直到葉子結(jié)點(diǎn)。若該結(jié)點(diǎn)的關(guān)鍵字值等于待查值，則搜索成功，否則搜索失敗。在Trie樹(shù)上容易實(shí)現(xiàn)插入和刪除操作。插入時(shí)，只需相應(yīng)地增加一些分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)。刪除時(shí)，當(dāng)分支結(jié)點(diǎn)中的非空指針數(shù)為1時(shí)便可刪除。

雙鏈樹(shù)和Trie樹(shù)是鍵樹(shù)的兩種不同的表示法，它們各有特點(diǎn)。從其存儲(chǔ)結(jié)構(gòu)可見(jiàn)，若鍵樹(shù)中結(jié)點(diǎn)的度較大，則采用Trie樹(shù)為宜。綜上所述，搜索樹(shù)的搜索都是從根結(jié)點(diǎn)開(kāi)始的，其搜索時(shí)間依賴于樹(shù)的高度。第6.5節(jié)的哈夫曼編碼樹(shù)是一個(gè)二叉Trie樹(shù)的例子。在哈夫曼樹(shù)中，編碼的完整值在葉子結(jié)點(diǎn)中。哈夫曼編碼取決于Trie樹(shù)結(jié)構(gòu)中字母的位置。8.5*伸展樹(shù)

二叉搜索樹(shù)和二叉平衡樹(shù)(AVL樹(shù))可有效實(shí)現(xiàn)搜索樹(shù)的搜索、插入和刪除運(yùn)算。采用普通的二叉搜索樹(shù)，搜索、插入和刪除運(yùn)算算法簡(jiǎn)單，容易實(shí)現(xiàn)，它們的平均情況時(shí)間復(fù)雜度都為(lbn)，但二叉搜索樹(shù)可能退化，使搜索、插入和刪除運(yùn)算的代價(jià)變得很大。采用AVL樹(shù)可克服這一點(diǎn)。AVL樹(shù)的搜索、插入和刪除運(yùn)算的最壞情況時(shí)間都是O(lbn)。改善二叉搜索樹(shù)性能的另一種可能的方法是不必總是使樹(shù)保持平衡，而是在每次運(yùn)算執(zhí)行后，做一次伸展(splay)，這種伸展操作總體上使得搜索樹(shù)趨向于平衡，但每一次單獨(dú)的伸展不一定會(huì)產(chǎn)生一棵更平衡的樹(shù)。伸展樹(shù)的伸展操作可以保證，對(duì)于一棵有n個(gè)結(jié)點(diǎn)的伸展樹(shù)，執(zhí)行一個(gè)m(m≥n)次運(yùn)算的運(yùn)算序列，花費(fèi)的總時(shí)間為O(mlbn)。這樣，一次搜索或插入運(yùn)算可能需要O(n)時(shí)間，m次這樣的運(yùn)算的總時(shí)間為O(mlbn)，平均起來(lái)，每次運(yùn)算的時(shí)間為O(lbn)。一棵伸展樹(shù)是一棵二叉搜索樹(shù)，它的搜索、插入和刪除運(yùn)算的算法與普通的二叉搜索樹(shù)完全相同，但在每次運(yùn)算執(zhí)行后緊跟一次伸展操作。一次伸展操作的開(kāi)始結(jié)點(diǎn)是指在二叉搜索樹(shù)的每次運(yùn)算(搜索、插入和刪除)結(jié)束后，應(yīng)被移至根結(jié)點(diǎn)處的結(jié)點(diǎn)。對(duì)于搜索運(yùn)算，如果被搜索的元素在樹(shù)中，則被搜索的元素是伸展操作的開(kāi)始結(jié)點(diǎn)；否則以搜索過(guò)程中遇到的最后一個(gè)元素(如果存在)作為伸展操作的開(kāi)始結(jié)點(diǎn)。對(duì)于插入運(yùn)算