數(shù)據(jù)結(jié)構(gòu)簡明教程（第3版）課件 第8章查找(下)

第8章查找8.1

查找的概念8.2靜態(tài)查找表8.3動態(tài)查找表8.4哈希表查找第8章查找1/61B樹中所有結(jié)點的孩子結(jié)點最大值稱為B樹的階，通常用m表示，從查找效率考慮，要求m≥3。一棵m階B樹或者是一棵空樹，或者是滿足下列要求的m叉樹：8.3.3B樹8.3.3

B樹樹中每個結(jié)點至多有m個孩子結(jié)點（即至多有m-1個關(guān)鍵字）。若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹。除根結(jié)點外，所有內(nèi)部結(jié)點至少有

m/2

棵子樹。1.B樹的定義2/61所有的內(nèi)部結(jié)點中包含下列信息數(shù)據(jù)：nP0K1P1K2P2…KnPnKi（i=1，…，n）為關(guān)鍵字，且Ki<Ki+1（i=1，…，n-1）。Pi（i=0，…，n）為指向子樹根結(jié)點的指針，且指針Pi-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki（i=1，…，n），Pn所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn。n為該結(jié)點中關(guān)鍵字個數(shù)，并且滿足

m/2

-1≤n≤m-1（設(shè)MIN=

m/2

-1，MAX=m-1）。樹的所有外部結(jié)點都出現(xiàn)在同一層次上，并且不帶信息（實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。8.3.3

B樹3/61根結(jié)點高度為4葉子結(jié)點層外部結(jié)點層內(nèi)部結(jié)點104268121618202428142226abdefghic一棵4階B樹m=4內(nèi)部結(jié)點關(guān)鍵字最多個數(shù)MAX=m-1=3內(nèi)部結(jié)點關(guān)鍵字最少個數(shù)MIN=

m/2-1=18.3.3

B樹4/612.B樹的查找在B樹中查找給定關(guān)鍵字的方法類似于二叉排序樹上的查找，不同的是在每個結(jié)點上確定向下查找的路徑不一定是二路（即二叉）的，而是n+1路的。因為結(jié)點內(nèi)的關(guān)鍵字序列是有序的數(shù)量key[1..n]，故既可以用順序查找關(guān)鍵字為k的方法查找，也可以用折半查找。8.3.3

B樹5/61將k與根結(jié)點比較開始：若k=K[i]，則查找成功。若k<K[1]，則沿著指針P[0]所指的子樹繼續(xù)查找。若K[i]<k<K[i+1]，則沿著指針P[i]所指的子樹繼續(xù)查找。若k>K[n]，則沿著指針P[n]所指的子樹繼續(xù)查找。nP0K1P1K2P2…KnPn從前向后找到恰好大于k的K[i]8.3.3

B樹6/61104268121618202428142226bdefghic根結(jié)點葉子結(jié)點層外部結(jié)點層查找關(guān)鍵字168.3.3

B樹7/61向m階B樹中插入一個關(guān)鍵字k的步驟如下：3.B樹的插入

（1）查找：從根結(jié)點開始比較，類似于查找過程，找到一個合適的葉子結(jié)點來插入關(guān)鍵字k。也就是說，關(guān)鍵字k一定是插入到某個葉子結(jié)點中。

（2）插入：在葉子結(jié)點x中插入關(guān)鍵字k。8.3.3

B樹8/61在葉子結(jié)點x中插入關(guān)鍵字k。分為兩種情況：若x結(jié)點的關(guān)鍵字個數(shù)小于MAX（m-1）

直接有序插入k。若x結(jié)點的關(guān)鍵字個數(shù)恰好為MAX，

分裂結(jié)點：k1

k2…km-1結(jié)點x有序插入kk1

k2…ks…km中間位置關(guān)鍵字結(jié)點x1分裂…ks…k1…ks-1ks+1…km結(jié)點x28.3.3

B樹9/614.B樹的創(chuàng)建給定一個關(guān)鍵字序列創(chuàng)建一棵m階B樹的過程是，從一棵空樹開始，掃描所有的關(guān)鍵字k，采用前面介紹的B樹插入方式將其插入到B樹中。顯然，m值的不同，構(gòu)造的B樹是不同的。8.3.3

B樹10/61【例8.13】給定的關(guān)鍵字序列為（1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15），創(chuàng)建一棵5階B樹。這里m=5，結(jié)點中最大關(guān)鍵字個數(shù)MAX=m-1=4。112,6,712678.3.3

B樹解11/61111267111271164,8,131247811136101247810111361246107811138.3.3

B樹12/615,17,9,161245610789111316172012456107891113161720124561016789111317208.3.3

B樹13/6131234561016789111317203610167891113172012348.3.3

B樹14/6112,14,18,19361016789111213141718192012348.3.3

B樹15/61153610167891112131415171819201234361013167891718192012341112141513163678917181920123411121415108.3.3

B樹16/615.B樹的刪除在m階B樹中刪除一個關(guān)鍵字k的步驟如下：

（1）查找：從根結(jié)點開始比較，類似于查找過程，找到包含關(guān)鍵字k的結(jié)點。

（2）刪除：在該結(jié)點中刪除關(guān)鍵字k分兩種情況：一種是在葉子結(jié)點上刪除關(guān)鍵字k；另一種是在非葉子結(jié)點上刪除關(guān)鍵字k。8.3.3

B樹17/61在非葉子結(jié)點上刪除關(guān)鍵字k可以轉(zhuǎn)化為在葉子結(jié)點中刪除：如果這個非葉子結(jié)點中某個關(guān)鍵字ki=k，則以指針Pi所指子樹中的最小關(guān)鍵字mink替代ki。mink所在的結(jié)點一定是葉子結(jié)點。然后在相應(yīng)的葉子結(jié)點中刪除mink；對稱地：也可以用指針Pi-1所指子樹中的最大關(guān)鍵字maxk替代ki，然后在相應(yīng)的葉子結(jié)點中刪除maxk。8.3.3

B樹18/61（1）從y結(jié)點中刪除關(guān)鍵字mink后，其中關(guān)鍵字個數(shù)仍大于等于MIN（MIN=

m/2

-1），直接刪除關(guān)鍵字mink，刪除過程結(jié)束。在B樹的葉子結(jié)點y中刪除關(guān)鍵字mink共有以下三種情況：14510MIN=3mink=5例如：14108.3.3

B樹19/61（2）從y結(jié)點中刪除關(guān)鍵字mink后，其中關(guān)鍵字個數(shù)少于MIN，而與y結(jié)點相鄰的左兄弟（或右兄弟）結(jié)點中的關(guān)鍵字多于MIN個

則向兄弟借一個關(guān)鍵字。145MIN=3mink=5例如：8910…14689107…768.3.3

B樹20/61（3）從y結(jié)點中刪除關(guān)鍵字mink后，其中關(guān)鍵字個數(shù)少于MIN，而且y結(jié)點左右相鄰的兄弟結(jié)點中的關(guān)鍵字都是MIN個

則可將y結(jié)點和它的雙親結(jié)點中的一個關(guān)鍵字合并到它的兄弟結(jié)點中。

如果這樣合并后使雙親結(jié)點中的關(guān)鍵字少于MIN個，則需要繼續(xù)進(jìn)行合并，直到根結(jié)點。145MIN=3mink=5例如：7896…146789…8.3.3

B樹21/61在索引文件組織中,經(jīng)常使用B樹的一些變形，其中B+樹是一種應(yīng)用廣泛的變形。

一棵m階B+樹滿足下列條件：

8.3.4B+樹每個分支結(jié)點至多有m棵子樹。根結(jié)點或者沒有子樹，或者至少有兩棵子樹。除根結(jié)點外，其他每個分支結(jié)點至少有

m/2

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

B+樹22/611028410246810121416182022242628142228sqtroot記錄層葉子層一棵4階的B+樹示例：隨機(jī)查找順序查找8.3.4

B+樹23/61所有葉子結(jié)點包含全部關(guān)鍵字及指向相應(yīng)記錄的指針，而且葉子結(jié)點按關(guān)鍵字大小順序鏈接（可以把每個葉子結(jié)點看成是一個基本索引塊，它的指針不再指向另一級索引塊，而是直接指向數(shù)據(jù)文件中的記錄）。所有分支結(jié)點（可看成是索引的索引）中僅包含它的各個子結(jié)點（即下級索引的索引塊）中最大關(guān)鍵字及指向子結(jié)點的指針。

8.3.4

B+樹24/61B+樹中具有n個關(guān)鍵字的結(jié)點含有n棵子樹，即每個關(guān)鍵字對應(yīng)一棵子樹。而在B樹中，具有n個關(guān)鍵字的結(jié)點含有(n+1)棵子樹。B+樹中所有非葉子結(jié)點僅起到索引的作用，而所有葉子結(jié)點包含了全部關(guān)鍵字。而在B樹中，葉子結(jié)點包含的關(guān)鍵字與其他結(jié)點包含的關(guān)鍵字是不重復(fù)的。B+樹支持隨機(jī)查找和順序查找。而B樹僅僅支持隨機(jī)查找。8.3動態(tài)查找表

m階的B+樹和m階的B樹的差異：25/61哈希表（HashTable）又稱散列表，是除順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)和索引表存儲結(jié)構(gòu)之外的又一種存儲結(jié)構(gòu)。

8.4哈希表查找8.4.1哈希表的基本概念8.4哈希表查找26/61哈希函數(shù)h存儲地址存儲地址=h(key)n個對象個數(shù)m（m≥n）的連續(xù)內(nèi)存單元8.4哈希表查找27/61學(xué)號姓名分?jǐn)?shù)201201王實85201205李斌82201206劉英92201202張山78201204陳功90哈希表長度m=6（存儲單元的地址為0～5）記錄個數(shù)n=5哈希函數(shù)：h(學(xué)號)=學(xué)號-2012011.1數(shù)據(jù)結(jié)構(gòu)概述地址學(xué)號姓名分?jǐn)?shù)0201201王實851201202張山7823201204陳功904201205李斌825201206劉英92第1章學(xué)生成績表28/61地址學(xué)號姓名分?jǐn)?shù)0201201王實851201202張山7823201204陳功904201205李斌825201206劉英92O(1)，按關(guān)鍵字查找速度快哈希函數(shù)：h(學(xué)號)=學(xué)號-201201哈希表查找201204的學(xué)生姓名h(201204)=201204-201201=3地址3的記錄姓名為"陳功"8.4哈希表查找29/61哈希函數(shù)：h(學(xué)號)=學(xué)號-201201如果n=30，m=35，但學(xué)號分布分散。學(xué)號201201，h(201201)=201201-201201=0…學(xué)號201250，h(201250)=201250-201201=49？哈希函數(shù)：h(學(xué)號)=(學(xué)號-201201)%m學(xué)號201201，h(201201)=(201201-201201)%35=0…學(xué)號201250，h(201250)=(201250-201201)=49%35=14問題18.4哈希表查找30/61h(201204)=(201204-201201)%35=3如果存在一個學(xué)號為201239,h(201239)=(201239-201201)%35=38%35=3?問題2哈希函數(shù)：h(學(xué)號)=(學(xué)號-201201)%m8.4哈希表查找31/61可能存在這樣的問題，對于兩個關(guān)鍵字ki和kj（i≠j），有ki≠kj（i≠j），但h(ki)=h(kj)。把這種現(xiàn)象叫做哈希沖突（同義詞沖突）。如果出現(xiàn)同義詞沖突，后存儲的記錄會覆蓋前面存儲的記錄。這是不允許的！?。?/p>

需要解決哈希沖突8.4哈希表查找32/61設(shè)計好的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。設(shè)計解決沖突的方法。歸納起來，哈希表設(shè)計：8.4哈希表查找33/61構(gòu)造哈希函數(shù)的目標(biāo)：使得到的哈希地址盡可能均勻地分布在m個連續(xù)內(nèi)存單元地址上，同時使計算過程盡可能簡單以達(dá)到盡可能高的時間效率。根據(jù)關(guān)鍵字的結(jié)構(gòu)和分布的不同，有多種構(gòu)造哈希函數(shù)的方法。

8.4.2哈希函數(shù)構(gòu)造方法8.4哈希表查找34/61以關(guān)鍵字k本身或關(guān)鍵字加上某個數(shù)值常量c作為哈希地址的方法。即h(k)=k+c。

這種哈希函數(shù)計算簡單，并且不可能有沖突發(fā)生。當(dāng)關(guān)鍵字的分布基本連續(xù)時，可用直接定址法的哈希函數(shù)；否則，若關(guān)鍵字分布不連續(xù)將造成內(nèi)存單元的大量浪費。1.直接定址法8.4哈希表查找35/61學(xué)號姓名分?jǐn)?shù)201201王實85201205李斌82201206劉英92201202張山78201204陳功90哈希表長度m=6（存儲單元的地址為0～5）記錄個數(shù)n=5哈希函數(shù)：h(學(xué)號)=學(xué)號-201201地址學(xué)號姓名分?jǐn)?shù)0201201王實851201202張山7823201204陳功904201205李斌825201206劉英92第1章學(xué)生成績表8.4哈希表查找36/61用關(guān)鍵字k除以某個不大于哈希表長度m的數(shù)p所得的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù)h(k)為：h(k)=kmodp

(mod為求余運算，p≤m)p最好是質(zhì)數(shù)（素數(shù)）。

2.除留余數(shù)法8.4哈希表查找37/61提取關(guān)鍵字中取值較均勻的數(shù)字位作為哈希地址的方法。適合于所有關(guān)鍵字值都已知的情況，并需要對關(guān)鍵字中每一位的取值分布情況進(jìn)行分析。

3.數(shù)字分析法8.4哈希表查找38/61位序123456789231760292326875927396289234363492706816927746389238126292394220哈希地址的集合為{2，75，28，34，16，38，62，20}8.4哈希表查找39/618.4.3哈希沖突解決方法在哈希表中，雖然沖突很難避免，但發(fā)生沖突的可能性卻有大有小。這主要與三個因素有關(guān)：與裝填因子有關(guān)。所謂裝填因子α是指哈希表中已存入的元素數(shù)n與哈希地址空間大小m的比值，即α=n/m。α越小，沖突的可能性就越??；但α越小，存儲空間的利用率就越低。與所采用的哈希函數(shù)有關(guān)。與解決沖突的哈希沖突函數(shù)有關(guān)。8.4哈希表查找40/61發(fā)生沖突時查找周圍一個空位置存放記錄。設(shè)置一個查找周圍一個空位置的函數(shù)。1.開放定址法8.4哈希表查找41/61從發(fā)生沖突的地址（設(shè)為d）開始，依次循環(huán)探測d的下一個地址（當(dāng)?shù)竭_(dá)下標(biāo)為m-1的哈希表表尾時，下一個探測的地址是表首地址0），直到找到一個空閑單元為止。描述公式為：

d0=h(k)，di=(di-1+1)modm

(1≤i≤m-1)（1）線性探測法0123456789********8.4哈希表查找42/61問題：可能出現(xiàn)堆積現(xiàn)象：0123456789101112n=6,m=10,關(guān)鍵字為（10,11,12,19,20,21）哈希函數(shù)：h(key)=key%910，11，1219

h(19)=19%9=1（沖突）d0=1，d1=(1+1)%10=2（沖突）d2=(2+1)%10=3（沖突）d3=(3+1)%10=4（將19放在4位置）01234567891011121920

h(20)=20%9=2（沖突）d0=2，d1=(2+1)%10=3（沖突）d2=(3+1)%10=4（沖突）d3=(4+1)%10=5（將20放在5位置）哈希函數(shù)值不相同的多個記錄爭奪同一個后繼哈希地址稱為非同義詞沖突8.4哈希表查找43/61發(fā)生沖突時前后查找空位置。描述公式為：

d0=h(k)，

di=(d0±i2)modm

(1≤i≤m-1)（2）平方探測法0123456789********8.4哈希表查找44/61平方探測法可以避免出現(xiàn)堆積問題。缺點是不能探測到哈希表上的所有單元，但至少能探測到一半單元。8.4哈希表查找45/61

【例8.15】假設(shè)哈希表長度m=13，采用采用除留余數(shù)法加線性探測法建立如下關(guān)鍵字集合的哈希表：(16,74,60,43,54,90,46,31,29,88,77)。n=11，m=13，除留余數(shù)法的哈希函數(shù)為：

h(k)=kmodp

p應(yīng)為小于等于m的素數(shù)，假設(shè)p取值13。8.4哈希表查找解46/61哈希函數(shù)：h(k)=kmod13解決沖突方法：線性探測法h(16)=3 ha[3]=16,共1次探測h(74)=9 ha[9]=74,共1次探測h(60)=8 ha[8]=60,共1次探測h(43)=4 ha[4]=43,共1次探測h(54)=2 ha[2]=54,共1次探測h(90)=12 ha[12]=90,共1次探測h(46)=7 ha[7]=46,共1次探測h(31)=5 ha[5]=31,共1次探測8.4哈希表查找47/61h(29)=3 有沖突

d0=3，d1=(3+1)%13=4 仍有沖突

d2=(4+1)%13=5 仍有沖突

d3=(5+1)%13=6 ha[6]=29,共4次探測h(88)=10 ha[10]=88,共1次探測h(77)=12 有沖突

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次探測8.4哈希表查找48/61下標(biāo)0123456789101112k7754164331294660748890探測次數(shù)21111411111哈希表ha[0..12]ASLsucc=1*9+2*1+4*111=1.364成功的查找：在ha中找到對應(yīng)的關(guān)鍵字h(77)=12 ha[12]=90≠77

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次比較比較的次數(shù)=探測次數(shù)8.4哈希表查找49/61下標(biāo)0123456789101112k7754164331294660748890哈希表ha[0..12]不成功的查找：在ha中找不到對應(yīng)的關(guān)鍵字xh(x)=12 ha[12]≠x

d0=12，d1=(12+1)%13=0 ha[0]≠x

d2=(0+1)%13=1 ha[1]為空，查找失敗，3次比較確定查找失敗，一定有比較到空為止！8.4哈希表查找50/61哈希表ha中查找失敗的所有情況的探測次數(shù)ASLunsucc=2+1+10+9+8+7+6+5+4+3+2+1+313=4.692下標(biāo)0123456789101112k7754164331294660748890探測次數(shù)211098765432138.4哈希表查找51/61拉鏈法是把所有的同義詞用單鏈表鏈接起來的方法。在這種方法中，哈希表每個單元中存放的不再是記錄本身，而是相應(yīng)同義詞單鏈表的頭指針。由于單鏈表中可插入任意多個結(jié)點，所以此時裝填因子α根據(jù)同義詞的多少既可以設(shè)定為大于1，也可以設(shè)定為小于或等于1，通常取α=1。2.拉鏈法8.4哈希表查找52/61

【例8.16】假設(shè)哈希表長度m=13，采用采用除留余數(shù)法加拉鏈法建立如下關(guān)鍵字集合的哈希表：(16,74,60,43,54,90,46,31,29,88,77)。8.4哈希表查找53/61

采用拉鏈法解決沖突建立的鏈表如下圖所示。23∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧存放的不再是記錄本身8.4哈希表查找解54/6123∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧成功的查找：在ha中找到對應(yīng)的關(guān)鍵字ASLsucc=1*9+2*211=1.18h(77)=12，在ha[12]的單鏈表中共1次比較比較的次數(shù)=對應(yīng)結(jié)點在單鏈表中的序號8.4哈希表查找55/6123∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧ASLunsucc=1*7+2*213=0.846h(x)=3，在ha[3]的單鏈表中共2次比較比較的次數(shù)=對應(yīng)單鏈表