第8章查找8.1查找的基本概念8.2靜態(tài)查找表8.3樹表形式的動態(tài)查找表8.4地址映射方式下的動態(tài)查找表——哈希表 8.1查找的基本概念

查找是使用最廣泛的操作之一，為了得到某些信息經(jīng)常需要進行查找。例如，學(xué)生在學(xué)習中用英文字典查找單詞；公路交通部門每天花費大量時間查找各種指定牌號的車輛；游客查找某個城市的景點、交通、街道和飲食情況；特別是在互聯(lián)網(wǎng)上查找大量的所需信息，已經(jīng)成為我們?nèi)粘Ｉ畹囊徊糠?。計算機以及計算機網(wǎng)絡(luò)使信息的查詢快捷、方便和準確。但是，要從計算機和計算機網(wǎng)絡(luò)中查找特定的信息，就需要在計算機中存儲包含該特定信息的表。在計算機中，被查找的對象是由一組記錄(數(shù)據(jù)元素)組成的表或文件，而每個記錄則是由若干個數(shù)據(jù)項組成，并且每個記錄都有一個能唯一標識該記錄的關(guān)鍵字(某一數(shù)據(jù)項)。在這種情況下，查找的定義是：給定一個值k，在含有n個記錄的表中找出關(guān)鍵字等于k的記錄。若找到，則查找成功，返回該記錄的信息或該記錄在表中的位置；否則查找失敗，返回相關(guān)的提示信息。用于查找的表和文件我們統(tǒng)稱為查找表，它是以集合為其邏輯結(jié)構(gòu)、以查找為目的的數(shù)據(jù)結(jié)構(gòu)。由于集合中的記錄之間沒有任何“關(guān)系”，因此查找表的實現(xiàn)也不受“關(guān)系”約束，而是根據(jù)實際應(yīng)用中對查找的具體要求來組織查找表，以便高效率的實現(xiàn)查找。查找表又可分為如下兩種類型：

(1)靜態(tài)查找表：對查找表的查找僅是以查詢?yōu)槟康?，不改動查找表中的記錄?/p>

(2)動態(tài)查找表：在查找過程中同時伴隨著插入不存在的記錄或者刪除某個已存在的記錄這類變更查找表的操作。查找表的典型結(jié)構(gòu)有線性表、樹表和哈希(Hash)表等。線性表常用的組織方式包括順序表、有序順序表和索引順序表等；樹表常用的組織方式包括二叉排序樹、平衡二叉樹、B樹和B+樹等。在這些結(jié)構(gòu)的查找表中，查找的效率取決于查找過程中給定的值與關(guān)鍵字的比較次數(shù)。哈希(又稱散列)表結(jié)構(gòu)是在記錄的存儲位置與該記錄的關(guān)鍵字之間建立了一個確定的關(guān)系，因此無需比較即可直接查找到記錄。

由于查找運算的主要操作是關(guān)鍵字的比較，因此，通常把查找過程中對關(guān)鍵字的比較次數(shù)作為衡量一個查找算法效率優(yōu)劣的標準，也稱為平均查找長度，通常用ASL表示。對一個含有n個記錄的表，平均查找長度ASL定義為其中，n是記錄的個數(shù)；pi是查找第i個記錄的概率(若不特別聲明，均認為對每個記錄的查找概率是相等的，即(1≤i≤n))；ci是查找第i個記錄所需進行的比較次數(shù)。 8.2靜態(tài)查找表

8.2.1順序查找

查找與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。我們以順序表作為存儲結(jié)構(gòu)來實現(xiàn)順序查找，即定義順序表類型如下：

typedefstruct

{

KeyTypekey;//KeyType為關(guān)鍵字key的數(shù)據(jù)類型

InfoTypeotherdata;//其他數(shù)據(jù)

}SeqList;在此，KeyType為一虛擬的數(shù)據(jù)類型，在實際實現(xiàn)中可為int、char等類型，InfoType也是其他數(shù)據(jù)的虛擬類型，而otherdata則代表一虛擬的其他數(shù)據(jù)，在實際實現(xiàn)中可根據(jù)需要設(shè)置為一個或多個真實的類型和真實的數(shù)據(jù)。

順序查找又稱線性查找，是最簡單、最基本的查找方法。順序查找的方法為：從表的一端開始，向另一端逐個按給定值k與表中記錄的關(guān)鍵字key值進行比較。若找到則查找成功，并給出記錄在表中的位置；若整個表掃描完仍未找到與k值相同的記錄關(guān)鍵字key值，則查找失敗，給出失敗的信息。順序查找的算法如下：

intSeqSearch(SeqListR[],intn,intk) //順序查找

{

inti=n;

R[0].key=k;//R[0].key為查找不成功的監(jiān)視哨

while(R[i].key!=k) //由表尾向表頭方向查找

i--;

returni;//查找成功返回找到的位置值否則返回0值

}在算法中，順序表中的n個數(shù)據(jù)存放于一維數(shù)組R[1]～R[n]中。在數(shù)組R中由后向前查找關(guān)鍵字(即R[i].key)值為k的記錄，若找到，則返回該記錄在數(shù)組R中的下標；若找不到，則必定查到R[0]處。由于原先已將k值存于R[0].key中，故R[0].key必然等于k，而這是在R[1]～R[n]都找不到關(guān)鍵字值為k的結(jié)果，也即查找不成功的位置。設(shè)置“監(jiān)視哨”R[0]的目的是簡化算法，即無論成功與否都通過同一個return語句返回結(jié)果值。此外，也避免了在while循環(huán)中每次都要判斷條件“i>0”以防查找中出現(xiàn)數(shù)組下標越界的情況。根據(jù)上述算法，對n個記錄的順序表采用由后向前比較方式。若給定值k與表中第i個元素的關(guān)鍵字(即R[i].key)值相等，即定位于第i個記錄時，由圖8-1可知，共對n-i+1個記錄的關(guān)鍵字進行了比較。也即，ci=n-i+1，則順序查找成功時的平均查找長度為設(shè)每個數(shù)據(jù)元素的查找概率相等，即，則有圖8-1由后向前比較到第i個記錄時比較次數(shù)示意圖查找不成功時，關(guān)鍵字的比較要由R[n].key一直持續(xù)到監(jiān)視哨R[0].key，即總共比較了n+1次。

由于上述算法中的基本工作就是關(guān)鍵字比較，因此查找長度的量級就是查找算法的時間復(fù)雜度，即為O(n)。注意，如果采用的是由前向后進行查找，則ci=i，故查找成功時的平均查找長度仍為，只不過要在while循環(huán)中增加判斷條件“i<=n”。

順序查找的缺點是當n很大時，平均查找長度較大、效率低。優(yōu)點是對表中記錄的存儲沒有過多的要求。8.2.2有序表的查找

1.折半查找

折半查找也稱二分查找，它是一種效率較高的查找方法。折半查找要求查找表必須是順序存儲結(jié)構(gòu)且表中記錄按關(guān)鍵字有序排列(即為有序表)。

折半查找的方法是：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關(guān)鍵字相等，則查找成功；否則由這個中間記錄位置把有序表劃分為兩個子表(不包括該中間記錄)。若給定值小于中間記錄的關(guān)鍵字，則在中間記錄左半?yún)^(qū)的子表去繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄右半?yún)^(qū)的子表去繼續(xù)查找。不斷重復(fù)上述查找過程，直到查找成功，或者所查找的子表區(qū)域無記錄而查找失敗。折半查找算法如下：

intBinSearch(SeqListR[],intn,intk)

{

intlow=0,high=n-1,mid;

while(low<=high) //查找區(qū)間最左記錄的位置low小于等于最右記錄的位置high

{

mid=(low+high)/2; //mid取該查找區(qū)間的中間記錄位置

if(R[mid].key==k) //當中間記錄的關(guān)鍵字與k相等時

returnmid; //查找成功

else

if(R[mid].key>k)

high=mid-1; //繼續(xù)在R[low]～R[mid-1]中查找

else

low=mid+1; //繼續(xù)在R[mid+1]～R[high]中查找

}

return-1; //查找失敗

}算法中，順序表中的n個記錄按關(guān)鍵字升序的方式存放于一維數(shù)組R[0]～R[n-1]中。整型變量low、high和mid分別用來標識查找區(qū)間最左記錄、最右記錄和中間記錄的位置。折半查找過程可用二叉樹來描述。以當前查找區(qū)間中間位置上的記錄作為根。左半?yún)^(qū)的子表和右半?yún)^(qū)的子表分別作為根結(jié)點的左、右子樹。對左、右子樹繼續(xù)這種劃分，則得到的二叉樹稱為折半查找判定樹，樹中結(jié)點內(nèi)的數(shù)字表示該結(jié)點(記錄)在有序表中的位置(位置值等于數(shù)組R中的下標值加1)。如結(jié)點個數(shù)為10的折半查找判定樹如圖8-2所示。圖8-2結(jié)點個數(shù)為10的折半查找判定樹由折半查找判定樹可知，折半查找的過程恰好是走了一條從根結(jié)點到被查結(jié)點的路徑，關(guān)鍵字進行比較的次數(shù)即為被查結(jié)點在樹中的層數(shù)。因此，折半查找成功時進行的比較次數(shù)最多不超過樹的深度，而具有n個結(jié)點的判定樹其深度為 +1。所以，折半查找成功時和給定值的比較次數(shù)至多為 。我們以樹高為k的滿二叉樹(即n=2k-1)來討論折半查找的平均查找長度，在等概率(即 )的條件下，折半查找成功的平均查找長度為當n很大時，ASL≈lb(n+1)-1。所以，折半查找的時間效率為O(lbn)。由于lb(cn+1)=k，故ASL≈k-1，即折半查找成功的平均查找長度約為折半查找判定樹的深度減1?？梢姡郯氩檎冶软樞虿檎业钠骄檎倚矢?，但折半查找只適用于順序存儲結(jié)構(gòu)。

例8.1

初始查找表關(guān)鍵字如下：

5101518212332566080

(1)查找關(guān)鍵字值為15的記錄；(2)查找關(guān)鍵字為62的記錄。

【解】對關(guān)鍵字值為15和62的折半查找過程與結(jié)果如圖8-3(a)、(b)所示。圖8-3折半查找過程示意圖對圖8-3(b)來說，第4次比較不成功時所執(zhí)行的語句是“high=mid-1;”，即high值變?yōu)?，而此時的low值為9，再次進行while循環(huán)的條件“l(fā)ow<=high”已不滿足，故終止while循環(huán)并返回-1值。

2.分塊查找

分塊查找又稱為索引順序查找，它是將順序查找與折半查找相結(jié)合的一種查找方法，在一定程度上解決了順序查找速度慢，以及折半查找要求數(shù)據(jù)元素有序排列的問題。

在分塊查找中，將表分為若干塊且每一塊中關(guān)鍵字不要求有序，但塊與塊之間的關(guān)鍵字是有序的，即后一塊中所有記錄的關(guān)鍵字均大于前一塊中的最大關(guān)鍵字。此外，還為這些塊建立了一個索引表且索引表項按關(guān)鍵字有序(為遞增有序表)，它存放各塊記錄的起始存放位置，以及該塊所有記錄中的最大關(guān)鍵字值。圖8-4給出了一個分塊查找存儲結(jié)構(gòu)示意圖。圖8-4分塊查找存儲結(jié)構(gòu)示意圖分塊查找過程分兩步走：第一步，在索引表中確定待查記錄在哪一塊，因為索引表有序，故可采用折半查找或順序查找；第二步，在已確定的塊中進行順序查找。

索引表的數(shù)據(jù)類型定義如下：

typedefstruct

{

KeyTypekey; //用于存放塊內(nèi)的最大關(guān)鍵字

intlink; //用于指向塊的起始位置

}IdxType;設(shè)索引表I長度為m，即其數(shù)組元素分別為I[0]～I[m-1]，則采用折半查找索引表的分塊查找算法如下：

intIdxSearch(IdxTypeI[],intm,SeqListR[],intk)

{//索引表I長度為m(數(shù)組元素分別為I[0]～I[m-1])

intlow=0,high=m-1,mid,i,j;

while(low<=high) //在索引表中折半查找

{

mid=(low+high)/2;

if(I[mid].key>=k)

high=mid-1;

else

low=mid+1;

}

if(low<m)

{//在索引表中找到所求的塊，接下來在順序表(即數(shù)組R)中順序查找

i=I[low+1].link-1; //i為該塊最后一個數(shù)組元素下標

j=I[low].link; //j為該塊第一個數(shù)組元素下標

while(R[i].key!=k&&i>=j)

i--;

if(i>=j)

returni; //當i>=j時查找成功返回i值

}

return-1; //查找失敗

}算法說明如下：分析圖8-3可知，無論查找是否成功，low都指向大于或等于給定值k的最接近的那個數(shù)組元素位置，這恰好是折半查找索引表時所需要的結(jié)果。對索引表進行折半查找無非是兩種情況。一種是給定的k值恰好等于索引表中的某一塊最大關(guān)鍵字值，這種情況下由圖8-3(a)可知：low、mid都指向索引表中存放該關(guān)鍵字所對應(yīng)的塊起始地址所指的數(shù)組元素下標。為了算法的簡潔，我們并不立即取得這個位置值，而是合并到關(guān)鍵字值大于k一起處理(即算法中的條件變?yōu)椤癐[mid].key>=k”；也即繼續(xù)執(zhí)行“high=mid-1;”語句)。這樣，由于此時high已小于low，即不滿足while循環(huán)條件“l(fā)ow<=high”而終止while循環(huán)，而此時的low仍為索引表中存放該塊起始位置的數(shù)組元素下標。另一種情況是查找不成功，我們此時需要的是與給定值k最接近且大于k的關(guān)鍵字所對應(yīng)塊的起始位置，而這時的low存放的正是索引表中有該起始位置的那個數(shù)組元素下標。還要考慮給出的k值大于索引表中最大關(guān)鍵字時的情況，在這種情況下，折半查找索引表的結(jié)果是low定位于并不存在的第m個數(shù)組元素，這也是判斷是否找到所求塊的條件“l(fā)ow<m”。當索引表查找到塊時，該塊第一個記錄在數(shù)組R中的下標即可由I[low].link得到，而該塊最后一個記錄在數(shù)組R中的下標則可由下一塊的起始位置減1得到，即為I[low+1].link-1。由于分塊查找實際上是兩次查找過程，因此整個分塊的平均查找長度應(yīng)該是兩次查找的平均查找長度(索引查找與塊內(nèi)查找)之和。也即分塊查找的平均查找長度為查找索引表的平均查找長度Lb與塊內(nèi)查找的平均查找長度Ls之和：ASLbs?=?Lb?+?Ls

為了進行分塊查找，可將長度為n的表均勻地分成m塊，每塊中含有t個記錄(即)。在等概率情況下，塊內(nèi)查找的概率是1/t，每塊查找的概率為1/m，則有：

(1)若順序查找確定所在的塊，則得到：

(2)用折半查找確定所在的塊，則得到：我們已經(jīng)介紹了三種靜態(tài)查找表。從表的結(jié)構(gòu)上看，順序查找對表有序、無序均適用，折半查找僅適用于有序表，而分塊查找則要求表分塊后“塊間有序、塊內(nèi)可以無序”。從表的存儲結(jié)構(gòu)來看，順序查找和分塊查找對于表的順序和鏈式存儲結(jié)構(gòu)均適用，而折半查找只適用于順序存儲結(jié)構(gòu)。就平均查找長度而言：折半查找最小，分塊查找次之，而順序查找最大。 8.3樹表形式的動態(tài)查找表

8.3.1二叉排序樹

1.二叉排序樹的定義和查找過程

二叉排序樹(BinarySortTree)又稱BST樹或二叉查找樹。它或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：

(1)若它的左子樹非空，則左子樹上所有結(jié)點(記錄)的值均小于根結(jié)點的值。

(2)若它的右子樹非空，則右子樹上所有結(jié)點的值均大于或等于根結(jié)點的值。

(3)左、右子樹本身又分別是一棵二叉排序樹。圖8-5二叉排序樹示意圖圖8-5給出了一棵二叉排序樹的示意圖。

由二叉排序樹的性質(zhì)可知：二叉排序樹可以看作是一個有序表。也即，在二叉排序樹中左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字，而右子樹所有結(jié)點的關(guān)鍵字均大于或等于根結(jié)點的關(guān)鍵字。所以，二叉排序樹上的查找與折半查找類似。

二叉排序樹的查找過程是：若二叉排序樹非空，則將給定值k與根結(jié)點關(guān)鍵字值比較；若相等，則查找成功；若不等，則當k值小于根結(jié)點關(guān)鍵字時到根的左子樹去繼續(xù)查找，否則到根的右子樹去繼續(xù)查找。二叉排序樹的這種查找過程顯然是一個遞歸過程。通常采用二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)，且二叉鏈表結(jié)點的類型定義如下：

typedefstructnode

{

KeyTypekey;//記錄簡化為僅含關(guān)鍵字項

structnode*lchild,*rchild;//左、右孩子指針

}BSTree;例8.2

已知圖8-6中的二叉排序樹中各結(jié)點的值依次為32～40，請正確標出各結(jié)點的值。圖8-6二叉排序樹中各結(jié)點形態(tài)

【解】根據(jù)二叉排序樹的性質(zhì)，進行中序遍歷所得到的一定是升序序列。因此中序遍歷圖8-6所示的二叉排序樹，并按遍歷的順序?qū)γ總€結(jié)點進行編號如圖8-7所示，再按這個編號填入32～40數(shù)字即得到如圖8-8所示的二叉排序樹。圖8-7對二叉排序樹結(jié)點進行編號圖8-8填入32～40數(shù)字后的二叉排序樹

2.二叉排序樹的查找操作

在二叉排序樹中查找其關(guān)鍵字為k的結(jié)點，若查找成功，則返回該結(jié)點的指針值；若查找失敗，則返回空指針值。

二叉排序樹查找算法如下：

BSTree*BSTSearch(BSTree*t,KeyTypek) //二叉排序樹查找

{ //在指針t所指的二叉排序樹中查找關(guān)鍵字值為k的結(jié)點

while(t!=NULL)

if(k==t->key)

returnt; //k等于根結(jié)點*t的關(guān)鍵字則查找成功，返回指針t值

else

if(k<t->key)

t=t->lchild; //k小于根結(jié)點*t的關(guān)鍵字值則到t的左子樹查找

else

t=t->rchild; //k大于根結(jié)點*t的關(guān)鍵字值則到t的右子樹查找

returnNULL; //查找失敗返回空指針值

}

3.二叉排序樹的插入操作和二叉排序樹的構(gòu)造

如果要向二叉排序樹插入一個關(guān)鍵字為k的結(jié)點，則先在二叉排序樹中進行查找。若查找成功，則待插接點已經(jīng)存在，故不用插入；若查找不成功，則新建一個關(guān)鍵字值為k的結(jié)點，然后插入之。注意，在二叉排序樹中，所有新插入的結(jié)點一定是作為葉子結(jié)點插入的。在二叉排序樹中插入一個結(jié)點的算法如下：

voidBSTCreat(BSTree*t,KeyTypek)

{ //非空二叉排序樹中插入一個結(jié)點

BSTree*p,*q;

q=t;

while(q!=NULL) //二叉排序樹非空時

if(k==q->key)

gotoL1; //查找成功，不插入新結(jié)點

else

if(k<q->key)

{//k小于結(jié)點*q的關(guān)鍵字值則到t的左子樹查找

p=q;

q=q->lchild;

}

else

{//k大于結(jié)點*q的關(guān)鍵字值則到t的右子樹查找

p=q;

q=p->rchild;

}

q=(BSTree*)malloc(sizeof(BSTree));

//查找不成功時創(chuàng)建一個新結(jié)點

q->key=k;

q->lchild=NULL; //因作為葉結(jié)點插入，故左、右指針均為空

q->rchild=NULL;

if(p->key>k)

p->lchild=q; //作為原葉結(jié)點*p的左孩子插入

else

p->rchild=q;//作為原葉結(jié)點*p的右孩子插入

L1:;

}例8.3

設(shè)關(guān)鍵字序列為：45,53,12,37,100,61,24,3,90，給出一棵二叉排序樹的構(gòu)造過程。

【解】依據(jù)關(guān)鍵字序列構(gòu)造二叉排序樹的過程示意圖如圖8-9所示。圖8-9由空樹開始構(gòu)造二叉排序樹的過程示意圖由二叉排序樹的構(gòu)造過程可以看出，每一個新結(jié)點都是作為葉結(jié)點插入到二叉排序樹中的。關(guān)鍵字序列的不同，生成的二叉排序樹也不同。如果關(guān)鍵字序列有序，則構(gòu)造的二叉排序樹為單支樹。例如當關(guān)鍵字序列為：3,12,24,37,45,53,61,90,100時，構(gòu)造的二叉排序樹如圖8-10所示。圖8-10單支二叉排序樹示意圖可以看出，中序遍歷二叉排序樹可以得到一個關(guān)鍵字有序的序列。這就是說，一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，且構(gòu)造樹的過程即是對無序序列進行排序的過程。此外，每次插入新結(jié)點都是作為二叉排序樹的葉結(jié)點插入的。也即在插入過程中無需移動二叉排序樹的其他結(jié)點，僅需改變原樹中某個葉結(jié)點的指針由空變?yōu)榉强杖ブ赶蛐虏迦氲慕Y(jié)點即可。這一特點相當于在一個有序表中插入一個新記錄卻無需移動其他記錄。因此，二叉排序樹既擁有類似折半查找的特性，又因采用了鏈式存儲而易于插入和修改結(jié)點(記錄)。由于二叉排序樹適合于記錄的頻繁插入且查找速度較快，因此是動態(tài)查找表一種較好的實現(xiàn)方法。在二叉排序樹上進行查找，若查找成功，則恰好走了一條從根結(jié)點到該結(jié)點的路徑，也即和給定值比較的關(guān)鍵字個數(shù)等于該結(jié)點所在的層數(shù)(或路徑長度加1)；若查找不成功，則是從根結(jié)點出發(fā)走了一條從根結(jié)點到某葉結(jié)點的左、右指針為止的路徑，因為只有當指針為空時才知道查找失敗。因此，查找成功時，二叉排序樹與給定值比較的關(guān)鍵字個數(shù)不超過二叉排序樹的深度。但是，折半查找長度為n的表其判定樹是唯一的，而含有n個結(jié)點的二叉排序樹卻不唯一。含有n個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。當按關(guān)鍵字有序的次序構(gòu)造一棵二叉排序樹時，所生成的是單支樹，此時樹的深度為n，即其平均查找長度與順序查找相同而變?yōu)?n+1)/2，這是二叉排序樹的最差情況。最好情況是二叉排序樹的形態(tài)與折半查找判定樹相同，即其平均查找長度與lbn成正比。例8.4一棵二叉排序樹如圖8-11所示，求查找成功的ASL和查找失敗的ASL。

【解】查找成功時，是從根結(jié)點出發(fā)走了一條從根結(jié)點到待查結(jié)點的路徑；若查找不成功，則是從根結(jié)點出發(fā)走了一條從根結(jié)點到某葉結(jié)點的路徑，當?shù)竭_葉結(jié)點時，還要繼續(xù)沿葉結(jié)點的左指針或右指針再探查一次。因此，對圖8-11所示的二叉排序樹查找成功的ASL，為樹中各結(jié)點的層數(shù)之和除以樹的結(jié)點個數(shù)n(見圖8-12(a))。而查找失敗時的ASL，為圖8-12(b)中空白結(jié)點(每個空白結(jié)點代表一個空指針)的層數(shù)之和除以空白結(jié)點的個數(shù)m。因此，查找成功的 ；查找失敗的 圖8-11二叉排序樹查找圖8-12查找成功和查找失敗的二叉排序樹示意圖

4.二叉排序樹的刪除操作

在二叉排序樹中，刪除一個結(jié)點要比插入一個結(jié)點困難，因為不能把以該結(jié)點為根的這棵子樹全都刪去，即只能刪除該結(jié)點并仍保持二叉排序樹的特性：按中序遍歷刪除結(jié)點之后的二叉排序樹時，所得到的結(jié)點序列仍然有序。也就是說，刪除二叉排序樹中的一個結(jié)點則相當于刪除有序序列中的一個結(jié)點。

假定待刪結(jié)點由指針q指示，待刪結(jié)點的雙親結(jié)點由指針p指示，則刪除指針q所指向的待刪結(jié)點可分為下面的四種情況。對這四種情況刪除結(jié)點前后二叉排序樹的變化示意圖如圖8-13所示。

(1)若待刪結(jié)點為葉結(jié)點，則可直接刪除，即只需將其雙親結(jié)點指向待刪結(jié)點的指針置為空即可。

(2)若待刪結(jié)點有右子樹但無左子樹，則可用該右子樹的根結(jié)點取代待刪結(jié)點的位置(見圖8-13(a))。這是因為在二叉排序樹中序遍歷的序列中，無左子樹的待刪結(jié)點其直接后繼即為待刪結(jié)點的右子樹根結(jié)點。用待刪結(jié)點右子樹根結(jié)點取代待刪結(jié)點，相當于在該有序序列中，直接刪去了待刪結(jié)點，而序列中的其他結(jié)點排列次序并沒有改變。

(3)若待刪結(jié)點有左子樹但無右子樹，則可用該左子樹的根結(jié)點取代待刪結(jié)點的位置(見圖8-13(b))。這種刪除同樣沒有改變其他結(jié)點在該二叉排序樹中序遍歷中的排列次序。圖8-13在二叉排序樹中刪除結(jié)點*q的不同情況示意圖

(4)若待刪結(jié)點左、右子樹均存在，則需用待刪結(jié)點在二叉排序樹中序遍歷序列中的直接后繼結(jié)點來取代該待刪結(jié)點。這個直接后繼結(jié)點即待刪結(jié)點右子樹中的“最左下結(jié)點”(即右子樹中關(guān)鍵字值最小的結(jié)點，并假定找到的“最左下結(jié)點”由指針r指示)，找到“最左下結(jié)點”后則用其替換待刪結(jié)點(即只是將“最左下結(jié)點”的關(guān)鍵字值賦給待刪結(jié)點，這相當于將“最左下結(jié)點”這一個結(jié)點移到待刪結(jié)點位置)。注意，“最左下結(jié)點”必然沒有左子樹(也可能沒有右子樹)，否則就不是待刪結(jié)點右子樹中關(guān)鍵字值最小的結(jié)點。這時，刪除待刪結(jié)點的操作就轉(zhuǎn)化為刪除這個“最左下結(jié)點”的操作了。如果“最左下結(jié)點”沒有左子樹，則轉(zhuǎn)化為上面的第(2)種情況；如果既沒有左子樹又沒有右子樹(即“最左下結(jié)點”為葉結(jié)點)，則轉(zhuǎn)化為上面的第(1)種情況(見圖8-13(c))。根據(jù)上述情況，在二叉排序樹中刪去待刪結(jié)點*q的算法如下：

voidBSTDelete(BSTree**t,KeyTypek) //在二叉排序樹中刪去結(jié)點

{

BSTree*p,*q,*r;

q=*t;p=*t;

if(q==NULL)

gotoL2;//樹t為空

if(q->lchild==NULL&&q->rchild==NULL&&q->key==k)

{ //樹t中僅有一個待刪結(jié)點*q

q=NULL;gotoL2;

}

while(q!=NULL)//查找待刪結(jié)點*q

if(k==q->key)

gotoL1; //找到待刪結(jié)點*q

else

if(k<q->key)

{p=q;q=q->lchild;}

else

{p=q;q=q->rchild;}

if(q==NULL)gotoL2; //樹中無此待刪結(jié)點*q

L1:if(q->lchild==NULL&&q->rchild==NULL)

//待刪結(jié)點*q為葉結(jié)點，即第(1)種情況

if(p->lchild==q) //刪去待刪結(jié)點*q

p->lchild=NULL;

else

p->rchild=NULL;

else

if(q->lchild==NULL) //待刪結(jié)點*q無左子樹，即第(2)種情況

if(p->lchild==q) //用待刪結(jié)點*q的右子樹根來取代待刪結(jié)點*q

p->lchild=q->rchild;

else

p->rchild=q->rchild;

else

if(q->rchild==NULL) //待刪結(jié)點*q無右子樹，即第(3)種情況

if(p->lchild==q) //用待刪結(jié)點*q的左子樹根來取代待刪結(jié)點*q

p->lchild=q->lchild;

else

p->rchild=q->lchild;

else //待刪結(jié)點*q有左、右子樹，即第(4)種情況

{

r=q->rchild;

if(r->lchild==NULL&&r->rchild==NULL)

{ //待刪結(jié)點*q的右子樹僅有一個根結(jié)點

q->key=r->key; //將右子樹這個根結(jié)點取代待刪結(jié)點*q

q->rchild=NULL;

}

else

{

p=q; //用p指向"最左下結(jié)點"的雙親結(jié)點

while(r->lchild!=NULL) //查找"最左下結(jié)點"

{p=r;r=r->lchild;}

q->key=r->key;

//"最左下結(jié)點"的關(guān)鍵字值送待刪結(jié)點*q的關(guān)鍵字

if(p->lchild==r) //刪去"最左下結(jié)點"

p->lchild=r->rchild;

else

p->rchild=r->rchild;

}

}

L2:;

}8.3.2平衡二叉樹

平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度之差的絕對值不超過1。

圖8-14給出了兩棵二叉排序樹，樹中每個結(jié)點旁邊所標記的數(shù)字是以該結(jié)點為根的二叉樹中左子樹與右子樹的高度之差，該數(shù)字稱為結(jié)點的平衡因子。由平衡二叉樹的定義可知，平衡二叉樹中所有結(jié)點的平衡因子只能取-1、0和1中的一個值。若二叉排序樹中存在著這樣的結(jié)點，其平衡因子的絕對值大于1，則這棵樹就不是平衡二叉樹。如圖8-14(a)所示的二叉排序樹就不是平衡二叉樹。我們知道，二叉排序樹是一棵完全二叉樹或者與折半查找的判定樹相似時，其查找性能最好，而當二叉排序樹蛻化為單支樹時其查找性能最差。因此，二叉排序樹最好是一棵平衡二叉樹。保持二叉排序樹為平衡二叉樹的基本思想是：每當給二叉排序樹插入一個新結(jié)點時，就檢查是否因為這次插入而破壞了平衡；如果破壞了平衡，則找出其中最小的不平衡樹，在保持二叉排序樹有序性的前提下，調(diào)整最小不平衡樹中結(jié)點之間的關(guān)系以達到新的平衡。所謂最小不平衡樹即指距插入結(jié)點最近且其平衡因子的絕對值大于1的結(jié)點作根的這樣一棵子樹。圖8-14二叉排序樹的平衡示意圖假定在二叉排序樹中因插入新結(jié)點而失去平衡的最小子樹其根結(jié)點指針為p，則失去平衡后進行調(diào)整的規(guī)律如下：

(1)?LL型平衡旋轉(zhuǎn)：由于在結(jié)點*p的左孩子的左子樹上插入新結(jié)點，使得結(jié)點*p的平衡因子由1變?yōu)?而失去平衡，因此需進行平衡旋轉(zhuǎn)操作(如圖8-15(a)所示)。

(2)?LR型平衡旋轉(zhuǎn)：由于在結(jié)點*p的右孩子的右子樹上插入新結(jié)點，使得結(jié)點*p的平衡因子由-1變?yōu)?2而失去平衡，因此需進行平衡旋轉(zhuǎn)操作(如圖8-15(b)所示)。

(3)?RR型平衡旋轉(zhuǎn)：由于在結(jié)點*p的左孩子的右子樹上插入新結(jié)點，使得結(jié)點*p的平衡因子由1變?yōu)?而失去平衡，因此需進行平衡旋轉(zhuǎn)操作(如圖8-15(c)所示)。

(4)?RL型平衡旋轉(zhuǎn)：由于在結(jié)點*p的右孩子的左子樹上插入新結(jié)點，使得結(jié)點*p的平衡因子由-1變?yōu)?2而失去平衡，因此需進行平衡旋轉(zhuǎn)操作(如圖8-15(d)所示)。

由圖8-15可知，在四種類型的平衡調(diào)整中，各子樹(如果有的話)AL、AR、BL、BR、CL、CR從左到右的排列順序并沒有發(fā)生變化，只是雙親結(jié)點可能發(fā)生了變化，即可能對結(jié)點A、B、C位置進行了調(diào)整。因此，我們只參考調(diào)整前和調(diào)整后的二叉樹形態(tài)，并以調(diào)整后的二叉樹為標準，由底層開始逐層向上修改相應(yīng)的指針值即可。例如對第二種LR型的平衡調(diào)整：根據(jù)圖8-15(b)，已知指針p指向不平衡樹的根結(jié)點A，增設(shè)兩指針q和r，則平衡調(diào)整如下：

q=p->lchild; //q指向結(jié)點B

r=q->rchild; //r指向結(jié)點C

p->lchild=r->rchild;//結(jié)點A的左指針改為指向結(jié)點C的右子樹CR

q->rchild=r->lchild;//結(jié)點B的右指針改為指向結(jié)點C的左子樹CL

r->lchild=q; //結(jié)點C的左指針改為指向結(jié)點B

r->rchild=p; //結(jié)點C的右指針改為指向結(jié)點A

p=r; //使指針p指向平衡后的根結(jié)點C

由于結(jié)點B的子樹沒有發(fā)生改變，因此無需調(diào)整結(jié)點B的左、右指針值。圖8-15二叉排序樹的四種平衡旋轉(zhuǎn)在不改變二叉樹的鏈式存儲結(jié)構(gòu)情況下，可通過判斷某結(jié)點左、右子樹的深度差值是否為2或-2來得知該子樹是否平衡。在平衡二叉樹中插入一個結(jié)點時即調(diào)用先序遍歷二叉樹非遞歸函數(shù)Preorder，函數(shù)Preorder在遍歷每一個結(jié)點時檢查其左、右子樹的深度差值是否為2或-2，若是則調(diào)用函數(shù)AVL_Revolve進行平衡處理后結(jié)束函數(shù)Preorder的執(zhí)行并返回1值，而只要返回1值則函數(shù)Preorder就繼續(xù)執(zhí)行(即函數(shù)AVL_TreeCreat中的“while(Preorder(t));”語句)遍歷二叉樹的每一個結(jié)點進行平衡處理直至返回0值為止。也即，每調(diào)用一次Preorder，只能對一個不平衡的結(jié)點進行平衡處理，而不能對樹中所有的不平衡的結(jié)點進行平衡處理。這是因為對一個不平衡的結(jié)點進行平衡處理后，其樹的形態(tài)已發(fā)生了變化，即不同于變化前暫存在棧stack中二叉樹的結(jié)點指針順序，所以只能對變化后的二叉樹重新調(diào)用函數(shù)Preorder繼續(xù)遍歷每一個結(jié)點進行平衡處理。生成一棵平衡二叉樹的算法如下：

voidAVL_Revolve(BSTree**p,intk) //對二叉樹進行平衡處理

{

BSTree*q,*r;

switch(k)

{

case1:r=(*p)->lchild;

(*p)->lchild=r->rchild;

r->rchild=*p;

break; //LL型旋轉(zhuǎn)處理

case2:q=(*p)->lchild;

r=q->lchild;

(*p)->lchild=r->rchild;

q->rchild=r->lchild;

r->lchild=q;

r->rchild=*p;

break; //LR型旋轉(zhuǎn)處理

case3:q=(*p)->rchild;

r=q->lchild;

(*p)->rchild=r->lchild;

q->lchild=r->rchild;

r->rchild=q;

r->lchild=*p;

break; //RL型旋轉(zhuǎn)處理

case4:r=(*p)->rchild;

(*p)->rchild=r->lchild;

r->lchild=*p; //RR型旋轉(zhuǎn)處理

}

*p=r; //保存旋轉(zhuǎn)處理后的子樹根結(jié)點指針

}

intPreorder_AVL(BSTree**t)//先序遍歷二叉樹進行平衡處理

{

BSTree*stack[MAXSIZE],*p=*t,*r=p;

inti=0,k,m=0,b=0;

stack[0]=NULL; //棧初始化

while(p!=NULL||i>0) //當指針p不空或棧stack不空(i>0)

if(p!=NULL) //當指針p不空時

{

k=0;

if(Depth(p->lchild)-Depth(p->rchild)==2)//左右子樹深度差值為2時

if(Depth(p->lchild->lchild)>Depth(p->lchild->rchild))

k=1; //LL型

else

k=2; //LR型

if(Depth(p->lchild)-Depth(p->rchild)==-2)//左右子樹深度差值為-2時

if(Depth(p->rchild->lchild)>Depth(p->rchild->rchild))

k=3; //RL型

else

k=4; //RR型

if(k>0) //進行旋轉(zhuǎn)處理

{

if(*t==p)m=1;//待平衡處理的子樹根結(jié)點是平衡二叉樹的根結(jié)點時置m=1

AVL_Revolve(&p,k); //對子樹p進行平衡處理

if(m)*t=p; //m=1應(yīng)將平衡后的子樹根結(jié)點作為平衡二叉樹的根結(jié)點

if(b&&p!=*t)

r->rchild=p; //子樹根結(jié)點不為根結(jié)點時將其作為父結(jié)點的右孩子

if(!b&&p!=*t)

r->lchild=p;//子樹根結(jié)點不為根結(jié)點時將其作為父結(jié)點的左孩子

return1; //有平衡處理

}

stack[++i]=p;//將該結(jié)點壓棧

r=p,b=0; //r指向*p的父結(jié)點，b=0表示*p是*r的左孩子

p=p->lchild;//沿左子樹向下遍歷

}

else //當指針p為空時

{

p=stack[i--]; //將這個無左子樹的結(jié)點由棧中彈出

r=p;b=1; //r指向*p的父結(jié)點，b=1表示*p是*r的右孩子

p=p->rchild; //從該結(jié)點右子樹的根開始繼續(xù)沿左子樹向下遍歷

}

return0; //無平衡處理

}

voidAVL_TreeCreat(BSTree**t,intkey)

{ //平衡二叉樹中插入一個結(jié)點

BSTree*p,*q;

q=*t;

while(q!=NULL)

if(key==q->key)

gotoL1; //查找成功，不插入新結(jié)點

else

if(key<q->key)

{//k小于結(jié)點*q的關(guān)鍵字值則到t的左子樹查找

p=q;

q=q->lchild;

}

else

{//k大于結(jié)點*q的關(guān)鍵字值則到t的右子樹查找

p=q;

q=p->rchild;

}

q=(BSTree*)malloc(sizeof(BSTree));

//查找不成功時創(chuàng)建一個新結(jié)點

q->key=key;

q->lchild=NULL; //因作為葉結(jié)點插入，故左、右指針均為空

q->rchild=NULL;

if(p->key>key)

p->lchild=q; //作為原葉結(jié)點*p的左孩子插入

else

p->rchild=q; //作為原葉結(jié)點*p的右孩子插入

while(Preorder_AVL(t)); //進行平衡處理

L1:;

}

例8.5

已知關(guān)鍵字的輸入序列為：4,5,7,2,1,3,6，試在構(gòu)造二叉排序樹的同時進行平衡調(diào)整，并指出每次調(diào)整的類型，使最終構(gòu)造好的二叉排序樹為一平衡二叉樹。

【解】對題設(shè)關(guān)鍵字序列所構(gòu)造的二叉排序樹及平衡調(diào)整過程如圖8-16所示。圖8-16構(gòu)造二叉排序樹及平衡調(diào)整示意圖由圖8-16可知，二叉排序樹在平衡調(diào)整后仍為一二叉排序樹。

在平衡二叉樹中進行查找，則查找過程中與給定值進行比較的關(guān)鍵字次數(shù)不超過樹的深度。由于平衡二叉樹形態(tài)類同于折半查找判定樹，因此在平衡二叉樹上查找的時間復(fù)雜度為O(lbn)。8.3.3B樹和B+樹

1.?B樹的定義與查找

一棵m階的B樹(也稱B-樹)或者為空樹，或者為滿足下列特性的m叉樹：

(1)樹中每個結(jié)點至多有m棵子樹。

(2)若根結(jié)點不是葉結(jié)點(空樹)，則至少有兩棵子樹。

(3)除根結(jié)點之外的所有非終端結(jié)點(非葉子結(jié)點)至少有棵子樹。

(4)所有非終端結(jié)點均包含以下信息數(shù)據(jù)：(n,p0,k1,p1,k2,…,kn,pn)。其中，ki(i=1,2,…,n)為關(guān)鍵字，且ki＜ki+1；pi(i=0,1,…,n)為指向子樹根結(jié)點的指針，且指針pi所指子樹中所有結(jié)點的關(guān)鍵字均大于ki，但小于ki+1(i=1,2,…,n-1)；pi-1和pi分別稱為ki的左子樹和右子樹，并且p0所指子樹中所有結(jié)點的關(guān)鍵字均小于k1；pn所指子樹中所有結(jié)點的關(guān)鍵字均大于kn(≤n≤m-1)，n為關(guān)鍵字個數(shù)。實際上，結(jié)點中還應(yīng)包含指向雙親結(jié)點的指針和指向關(guān)鍵字對應(yīng)數(shù)據(jù)區(qū)記錄的指針。圖8-174階的B樹示意圖由B樹的定義可知，B樹的查找類似二叉排序樹的查找，區(qū)別在于B樹是m階故查找分支有m條，而不像二叉排序樹只有兩條。由于B樹每個結(jié)點上存放的是多關(guān)鍵字的有序表，即在到達某個結(jié)點時，先在有序表中查找，若找到即查找成功，否則按照對應(yīng)的指針信息到指向的子樹中去查找。當?shù)竭_葉子結(jié)點時則說明沒有對應(yīng)的關(guān)鍵字，即查找失敗。在B樹上的查找過程是一個順指針查找結(jié)點并在結(jié)點中查找關(guān)鍵字這種交替進行的過程。例如，在圖8-17中查找關(guān)鍵字為65的過程是：先在根結(jié)點中順序(或折半)查找，根結(jié)點中只有關(guān)鍵字50且65>50，所以在關(guān)鍵字50的右子樹中順序(或折半)查找；這個右子樹根結(jié)點中有兩個關(guān)鍵字分別為60、70，且60<65<70，因此在關(guān)鍵字60的右子樹中繼續(xù)查找，并在該右子樹根結(jié)點中找到關(guān)鍵字65，即查找成功。

當B樹中沒有所要查找的關(guān)鍵字時，查找方法也類似。例如，在圖8-17中查找關(guān)鍵字20的過程是：因20小于根結(jié)點中關(guān)鍵字50，到50的左子樹中查找；因50的左子樹中只有關(guān)鍵字30且20<30，故再到30的左子樹中查找；因30的左子樹有兩個關(guān)鍵字15和28，且15<20<28，所以繼續(xù)到15的右子樹中查找，而右子樹為空，即查找失敗。

2.?B樹的插入

同生成二叉排序樹類似，我們可以通過逐個插入關(guān)鍵字的方法來生成一棵m階的B樹。但是，在B樹上插入關(guān)鍵字與在二叉排序樹上插入結(jié)點不同，關(guān)鍵字的插入不是在葉結(jié)點而是在B樹最底層的某個非終端結(jié)點上添加這個關(guān)鍵字。添加分為下面兩種情況：

(1)若添加后該結(jié)點上的關(guān)鍵字個數(shù)小于m，則插入結(jié)束。

(2)若添加后該結(jié)點上的關(guān)鍵字個數(shù)等于m，則該結(jié)點的子樹超過了m棵(其子樹為m+1棵)，這與B樹定義不符，所以要對該結(jié)點進行調(diào)整，即進行結(jié)點“分裂”(保證該樹仍是m階的B樹)。結(jié)點“分裂”的方法是：先將關(guān)鍵字添加到結(jié)點中，然后將結(jié)點的關(guān)鍵字分成三個部分，使得前后兩部分的關(guān)鍵字個數(shù)均大于等于，而中間部分只有一個關(guān)鍵字。前后兩部分形成新的結(jié)點，中間部分的這個關(guān)鍵字則插入到雙親結(jié)點中，而插入到雙親結(jié)點的關(guān)鍵字其左、右孩子恰為這兩個新結(jié)點。但是，將關(guān)鍵字插入到雙親結(jié)點的操作有可能使雙親結(jié)點的關(guān)鍵字個數(shù)也達到m個，這就需要按上述結(jié)點“分裂”的方法繼續(xù)“分裂”雙親結(jié)點，直至某個祖先結(jié)點的關(guān)鍵字個數(shù)小于m時為止?？梢?，B樹是由底向上生長的。

例8.6

已知一3階的B樹如圖8-18所示，現(xiàn)要在該B樹中依次插入關(guān)鍵字15、35和95，請說明插入的過程并給出插入過程中B樹變化的示意圖。圖8-183階B樹示意圖

【解】根據(jù)B樹的定義，根結(jié)點中子樹的個數(shù)范圍是2～m，而m=3，即根結(jié)點子樹的個數(shù)范圍為2～3，則關(guān)鍵字個數(shù)的范圍是1～m-1，即1～2；其他非終端結(jié)點中子樹的個數(shù)范圍是～m，即2～3。

(1)插入15。從根結(jié)點開始查找，因15＜50，則沿根結(jié)點的左子樹查找。左子樹根結(jié)點中僅含關(guān)鍵字20且15＜20，即再沿該結(jié)點的左子樹查找。而這個左子樹即為非終端結(jié)點的最底層(圖8-18中已略去葉子結(jié)點一層)，且有關(guān)鍵字10，而15＞10，也即15應(yīng)插入到該結(jié)點第二個關(guān)鍵字位置。插入后仍滿足關(guān)鍵字個數(shù)小于2，即無需對該結(jié)點“分裂”，插入完成(如圖8-19(a)所示)。

(2)插入35。查找插入位置方法同(1)，因30＜35＜40，故將35插入到最底層結(jié)點包含30和40兩關(guān)鍵字的中間位置(如圖8-19(b)所示)。此時該結(jié)點中的關(guān)鍵字個數(shù)為3，不滿足3階的B樹性質(zhì)，故需對該結(jié)點進行“分裂”。分裂過程為：將該結(jié)點分成三個部分，前一部分包含關(guān)鍵字30，中間部分包含關(guān)鍵字35，后一部分包含關(guān)鍵字40；然后將中間部分這個關(guān)鍵字35上移至雙親結(jié)點中，且在關(guān)鍵字35的右邊增加一新指針域。這時，35的左指針指向“分裂”后的前一部分(作為一個結(jié)點)，35的右指針指向“分裂”后的后一部分(作為一個結(jié)點)，由于35插入到雙親結(jié)點后該雙親結(jié)點的關(guān)鍵字個數(shù)為2，即滿足3階B樹的性質(zhì)，故至此插入完成(如圖8-19(c)所示)。

(3)插入95。查找方法同(1)，因80＜90＜95，即將95插入到最底層結(jié)點包含關(guān)鍵字80和90的右邊(因90＜95)位置(如圖8-19(d)所示)。同樣在插入后需對該結(jié)點進行“分裂”，“分裂”過程同(2)，其結(jié)果如圖8-19(e)所示，但這時的雙親結(jié)點中的關(guān)鍵字個數(shù)又超過了2，所以繼續(xù)進行“分裂”，最終得到圖8-19(f)，插入完成。圖8-19在3階B樹中插入關(guān)鍵字時樹的變化示意圖

3.?B樹的刪除

B樹的刪除類似于B樹的插入。若要在B樹上刪除某結(jié)點中的一個指定關(guān)鍵字，則需要先在B樹查找含有此關(guān)鍵字值的結(jié)點。若找到，則刪除該結(jié)點中的這個關(guān)鍵字，否則因找不到關(guān)鍵字而刪除失敗。但是，刪除結(jié)點中的關(guān)鍵字也可能會造成B樹不再滿足其原有性質(zhì)。因此，還需在不滿足B樹原有性質(zhì)時對該樹進行調(diào)整，使其滿足B樹的原有性質(zhì)。這種調(diào)整分為下面四種情況：

(1)若待刪關(guān)鍵字ki所在結(jié)點不在最底層(注：指非終端結(jié)點，下同)，則先找到ki的后繼kj。而kj就是ki的右子樹pi中的最小關(guān)鍵字，然后用kj取代ki，最后在相應(yīng)的結(jié)點(即原來含kj的結(jié)點)刪去這原來的kj及其右指針。根據(jù)B樹的性質(zhì)，kj所在的結(jié)點一定在B樹中的最底層。

(2)若待刪關(guān)鍵字ki所在的結(jié)點在最底層，且該結(jié)點中關(guān)鍵字個數(shù)大于 個，則直接刪去該關(guān)鍵字及其右指針即可。

(3)若待刪關(guān)鍵字ki所在的結(jié)點在最底層，且該結(jié)點中關(guān)鍵字個數(shù)等于個，而其相鄰的左兄弟(或右兄弟)結(jié)點中關(guān)鍵字個數(shù)大于個，則可先在ki所在結(jié)點的雙親結(jié)點中找到ki的前驅(qū)(或后繼)關(guān)鍵字kj，然后用kj取代ki。最后在ki所在結(jié)點的左兄弟(或右兄弟)結(jié)點中找到最大(或最小)關(guān)鍵字kr來取代雙親結(jié)點中的關(guān)鍵字kj。

(4)若待刪關(guān)鍵字ki所在的結(jié)點在最底層，且該結(jié)點及其相鄰兄弟結(jié)點中關(guān)鍵字個數(shù)均等于 個。相鄰結(jié)點以左兄弟為例(右兄弟可據(jù)此推得)，并假設(shè)pi指向該左兄弟結(jié)點。在刪除關(guān)鍵字ki之后，將結(jié)點中剩余關(guān)鍵字、指針及雙親結(jié)點中的ki-1(即ki的前驅(qū)關(guān)鍵字)一起合并到左兄弟結(jié)點中，同時刪去其右指針pi(pi指向ki所在的結(jié)點)。如果因為合并使雙親結(jié)點中的關(guān)鍵字個數(shù)小于，則仍需按上述方法合并雙親結(jié)點，這種合并一直持續(xù)到某個祖先結(jié)點的關(guān)鍵字個數(shù)不小于為止。

例8.7

已知一3階B樹如圖8-20所示，現(xiàn)要在該B樹中依次刪除關(guān)鍵字90、15、92、80和70，請說明刪除的過程并給出刪除過程中B樹變化的示意圖。圖8-203階B樹示意圖

【解】根據(jù)B樹的定義，3階B樹中每個結(jié)點的關(guān)鍵字個數(shù)范圍為：1～m-1，即1到2個。則依次刪除關(guān)鍵字90、15、92、80和70的刪除過程說明如下：

①刪除90。根據(jù)情況(1)，在關(guān)鍵字90右子樹沿左分支找到最底層結(jié)點中的最小關(guān)鍵字92(即90的后繼)，并用92取代90，然后刪除關(guān)鍵字92及其右指針(結(jié)果如圖8-21(a)所示)。

②刪除15。由于關(guān)鍵字15所在的結(jié)點位于B樹的最底層，且該結(jié)點中關(guān)鍵字個數(shù)大于=1個，根據(jù)情況(2)直接刪除關(guān)鍵字15及其右指針(結(jié)果如圖8-21(b)所示)。③刪除92。由于關(guān)鍵字92所在的結(jié)點不在最底層，所以根據(jù)情況(1)，用關(guān)鍵字92所在結(jié)點的右子樹的最左下結(jié)點中的關(guān)鍵字95取代92(并不刪去原關(guān)鍵字95)，這時就轉(zhuǎn)化為刪除最底層結(jié)點中關(guān)鍵字95的問題(如圖8-21(c)所示，虛線框為待刪關(guān)鍵字95所在的結(jié)點)。這恰好是情況(4)，即先刪去原先的95，再將含95結(jié)點中的剩余信息(在此無)及其雙親結(jié)點中的關(guān)鍵字96一起合并到右兄弟結(jié)點(即100所在的結(jié)點)中，右兄弟結(jié)點此時包含關(guān)鍵字96和100，而雙親結(jié)點中的關(guān)鍵字為空，即此次合并雙親結(jié)點中關(guān)鍵字個數(shù)小于個，故仍需繼續(xù)對雙親結(jié)點(虛線框結(jié)點，其關(guān)鍵字96已不存在)進行合并(如圖8-21(d)所示)。根據(jù)情況(4)，將虛線框96所在結(jié)點的剩余信息(在此無)及其雙親結(jié)點中的關(guān)鍵字95一起合并到左兄弟結(jié)點(即關(guān)鍵字70所在的結(jié)點)中，左兄弟結(jié)點此時包含關(guān)鍵字70和95，而雙親結(jié)點中的關(guān)鍵字為50，即此次合并雙親結(jié)點中的關(guān)鍵字不小于個，因此合并結(jié)束(結(jié)果如圖8-21(e)所示)。④刪除80。根據(jù)情況(3)，待刪結(jié)點正好有1個關(guān)鍵字，而其右兄弟結(jié)點中有2個關(guān)鍵字(96,100)，則先用70取代80，然后再用96取代70放入雙親結(jié)點中關(guān)鍵字95的右面(結(jié)果如圖8-21(f)所示)。⑤刪除70。根據(jù)情況(4)，先將70刪除，再將70中剩余信息(在此無)及其雙親結(jié)點中關(guān)鍵字95一起合并到左兄弟結(jié)點中，左兄弟結(jié)點中此時包含關(guān)鍵字60和95，而雙親結(jié)點中只剩下關(guān)鍵字96，滿足B樹要求(結(jié)果如圖8-21(g)所示)。

由于查找是B樹的最基本操作，因此我們僅分析B樹的查找性能。B樹的查找由兩個基本操作構(gòu)成，即在B樹上尋找關(guān)鍵字所在的結(jié)點以及在結(jié)點中尋找關(guān)鍵字。由于B樹主要用于外存文件中數(shù)據(jù)的查找，因此B樹存儲在外存設(shè)備上。整個查找過程就是先從外存設(shè)備上讀取B樹的結(jié)點數(shù)據(jù)，然后再對結(jié)點中的關(guān)鍵字進行順序或折半查找。因此，整個查找時間是由查找外存中B樹的結(jié)點信息以及在內(nèi)存中查找該結(jié)點的關(guān)鍵字信息這兩部分組成。顯然，在外存設(shè)備(如磁盤)上查找B樹結(jié)點信息花費的時間代價要大得多(外存上訪問數(shù)據(jù)的時間要遠遠多于內(nèi)存訪問數(shù)據(jù)的時間)。故此，我們重點討論在B樹中查找結(jié)點的問題。圖8-21在3階B樹中刪除關(guān)鍵字時B樹的變化示意圖由B樹的性質(zhì)可知，查找結(jié)點的次數(shù)不會超過B樹的深度。我們討論在最壞情況下B樹的深度，根據(jù)B樹的定義可知：第一層至少有1個結(jié)點，第二層至少有2個結(jié)點，由于除根結(jié)點外的每個非終端結(jié)點至少有棵子樹，則第三層至少有個結(jié)點，第四層至少有個結(jié)點……，第h層至少有個結(jié)點。假定深度為h的B樹有n個關(guān)鍵字，葉子結(jié)點數(shù)為n+1個，并且在h+1層上，則依照上述推理得出：即也即，在具有n個關(guān)鍵字的B樹上查找，所查結(jié)點次數(shù)不超過 。

4.?B+樹簡介

B+樹是根據(jù)文件系統(tǒng)的需要而產(chǎn)生的一種B樹的變形樹，它借助了分塊查找的思想，使得查找更加方便。一棵m階B+樹和m階的B樹其區(qū)別主要有：

(1)有n棵子樹的結(jié)點中含有n個關(guān)鍵字。

(2)所有葉子結(jié)點中包含了全部關(guān)鍵字的信息以及指向含有這些關(guān)鍵字記錄的指針，并且葉子結(jié)點本身是按關(guān)鍵字大小由小到大順序鏈接。

(3)所有非終端結(jié)點可看作是一個索引表，索引表中每個關(guān)鍵字對應(yīng)于子樹中最大(或最小)的關(guān)鍵字值。

(4)葉子結(jié)點中還有兩類指針：一類指針與各關(guān)鍵字相對應(yīng)，它指向該結(jié)點在外存主文件中的物理位置；另一類指針將各葉子結(jié)點鏈接起來形成一個雙向鏈表。

圖8-22給出了一棵3階B+?樹的示意圖，其中，root指向根結(jié)點，sq_h指向關(guān)鍵字值最小的葉結(jié)點，sq_t指向關(guān)鍵字值最大的葉結(jié)點，葉結(jié)點之間采用雙向鏈表連接。為方便起見，圖中葉子結(jié)點的內(nèi)部指針以“^”示意。因此，對B+?樹可以有兩種查找方法：一種是由根結(jié)點開始，即類似于B樹的查找方法；另一種是使用指針sq_h(或者sq_t)從最小(最大)關(guān)鍵字開始順序查找。圖8-223階B+樹示意圖在B+樹中進行隨機查找、插入和刪除的過程基本上與B樹類似。只是在查找中，若非終端結(jié)點中的關(guān)鍵字等于給定值時，查找過程并不終止而是繼續(xù)查找至葉結(jié)點，直到在葉結(jié)點中找到關(guān)鍵字時為止(如同分塊查找一樣，即使給定值與索引表中保存的最大關(guān)鍵字值相等也還要到對應(yīng)塊中順序查找)。因此，在B+樹上的查找無論成功與否都走了一條從根結(jié)點到葉子結(jié)點的路徑，并且還要在葉結(jié)點上進行順序查找。在B+樹中插入關(guān)鍵字只能在葉結(jié)點上進行，當結(jié)點中的關(guān)鍵字個數(shù)大于m時就要“分裂”成兩個結(jié)點，這兩個結(jié)點所含關(guān)鍵字的個數(shù)均為 ，并同時修改它們雙親結(jié)點中的關(guān)鍵字，使該雙親結(jié)點添加包含這兩個結(jié)點中的最大關(guān)鍵字。此外，還要修改鏈接指針，使葉結(jié)點之間仍然構(gòu)成一個雙向鏈表。同理，在B+?樹中刪除一個關(guān)鍵字也是在葉結(jié)點上進行，當葉結(jié)點中的最大關(guān)鍵字被刪除時，其雙親結(jié)點中的值仍可作為一個“分界關(guān)鍵字”存在。如果因刪除而使得結(jié)點中的關(guān)鍵字個數(shù)少于時，就要像B樹一樣進行兄弟結(jié)點合并。刪除過程中也要保持葉結(jié)點之間的雙向鏈表關(guān)系。8.4地址映射方式下的動態(tài)查找表—哈希表

8.4.1哈希表與哈希方法

哈希表查找方法的基本思想是:在記錄的關(guān)鍵字(記為key)和記錄的存儲位置(記為address)之間找出關(guān)系函數(shù)f，使得每個關(guān)鍵字能夠被映射到一個存儲位置上，即address=f(key)。當存儲一個記錄時，按照記錄的關(guān)鍵字key通過函數(shù)f計算出它的存儲位置address，并將該記錄存入這個位置。這樣，當查找這個記錄時，我們就可根據(jù)給定值key以及函數(shù)f，通過f(key)計算求得該記錄的存儲位置，即可直接由該存儲位置訪問這個記錄了。這種方法避免了查找中需進行大量的關(guān)鍵字比較操作，因此查找效率要比前面介紹的各種查找方法都高。

上述方法中，函數(shù)f被稱為哈希函數(shù)或散列函數(shù)，通常記為Hash(key)，由哈希函數(shù)及關(guān)鍵字值計算出來的哈希函數(shù)值(即存儲地址)稱為哈希地址，通過構(gòu)造哈希函數(shù)的過程得到一張關(guān)鍵字與哈希地址之間的關(guān)系表稱為哈希表或散列表。因此，哈希表可以用一維數(shù)組實現(xiàn)。數(shù)組元素用于存儲包含關(guān)鍵字的記錄。數(shù)組元素的下標就是該記錄的哈希地址，當需要查找某關(guān)鍵字時，只要它在哈希表中就可以通過哈希函數(shù)確定它在表中(數(shù)組中)的存儲位置。

例如，有一個由整數(shù)組成的關(guān)鍵字集合序列：{27