第09章-2 查找

1、第九章查找n9.1 靜態(tài)查找表n9.2 動態(tài)查找表n9.3 哈希表29.2 動態(tài)查找表nB-樹（平衡多路查找樹）及其查找 一棵m階的B-樹，或?yàn)榭諛洌驗(yàn)闈M足下列性質(zhì)的m叉樹：樹中每個(gè)結(jié)點(diǎn)最多有m棵子樹；若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；除根結(jié)點(diǎn)之外的非葉子結(jié)點(diǎn)至少有m/2棵子樹；結(jié)點(diǎn)的結(jié)構(gòu)如下：（n，A0，K1，A1，K2，An-1，Kn，An） 其中Ki表示關(guān)鍵字，且KiKi+1；Ai表示孩子結(jié)點(diǎn)指針，且Ai-1所指子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki；n為結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，m/2-1nm-1；所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，并且不帶信息。3 以下是一個(gè)3階B-樹，除根結(jié)點(diǎn)外，每個(gè)結(jié)

2、點(diǎn)中的子樹個(gè)數(shù)不少于2，不多于3，即每個(gè)結(jié)點(diǎn)中最多含有2個(gè)關(guān)鍵字，最少含有1個(gè)關(guān)鍵字。241547211792838335549653089769892 4nB-樹及其查找 在B-樹上查找關(guān)鍵字Kn從根結(jié)點(diǎn)出發(fā)，先在結(jié)點(diǎn)上查找K，則若找到，則查找成功；如果KiKKi+1，沿Ai 子樹繼續(xù)查找；如果KKn，沿An子樹繼續(xù)查找。n若在葉子結(jié)點(diǎn)中查找失敗，則查找失敗。9.2 動態(tài)查找表59.2 動態(tài)查找表nB-樹的插入和刪除向B-樹中增加新的記錄n新增記錄將被插入到葉子結(jié)點(diǎn)上；n先通過查找操作，定位待插入的葉子結(jié)點(diǎn)，再向葉子結(jié)點(diǎn)中插入新記錄；n如果插入后結(jié)點(diǎn)中的記錄個(gè)數(shù)（關(guān)鍵字個(gè)數(shù)）超過階數(shù)-1，則

3、進(jìn)行分裂調(diào)整；69.2 動態(tài)查找表nm階B-樹的插入和刪除分裂調(diào)整n當(dāng)插入新記錄后的結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)超過m-1時(shí)：E1：將結(jié)點(diǎn)的中間記錄抽出，將結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn)；E2：將中間記錄加入到其父結(jié)點(diǎn)中；E3：如果父結(jié)點(diǎn)失衡，繼續(xù)對父結(jié)點(diǎn)作出調(diào)整。756238731263547523523568731265247例：在一棵5階B-樹上，插入新結(jié)點(diǎn)后的分裂調(diào)整。9.2 動態(tài)查找表8設(shè)輸入序列：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 26構(gòu)造3階B-樹454532 3216453216453216774532167745947732164594773216

4、944538773216944438454432771638459416384594327744384594327744211645943277442116393894327744211639386845943277442116684538333994774421166845383233399477446845383233392116269477446845333916263221389477684533391626213844329nB-樹的插入和刪除從B-樹中刪除記錄n先通過查找操作，定位待刪除的記錄；n從記錄所在結(jié)點(diǎn)上刪除該記錄；n若被刪除記錄的結(jié)點(diǎn)為最下層的非葉子結(jié)點(diǎn)，且結(jié)點(diǎn)中的記錄數(shù)

5、不少于階數(shù)/2，則刪除完成，否則須進(jìn)行合并調(diào)整；9.2 動態(tài)查找表10- 合并調(diào)整被刪除關(guān)鍵字所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目不小于m/2則只需從該結(jié)點(diǎn)刪去該關(guān)鍵字Ki；被刪除關(guān)鍵字所在結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目等于m/2-1,而與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目大于m/2-1,則需將其兄弟結(jié)點(diǎn)中的最小(或最大)的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親中小于(或大于)且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。被刪除關(guān)鍵字結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于m/2-1.假設(shè)該結(jié)點(diǎn)有右兄弟,且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Ai所指,則在刪去關(guān)鍵字之后,它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針,加上雙

6、親結(jié)點(diǎn)中的關(guān)鍵字Ki一起,合并到Ai所指兄弟結(jié)點(diǎn)中。9.2 動態(tài)查找表11153677416545515915417745655159123742596166355672132281893756355972132281896166當(dāng)被刪除記錄的結(jié)點(diǎn)中的記錄數(shù)低于下限，當(dāng)被刪除記錄的結(jié)點(diǎn)中的記錄數(shù)低于下限，如果兄弟結(jié)點(diǎn)中有富余的記錄，則向其兄弟結(jié)點(diǎn)借記錄。如果兄弟結(jié)點(diǎn)中有富余的記錄，則向其兄弟結(jié)點(diǎn)借記錄。下面是從一個(gè)下面是從一個(gè)5階階B-樹中刪除一條記錄的例子。樹中刪除一條記錄的例子。13375635597213228189616613228189357237596166當(dāng)被刪除記錄的結(jié)點(diǎn)中的記

7、錄數(shù)低于下限，且其兄弟結(jié)點(diǎn)當(dāng)被刪除記錄的結(jié)點(diǎn)中的記錄數(shù)低于下限，且其兄弟結(jié)點(diǎn)中沒有富余的記錄，則與其兄弟合并。中沒有富余的記錄，則與其兄弟合并。下面是從一個(gè)下面是從一個(gè)5階階B-樹中刪除一條記錄的例子。樹中刪除一條記錄的例子。14452453 903 12375061 70100452453 903375061 70100452461 90337537010045249033761 7010045903 2461 7010045 903 2461 7010045 903 2461 70100從下面的從下面的3階階B-樹中依次刪去：樹中依次刪去：12, 50, 53, 3715nB+樹B+樹是一

8、種變異的B-樹。有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字。所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。1.所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹中的最大（或最小）關(guān)鍵字。9.2 動態(tài)查找表169.3 哈希表 前面我們所介紹的三種查找方法的共同特點(diǎn)在于：通過對關(guān)鍵字的一系列比較，逐步縮小查找范圍，直到確定記錄的存儲位置或確定查找失敗。 哈希法則希望不經(jīng)過任何比較，一次存取就能得到所查記錄，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個(gè)確定的函數(shù)對應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲位置相對應(yīng)，這樣查找時(shí)只需

9、對記錄的關(guān)鍵字進(jìn)行某種運(yùn)算就能確定結(jié)點(diǎn)在表中的位置。稱這個(gè)對應(yīng)關(guān)系為哈希函數(shù)。 n哈希函數(shù)17 假定某教室有35個(gè)座位，如果不加限定讓學(xué)生任意就座，則要找某個(gè)學(xué)生時(shí)就要將待找學(xué)生與當(dāng)前座位上的學(xué)生一一做比較，這就是我們前面所介紹的查找方法的大致思路。 哈希法則要限定學(xué)生所坐的位置，比如可規(guī)定學(xué)生座位的編號應(yīng)與其學(xué)號的末兩位相同，則學(xué)號為993605的學(xué)生應(yīng)坐編號為5的座位。這樣我們要找某個(gè)學(xué)生時(shí)只需根據(jù)其學(xué)號的末兩位到相應(yīng)座位上去找即可，不必一一比較了。 在這個(gè)例子里，學(xué)生好比記錄，學(xué)號則為關(guān)鍵字，對關(guān)鍵字進(jìn)行的操作則是取其末兩位，用以確定記錄的位置。 n哈希法舉例9.3 哈希表9.3 哈希表

10、n哈希法舉例9.3 哈希表18gassummeryockbloodzoomJohn0123Hash表summerpictureplatemomentpleasurebeachcompanygaszoombloodfrenchJohnnewlandyockH(key)集合n思想9.3 哈希表19哈希函數(shù)是一個(gè)映射函數(shù)，哈希函數(shù)的設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長允許的范圍內(nèi)即可。對不同的關(guān)鍵字可能得到同一哈希地址，即key1key2，而H(key1)=H(key2),這種現(xiàn)象稱為沖突。根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集

11、上，并以函數(shù)值作為記錄在表中的存儲位置，這樣構(gòu)建的表稱為哈希表或散列表，所得存儲位置稱為哈希地址或散列地址。n相關(guān)概念9.3 哈希表20散列函數(shù)的常用構(gòu)造方法散列函數(shù)的常用構(gòu)造方法n選擇法選擇法n疊加法疊加法n折疊法折疊法n模除法模除法n數(shù)乘法數(shù)乘法n平方取中法平方取中法n基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法n偽隨機(jī)法偽隨機(jī)法n哈希/散列函數(shù)9.3 哈希表21如何能盡量避免沖突？如果發(fā)生沖突，該如何解決？n實(shí)現(xiàn)哈希查找待解決的問題9.3 哈希表22 若對于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)映像到地址集合中任何一個(gè)地址的概率是相等的，則稱此類哈希函數(shù)為均勻的哈希函數(shù)。 直接定址法：直接取關(guān)鍵字本身或者關(guān)鍵字

12、加上一個(gè)常數(shù)作為哈希地址。H(key)=key或H(key)=a*key+b 由于直接定址所得地址集合和關(guān)鍵字集合的大小相同。因此，對于不同的關(guān)鍵字不會發(fā)生沖突。但實(shí)際中能夠使用這種哈希函數(shù)的情況很少。n哈希函數(shù)的構(gòu)造方法9.3 哈希表23數(shù)學(xué)分析法：假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.

13、 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 數(shù)字分布近乎隨機(jī)數(shù)字分布近乎隨機(jī)所以：取所以：取任意組合作哈希地址任意組合作哈希地址n哈希函數(shù)的構(gòu)造方法9.3 哈希表24平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分可以不同），然后取這幾部分的疊加和作為哈希地址。關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻時(shí)，可以采用折疊法得到哈希函數(shù)。n哈希函數(shù)的構(gòu)造方法9.3 哈希表25除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p 除后所得余數(shù)為哈希地址。這是一種最簡單，也是最常用的構(gòu)造哈希函數(shù)的方法。H(key

14、) = key % p ( pm )n哈希函數(shù)的構(gòu)造方法9.3 哈希表選擇哈希函數(shù)需考慮的因素：計(jì)算哈希值所需時(shí)間關(guān)鍵字的長度哈希表的大小關(guān)鍵字的分布情況記錄的查找頻率26 在設(shè)計(jì)或選用哈希函數(shù)時(shí)希望由它得到的地址能均勻散列分布在哈希表的空間中，即每個(gè)關(guān)鍵字能唯一對應(yīng)表中的一個(gè)地址。但可能出現(xiàn)多個(gè)關(guān)鍵字對應(yīng)一個(gè)地址的情況，這種情況稱為沖突。解決沖突的方法是為同義詞（哈希值相同的關(guān)鍵字）另外尋找一個(gè)新地址。開放定址法：按某種方法在哈希表中形成一個(gè)探查地址序列Hi，沿著這個(gè)序列在哈希表中逐個(gè)查找，直到碰到無沖突（找到或該位置為空）的位置為止。H Hi i=(H(key)+d=(H(key)+di

15、i)% m i=1,2,k(k=m-1)% m i=1,2,k(k=m-1)n處理沖突的方法9.3 哈希表di:增量序列；根據(jù)di取值的不同形式，可有多種探測法。27開放定址法：按某種方法在散列表中形成一個(gè)探查地址序列，沿著這個(gè)探查地址序列在數(shù)組中逐個(gè)查找，直到碰到無沖突的位置為止，并放入記錄。H Hi i=(H(key)+d=(H(key)+di i)% m i=1,2,k(k=m-1)% m i=1,2,k(k=m-1)n處理沖突的方法9.3 哈希表一次線性探測法：di=1,2,3,4,5,，m-1二次探測法：di=12, -12,22,-22,28再哈希法：在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。 H Hi i=RH=RHi i(key) i=1,2,k(key) i=1,2,k鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一個(gè)線性鏈表中。 建立一個(gè)公共溢出區(qū)：所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。n處理沖突的方法9.3 哈希表29n散列表上的查找E1：計(jì)算H(key)，獲得存儲地址；E2：nE21：如果沖突，按照沖突解決策略，計(jì)算下一個(gè)地址；nE22:循環(huán)直到元素為空或等于keyE3：若元素為空，則查找失敗，否則查找成功。n散列