數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第8章 查找

第8章查找人們?cè)谌粘Ｉ钪薪?jīng)常需要查找某個(gè)人或某個(gè)單位的電話號(hào)碼，要求實(shí)現(xiàn)一個(gè)簡單的通訊錄查詢系統(tǒng)，根據(jù)用戶輸入的信息（例如姓名）進(jìn)行快速查詢。計(jì)算機(jī)的出現(xiàn)使信息查詢更加快捷、方便、準(zhǔn)確。導(dǎo)學(xué)問題：8.1知識(shí)學(xué)習(xí)——查找的基本概念

查找的術(shù)語查找表。由具有同一類型的數(shù)據(jù)元素（或記錄）組成的集合。關(guān)鍵字。是記錄中某個(gè)項(xiàng)或組合項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)記錄。能唯一確定一個(gè)記錄的關(guān)鍵字，稱為主關(guān)鍵字；而不能唯一確定一個(gè)記錄的關(guān)鍵字，稱為次關(guān)鍵字。查找。是指按給定的某個(gè)值k，在查找表中查找關(guān)鍵字為給定值k的記錄。

8.1知識(shí)學(xué)習(xí)——查找的基本概念

查找算法的性能查找算法時(shí)間性能通過關(guān)鍵碼的比較次數(shù)來度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？⑴算法；⑵問題規(guī)模；⑶待查關(guān)鍵碼在查找集合中的位置；⑷查找頻率。查找頻率與算法無關(guān)，取決于具體應(yīng)用。8.1知識(shí)學(xué)習(xí)——查找的基本概念

查找算法的性能平均查找長度：查找算法進(jìn)行的關(guān)鍵碼的比較次數(shù)的數(shù)學(xué)期望值。計(jì)算公式為：其中：n：問題規(guī)模，查找集合中的記錄個(gè)數(shù)；

pi：查找第i個(gè)記錄的概率；ci：查找第i個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)。結(jié)論：ci取決于算法；pi與算法無關(guān)，取決于具體應(yīng)用。如果pi是已知的，則平均查找長度只是問題規(guī)模的函數(shù)。ASL?==niiicp18.1知識(shí)學(xué)習(xí)——查找的基本概念

查找技術(shù)靜態(tài)查找

：不涉及插入和刪除操作的查找。靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對(duì)其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作；動(dòng)態(tài)查找：涉及插入和刪除操作的查找。動(dòng)態(tài)查找適用于：查找與插入和刪除操作在同一個(gè)階段進(jìn)行，例如當(dāng)查找成功時(shí)，要?jiǎng)h除查找到的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。8.1知識(shí)學(xué)習(xí)8.1.2順序表查找1）順序查找

基本思想：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。intSeqSearch(intr[],intn,intk){ inti=0; while(i<n&&r[i]!=k)

i++; if(i<n)returni; elsereturn-1;}基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。101524612354098550123456789i例：查找k＝35iii哨兵35查找方向改進(jìn)的順序查找

intSeqSearch2(intr[],intn,intk){ inti=0;

r[n]=k;

while(r[i]!=k) i++; if(i<n)returni; elsereturn-1;}

ASL==?=niicp1?+-=niiinp1)1(i=(n+1)/2=O(n)改進(jìn)的順序查找順序查找的缺點(diǎn)：平均查找長度較大，特別是當(dāng)待查找集合中元素較多時(shí)，查找效率較低。順序查找的優(yōu)點(diǎn)：算法簡單而且使用面廣。對(duì)表中記錄的存儲(chǔ)沒有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可；對(duì)表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。8.1.2順序表查找2）折半查找使用條件：線性表中的記錄必須按關(guān)鍵碼有序；必須采用順序存儲(chǔ)?；舅枷耄涸谟行虮碇?，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。例：查找值為23的過程low=0high=13mid=6

high=5mid=2

32>2319<2301234567891011125131921232932353742464956low=0low=3high=5mid=4

23=23例：查找值為23的過程low=0high=13mid=6

high=5mid=2

32>2219<2201234567891011125131921232932353742464956low=0low=3high=5mid=4

mid=3

23>22low=3high=321<22low=4high=3Low>highintBiSearch(intr[],intn,intk){

intlow=0,high=n-1,mid; while(low<=high) { mid=(low+high)/2; if(r[mid]==k)returnmid; elseif(r[mid]<k)low=mid+1; elsehigh=mid-1; } return-1;}

折半查找——非遞歸

intBiSearch2(intr[],intlow,inthigh,intk){ intmid;if(low>high) return-1; else { mid=(low+high)/2; if(r[mid]==k) returnmid; else if(r[mid]<k) returnBiSearch2(r,mid+1,high,k); else returnBiSearch2(r,low,mid-1,k); }}

折半查找——遞歸

折半查找的判定樹判定樹：折半查找的過程可以用二叉樹來描述，樹中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)記錄，結(jié)點(diǎn)的值為該記錄在表中的位置。通常稱這個(gè)描述折半查找過程的二叉樹為折半查找判定樹，簡稱二叉判定樹。折半查找的判定樹判定樹的構(gòu)造方法⑴當(dāng)n=0時(shí)，折半查找判定樹為空；⑵當(dāng)n＞0時(shí)，折半查找判定樹的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹是與有序表r[1]~r[mid-1]相對(duì)應(yīng)的折半查找判定樹，根結(jié)點(diǎn)的右子樹是與r[mid+1]~r[n]相對(duì)應(yīng)的折半查找判定樹。－11－22－33－44－510－1111－9－108－97－85－66－7內(nèi)部結(jié)點(diǎn)外部結(jié)點(diǎn)3691011784512折半查找的判定樹具有n個(gè)結(jié)點(diǎn)的折半查找判定樹的深度為查找成功：在表中查找任一記錄的過程，即是折半查找判定樹中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹中的層數(shù)。查找不成功：查找失敗的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。。??1log2+n折半查找的性能分析設(shè)有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對(duì)其進(jìn)行折半搜索時(shí)的二叉判定樹,并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。練習(xí)設(shè)有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對(duì)其進(jìn)行折半搜索時(shí)的二叉判定樹,并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。練習(xí)8.1.2順序表查找如何提高大數(shù)據(jù)表的查找效率是一個(gè)重要的研究內(nèi)容。對(duì)于擁有大量數(shù)據(jù)甚至海量數(shù)據(jù)的數(shù)據(jù)表，采用順序查找的效率很難適應(yīng)實(shí)際需求，即使采用折半查找，時(shí)間復(fù)雜度仍然達(dá)到O(log2n)，而且還要求數(shù)據(jù)表有序。8.1.2順序表查找想一想我們是如何在厚重的英語或漢語詞典中查找一個(gè)單詞的。我們通常是根據(jù)待查單詞的首字母，利用詞典邊緣的索引（26個(gè)英文字母），快速定位到單詞所在的區(qū)間，然后在這個(gè)較小的區(qū)間中再逐步查找的。8.1.2順序表查找3）分塊查找生活中這種利用索引查找單詞的方法可以運(yùn)用于數(shù)據(jù)表的查找，稱之為分塊查找，或稱為分塊索引查找，該方法適用于對(duì)關(guān)鍵字分塊有序的查找表進(jìn)行查找操作。8.1.2順序表查找所謂分塊有序是指查找表可按關(guān)鍵字大小分成若干子表（或稱塊），且前一塊中的最大關(guān)鍵字小于后一塊中的最小關(guān)鍵字，但是各塊內(nèi)部的關(guān)鍵字不一定有序。分塊查找需對(duì)子表建立索引表，查找表的每一個(gè)子表由索引表中的索引項(xiàng)確定。索引項(xiàng)包括兩個(gè)字段：關(guān)鍵字字段（存放對(duì)應(yīng)子表中的最大關(guān)鍵字值）和指針字段（存放子表的起始序號(hào)）。8.1.2順序表查找分塊查找過程分兩步進(jìn)行：①確定要查找的記錄所在的子表。用給定值k在索引表中查找索引項(xiàng)，以確定要查找的記錄位于哪個(gè)子表中。②確定要查找的記錄的情況。對(duì)第①步確定的子表進(jìn)行順序查找，以確定要查找的記錄的情況。8.1.2順序表查找查找38的過程在索引表順序查找在子表順序查找索引表通常有序，可以折半查找分塊查找的效率介于順序查找和折半查找之間分塊查找的進(jìn)一步討論：進(jìn)一步地，再想一想翻閱字典時(shí)的情形。在利用詞典邊緣的字母索引來確定單詞的起始查找位置時(shí)，我們一般不會(huì)嚴(yán)格按照折半查找的方式來確定，而是這樣一個(gè)過程：如果所要查找的單詞按照字母次序比已經(jīng)翻開的頁面上的字大很多，就多翻幾頁來看下一個(gè)頁面；否則就往前多翻幾頁來查看?？梢园堰@種方法描述成這樣的計(jì)算機(jī)算法：當(dāng)知道關(guān)鍵字k位于kl和kh之間時(shí)，下一次探測的位置可以選在

（k-kl）/（kh-kl）這個(gè)點(diǎn)上。這個(gè)算法在關(guān)鍵字以基本均勻的速度增加的情況下，可以比折半查找更快地接近要查找的位置。折半查找中的每一步把查找工作量從n降到n/2，該查找方法則可以把查找工作量從n降到

。8.1.3樹表查找1）二叉排序樹二叉排序樹（也稱二叉查找樹）：或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：⑴若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；⑵若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；⑶它的左右子樹也都是二叉排序樹。二叉排序樹的定義采用的是遞歸方法。二叉排序樹非二叉排序樹6390554258104567837063605582581045678370中序遍歷二叉排序樹可以得到一個(gè)按關(guān)鍵碼有序的序列二叉排序樹設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,37,70,29},試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。

練習(xí)二叉排序樹的存儲(chǔ)結(jié)構(gòu)假設(shè)二叉排序樹中結(jié)點(diǎn)的數(shù)據(jù)域只含一個(gè)整型數(shù)據(jù)，類型定義如下：typedefstructBiNode{ intkey; structBiNode*lchild,*rchild;}*BiSortTree;二叉排序樹的插入在一棵二叉排序樹中插入值為k的結(jié)點(diǎn)，步驟如下：①若二叉排序樹為空，則生成值為k的新結(jié)點(diǎn)，同時(shí)將新結(jié)點(diǎn)s作為根結(jié)點(diǎn)插入。②若k小于根結(jié)點(diǎn)的值，則在根的左子樹中插入值為k的結(jié)點(diǎn)。③若k大于根結(jié)點(diǎn)的值，則在根的右子樹中插入值為k的結(jié)點(diǎn)。④若k等于根結(jié)點(diǎn)的值，表明二叉排序樹中已有此關(guān)鍵字，則無須插入。從以上描述可知，插入過程是遞歸的。例：插入值為98的結(jié)點(diǎn)6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧voidInsert(BiSortTree&T,intk){ if(T==NULL) { T=newBiNode; T->key=k; T->lchild=T->rchild=NULL; } elseif(k<T->key) Insert(T->lchild,k); else Insert(T->rchild,k);}二叉排序樹的插入算法二叉排序樹的構(gòu)造從空的二叉排序樹開始，依次插入一個(gè)個(gè)結(jié)點(diǎn)。例：關(guān)鍵碼集合為{63，90，70，55，58}，二叉排序樹的構(gòu)造過程為：

6355905870voidCreateBiSortTree(BiSortTree&T,inta[],intn){ inti; for(i=0;i<n;i++) Insert(T,a[i]);}

二叉排序樹的建立算法在二叉排序樹中查找給定值k的過程是：①若二叉排序樹為空，則表明查找失敗，返回空指針；否則，若給定值k等于根結(jié)點(diǎn)的值，則表明查找成功，返回根結(jié)點(diǎn)；②若給定值k小于根結(jié)點(diǎn)的值，則繼續(xù)在根的左子樹中查找；③若給定值k大于根結(jié)點(diǎn)的值，則繼續(xù)在根的右子樹中查找。這是一個(gè)遞歸查找過程。二叉排序樹的查找例：在二叉排序樹中查找關(guān)鍵字值為35，95的過程：50302080908588403532二叉排序樹的查找50302080908588403532BiSortTreeBST_Search(BiSortTreeT,intk){ if(T==NULL) returnNULL; elseif(k==T->key) returnT; elseif(k<T->key) returnBST_Search(T->lchild,k); else returnBST_Search(T->rchild,k);}二叉排序樹的查找二叉排序樹的查找性能分析由序列{3,1,2,5,4}得到二叉排序樹：由序列{1,2,3,4,5}得到二叉排序樹：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2二叉排序樹的查找性能取決于二叉排序樹的形狀，在O(log2n)和O(n)之間。

1234531254二叉排序樹的刪除在二叉排序樹上刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結(jié)點(diǎn)是葉子；被刪除的結(jié)點(diǎn)是單支結(jié)點(diǎn)（只有左子樹或者只有右子樹）；被刪除的結(jié)點(diǎn)是雙支結(jié)點(diǎn)（既有左子樹，也有右子樹）。情況1——被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)50302080908588403532503020809085403532操作：將雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為空。情況2——被刪除的結(jié)點(diǎn)是單支結(jié)點(diǎn)操作：將雙親結(jié)點(diǎn)的相應(yīng)指針域的值指向被刪除結(jié)點(diǎn)的左子樹（或右子樹）。50302080908588403532503020908588403532情況3——被刪除的結(jié)點(diǎn)是雙支結(jié)點(diǎn)操作：以其前驅(qū)（左子樹中的最大值）替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)。5030208090858840353240302080908588353240刪除二叉排序樹的刪除算法（遞歸）①若二叉排序樹為空，則表明不存在刪除的結(jié)點(diǎn)，不進(jìn)行刪除操作。②若給定值k小于根結(jié)點(diǎn)的值，則繼續(xù)在根的左子樹中刪除。③若給定值k大于根結(jié)點(diǎn)的值，則繼續(xù)在根的右子樹中刪除。④若給定值k等于根結(jié)點(diǎn)的值，則根結(jié)點(diǎn)即為要?jiǎng)h除的結(jié)點(diǎn)，此時(shí)需要根據(jù)上述分析的三種結(jié)點(diǎn)情況：葉子結(jié)點(diǎn)、單支結(jié)點(diǎn)或雙支結(jié)點(diǎn)，執(zhí)行相應(yīng)的刪除操作。平衡二叉樹平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：⑴根結(jié)點(diǎn)的左子樹和右子樹的深度最多相差1;⑵根結(jié)點(diǎn)的左子樹和右子樹也都是平衡二叉樹。平衡因子：結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)的左子樹的深度與右子樹的深度之差。548254821是平衡樹非平衡樹在平衡樹中，結(jié)點(diǎn)的平衡因子可以是1，0，-1。結(jié)點(diǎn)的平衡因子＝HL-HR平衡二叉樹基本思想：在構(gòu)造二叉排序樹的過程中，每插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性，若是，在保持二叉排序樹特性的前提下，調(diào)整各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。平衡二叉樹的構(gòu)造平衡二叉樹的構(gòu)造設(shè)結(jié)點(diǎn)A為最小不平衡子樹的根結(jié)點(diǎn)，對(duì)該子樹進(jìn)行平衡調(diào)整歸納起來有以下四種情況：1.LL型2.RR型3.LR型4.RL型練習(xí)：設(shè)有關(guān)鍵碼序列{4，5，7，2，1，3，6}，構(gòu)造平衡二叉樹練習(xí)：設(shè)有關(guān)鍵碼序列{4，5，7，2，1，3，6}，構(gòu)造平衡二叉樹練習(xí)：設(shè)有關(guān)鍵碼序列{4，5，7，2，1，3，6}，構(gòu)造平衡二叉樹B樹B樹的B即Balanced，平衡的意思。從字面意思可知B樹是平衡二叉樹的延伸。B樹屬于動(dòng)態(tài)的多級(jí)索引，是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。B樹定義：一棵m階的B樹，或者為空樹，或?yàn)闈M足下列特性的m叉樹：（1）樹中葉子結(jié)點(diǎn)的說明：所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，并且不帶信息，這些結(jié)點(diǎn)可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)因?yàn)槿~子結(jié)點(diǎn)實(shí)際不存在，所以葉子結(jié)點(diǎn)可以不畫出，后續(xù)的圖例中不再出現(xiàn)葉子結(jié)點(diǎn)。B樹（2）樹中關(guān)鍵字的要求：根結(jié)點(diǎn)中至少有一個(gè)關(guān)鍵字，最多有m-1個(gè)關(guān)鍵字；非根非葉子結(jié)點(diǎn)中包含

m/2

1~m

1個(gè)關(guān)鍵字，且這些關(guān)鍵字升序存放；非葉子結(jié)點(diǎn)存儲(chǔ)的關(guān)鍵字對(duì)存儲(chǔ)在其各個(gè)子樹中的關(guān)鍵字范圍進(jìn)行分割；所有關(guān)鍵字在整棵樹中出現(xiàn)且僅出現(xiàn)一次。該5階B樹中，根結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)最少為1，最多為m

1=4每個(gè)非根非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)最少為

m/2

1=

5/2

1=2，最多為m

1=4B樹（3）樹中子樹的要求：每個(gè)非葉子結(jié)點(diǎn)有比其包含的關(guān)鍵字個(gè)數(shù)多一個(gè)的指向孩子的指針，葉子結(jié)點(diǎn)沒有孩子指針；每個(gè)結(jié)點(diǎn)至多有m棵子樹；根結(jié)點(diǎn)至少有兩棵子樹；非根非葉子結(jié)點(diǎn)至少有

m/2

棵子樹。該5階B樹中，根結(jié)點(diǎn)的子樹個(gè)數(shù)最少為2，最多為m=5每個(gè)非根非葉子結(jié)點(diǎn)的子樹個(gè)數(shù)最少為3，最多為5B樹B樹的查找：B樹的查找類似二叉排序樹的查找，不同之處在于B樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵字的有序表。在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在該結(jié)點(diǎn)的有序表中查找。若找到，則查找成功；否則，再到對(duì)應(yīng)的指針指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對(duì)應(yīng)的關(guān)鍵字，查找失敗。即B樹上的查找過程是由兩個(gè)基本操作交叉進(jìn)行的過程：①在B樹上找結(jié)點(diǎn)；②在結(jié)點(diǎn)中找關(guān)鍵字。B樹例如，在圖中查找關(guān)鍵字值為93的元素。首先，從r指向的根結(jié)點(diǎn)a開始，結(jié)點(diǎn)a中只有一個(gè)關(guān)鍵字，且93大于它因此，按a結(jié)點(diǎn)第2個(gè)指針到結(jié)點(diǎn)c去查找，結(jié)點(diǎn)c有兩個(gè)關(guān)鍵字，而93也都大于它們應(yīng)按c結(jié)點(diǎn)第3個(gè)指針到結(jié)點(diǎn)i去查找，在結(jié)點(diǎn)i中順序比較關(guān)鍵字，找到關(guān)鍵字93。B樹由于B樹通常是存儲(chǔ)在外存上的，因此上述查找過程中的操作①就是通過指針在磁盤相對(duì)定位，將結(jié)點(diǎn)信息讀入內(nèi)存，之后再對(duì)結(jié)點(diǎn)中的關(guān)鍵字有序表進(jìn)行順序查找或折半查找。因?yàn)樵诖疟P上讀取結(jié)點(diǎn)信息比在內(nèi)存中進(jìn)行關(guān)鍵字查找耗時(shí)多，所以在磁盤上讀取結(jié)點(diǎn)信息的次數(shù)，即B樹的高度是決定B樹查找效率的首要因素。在含有n個(gè)關(guān)鍵字的B樹上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過

B樹B樹的插入和刪除操作（1）插入操作同二叉排序樹一樣，關(guān)鍵字的插入次序不同，將可能生成不同結(jié)構(gòu)的B樹。在B樹上插入關(guān)鍵字與在二叉排序樹上插入結(jié)點(diǎn)不同，關(guān)鍵字的插入不是在葉結(jié)點(diǎn)上進(jìn)行，而是在最低層的某個(gè)結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字。若該結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)不超過m

1個(gè)，則可直接插入到該結(jié)點(diǎn)上；否則，該結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)達(dá)到m個(gè)，使該結(jié)點(diǎn)的子樹超過了m棵，這與B樹定義不符，所以要調(diào)整，即進(jìn)行結(jié)點(diǎn)的分裂。B樹（1）插入操作分裂的方法是：關(guān)鍵字加入結(jié)點(diǎn)后，將結(jié)點(diǎn)中的關(guān)鍵字分成三部分，使得前后兩部分關(guān)鍵字個(gè)數(shù)均大于等于

m/2

1，而中間部分只有一個(gè)結(jié)點(diǎn)。前后兩部分成為兩個(gè)結(jié)點(diǎn)，中間的一個(gè)結(jié)點(diǎn)插入到父結(jié)點(diǎn)中。若插入父結(jié)點(diǎn)而使父結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)超過m

1，則父結(jié)點(diǎn)繼續(xù)分裂，直到插入某個(gè)父結(jié)點(diǎn)后，其關(guān)鍵字個(gè)數(shù)小于m。可見，B樹是從底向上生長的。B樹例

在一棵3階B樹上依次插入關(guān)鍵字65、24、50和38

B樹（2）刪除操作1）刪除底層結(jié)點(diǎn)中的關(guān)鍵字。這里又分3種情形處理①若結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于

m/2

1，直接刪去。②若余項(xiàng)與右兄弟（無右兄弟，則找左兄弟）項(xiàng)數(shù)之和大于等于2(

m/2

1)就與它們父結(jié)點(diǎn)中的有關(guān)項(xiàng)一起重新分配。③若刪除后，余項(xiàng)與右兄弟或左兄弟關(guān)鍵字個(gè)數(shù)之和均小于2(

m/2

1)，就將余項(xiàng)與右兄弟或左兄弟合并。由于兩個(gè)結(jié)點(diǎn)合并后，父結(jié)點(diǎn)中相關(guān)項(xiàng)不能滿足B樹要求，則繼續(xù)調(diào)整，直到根結(jié)點(diǎn)。B樹例在如圖所示的5階B樹中分別刪除76和7B樹（2）刪除操作2）刪除非底層結(jié)點(diǎn)中的關(guān)鍵字。若刪除非底層結(jié)點(diǎn)中的關(guān)鍵字K，則以該關(guān)鍵字相關(guān)聯(lián)指針?biāo)缸訕渲械淖钚￡P(guān)鍵字X與K交換，問題轉(zhuǎn)換為在下一層結(jié)點(diǎn)中再刪除關(guān)鍵字K，直到這個(gè)K在最底層結(jié)點(diǎn)上，即轉(zhuǎn)為情形1）。B樹例在如圖所示的5階B樹中刪除26B+樹B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B樹的變形樹。一棵m階的B+樹和m階的B樹的差異在于：（1）在B樹中，每個(gè)結(jié)點(diǎn)含n個(gè)關(guān)鍵字，n+1棵子樹；

在B+樹中，每個(gè)結(jié)點(diǎn)含n個(gè)關(guān)鍵字，n棵子樹。（2）在B樹中，每個(gè)結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n的取值范圍

m/2

1≤n≤m

1（除根）結(jié)點(diǎn)外。

在B+樹中，每個(gè)結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n的取值范圍

m/2

≤n≤m（除根結(jié)點(diǎn)外），1≤n≤m（根結(jié)點(diǎn)）。（3）B+樹中所有底層結(jié)點(diǎn)包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，且所有底層結(jié)點(diǎn)按關(guān)鍵字由小到大順序依次鏈接。（4）B+樹中所有非底層結(jié)點(diǎn)僅起索引作用，結(jié)點(diǎn)中僅含有其子樹中的最大（或最?。╆P(guān)鍵字。B+樹在B+樹上進(jìn)行隨機(jī)查找、插入和刪除的過程基本上與B樹類似。不同之處在于在查找時(shí)，若非底層結(jié)點(diǎn)上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)向下直到底層結(jié)點(diǎn)。因此，在B+樹中，不論查找成功與否，每次查找都是走了一條從根到底層結(jié)點(diǎn)的路徑。B+樹查找效率的分析類似于B樹。B+樹B+樹的插入僅在底層結(jié)點(diǎn)上進(jìn)行，當(dāng)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于m時(shí)要分裂成兩個(gè)結(jié)點(diǎn)，他們所含關(guān)鍵字的個(gè)數(shù)均為

(m+1)/2

。并且，他們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)中的最大關(guān)鍵字。B+樹的刪除也僅在底層結(jié)點(diǎn)進(jìn)行，當(dāng)?shù)讓咏Y(jié)點(diǎn)中的最大關(guān)鍵字被刪除時(shí)，其在非底層結(jié)點(diǎn)中的值可以作為一個(gè)分界關(guān)鍵字存在。若因刪除而使結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)少于

m/2

時(shí)，其和兄弟結(jié)點(diǎn)的合并過程亦和B樹類似。B+樹例在如圖所示的3階B+樹中依次插入關(guān)鍵字16、17、198.2知識(shí)應(yīng)用為了實(shí)現(xiàn)對(duì)電話號(hào)碼的快速查詢，可以將通訊錄存儲(chǔ)到元素類型為結(jié)構(gòu)體的順序表中，然后按姓名排序，以便應(yīng)用折半查找，但是排序代價(jià)較高。且通訊錄是動(dòng)態(tài)的，會(huì)經(jīng)常進(jìn)行插入和刪除操作，因此可考慮采用二叉排序樹的結(jié)構(gòu)存儲(chǔ)通訊錄信息，則查找和維護(hù)都能獲得較高的時(shí)間性能。8.3知識(shí)拓展以上討論的查找方法，由于記錄的存儲(chǔ)位置與關(guān)鍵字之間不存在確定的關(guān)系，因此，查找時(shí)需要進(jìn)行一系列對(duì)關(guān)鍵字的查找比較，即“查找算法”是建立在比較的基礎(chǔ)上的，查找效率由比較一次縮小的查找范圍決定。以上介紹的算法是否對(duì)任何情況都適合呢？處理在海量數(shù)據(jù)中查找時(shí)，能否表現(xiàn)出較好的性能？能否不用比較，通過關(guān)鍵碼直接確定存儲(chǔ)位置？理想的情況是，依據(jù)關(guān)鍵字直接得到其對(duì)應(yīng)的記錄位置，即要求關(guān)鍵字與記錄位置間存在一一對(duì)應(yīng)關(guān)系，通過這個(gè)關(guān)系，能很快地由關(guān)鍵字得到對(duì)應(yīng)的記錄位置。

Hash查找查找操作要完成什么任務(wù)？我們學(xué)過哪些查找技術(shù)？這些查找技術(shù)的共性？順序查找、折半查找、二叉排序樹查找等。以上討論的查找方法，由于記錄的存儲(chǔ)位置與關(guān)鍵字之間不存在確定的關(guān)系，因此查找時(shí)需要進(jìn)行一系列對(duì)關(guān)鍵字的查找比較，即“查找算法”是建立在比較的基礎(chǔ)上的，查找效率由比較一次縮小的查找范圍決定。

待查值k確定k在存儲(chǔ)結(jié)構(gòu)中的位置散列技術(shù)僅僅是一種查找技術(shù)嗎？散列既是一種查找技術(shù)，也是一種存儲(chǔ)技術(shù)。散列是一種完整的存儲(chǔ)結(jié)構(gòu)嗎？散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達(dá)記錄之間的邏輯關(guān)系，所以，散列主要是面向查找的存儲(chǔ)結(jié)構(gòu)。散列技術(shù)適合于哪種類型的查找？散列技術(shù)一般不適用于允許多個(gè)記錄有同樣關(guān)鍵碼的情況。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關(guān)鍵碼的記錄，也不可能找到在某一范圍內(nèi)的記錄。散列技術(shù)的關(guān)鍵問題：⑴散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡單、均勻、存儲(chǔ)利用率高的散列函數(shù)。①所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度。②所選函數(shù)對(duì)關(guān)鍵字計(jì)算出的地址，應(yīng)在Hash地址集中大致均勻分布，以盡量減少?zèng)_突。散列技術(shù)的關(guān)鍵問題：⑵沖突的處理。如何采取合適的處理沖突方法來解決沖突。①Hash函數(shù)。若Hash函數(shù)選擇得當(dāng)，就可使Hash地址盡可能均勻地分布在Hash地址空間上，從而減少?zèng)_突的發(fā)生；否則，若Hash函數(shù)選擇不當(dāng)，就可能使Hash地址集中于某些區(qū)域，從而加大沖突的發(fā)生。②處理沖突的方法。選擇適當(dāng)?shù)腍ash函數(shù)可以減少?zèng)_突，但不能避免沖突，因此當(dāng)沖突發(fā)生時(shí)，必須有較好的處理沖突的方法。③Hash表的裝填因子。散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：H(key)=a

key+b（a，b為常數(shù)）例：關(guān)鍵碼集合為{10,30,50,70,80,90}，選取的散列函數(shù)為H(key)=key/10，則散列表為：0123456789103050708090適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。散列函數(shù)——直接定址法散列函數(shù)為：H(key)=keymodp

1470147014散列地址56494235282114關(guān)鍵碼如何選取合適的p，產(chǎn)生較少?zèng)_突？例：p＝21=3×7散列函數(shù)——除留余數(shù)法若p取偶數(shù)時(shí)，偶數(shù)的關(guān)鍵字將映射到Hash表的偶數(shù)地址，奇數(shù)的關(guān)鍵字將映射到Hash表的奇數(shù)地址，從而增加了沖突的可能；若p含有質(zhì)因子即p=mn，則所有含有m或n因子的關(guān)鍵字的Hash地址均為m或n的倍數(shù)，這也會(huì)增加沖突的可能性。根據(jù)關(guān)鍵碼在各個(gè)位上的分布情況，選取分布比較均勻的若干位組成散列地址。

例：關(guān)鍵碼為8位十進(jìn)制數(shù)，散列地址為2位十進(jìn)制數(shù)81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧散