2022-02巖數(shù)據(jù)結(jié)構(gòu)講義第5章查找2010秋

1、數(shù)據(jù)結(jié)構(gòu)與算法Data Structures and Algorithms哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-2學(xué)習(xí)目標(biāo)查找是指在某種數(shù)據(jù)結(jié)構(gòu)上找出滿足給定條件的數(shù)據(jù)元素，又稱檢索，是數(shù)據(jù)處理中常見的重要操作。了解不同數(shù)據(jù)結(jié)構(gòu)上的查找方法。掌握各種查找結(jié)構(gòu)的性質(zhì)、在靜態(tài)和動(dòng)態(tài)環(huán)境下的查找算法的設(shè)計(jì)和實(shí)現(xiàn)方法。掌握各種查找方法的時(shí)間性能(平均查找長(zhǎng)度)的分析方法。能夠根據(jù)具體情況選擇適合的方法解決實(shí)際問題。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-3本章主要內(nèi)容基本概念和術(shù)語線性查找折半（二分）查找分塊查找BST-二叉查找樹 AVL樹B-樹與B+樹散

2、列技術(shù)5.15.25.35.45.55.65.75.8本章小結(jié)哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-45.1 基本概念和術(shù)語查找表：由同一類型的數(shù)據(jù)元素(或)的集合(文件)。關(guān)鍵字：可以標(biāo)識(shí)一個(gè)鍵值：關(guān)鍵字的取值。的某個(gè)數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)組合。主關(guān)鍵字：可以唯一地標(biāo)識(shí)一個(gè)次關(guān)鍵碼：不能唯一地標(biāo)識(shí)一個(gè)的關(guān)鍵字。的關(guān)鍵字。查找：在查找表中找出（確定）一個(gè)關(guān)鍵字值等于給定值的數(shù)據(jù)元素（或）。查找結(jié)果：若在查找集合中找到了與給定值相匹配的數(shù)據(jù)元素，則稱查找成功；否則，稱查找失敗。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-5學(xué)號(hào)入學(xué)成績(jī)0001男0002女2800

3、03女195.1 基本概念和術(shù)語（Cont.）查找的分類：根據(jù)查找方法取決于的鍵值還是的位置？基于關(guān)鍵字比較的查找順序查找、折半查找、分塊查找、BST&AVL、B-樹和B+樹基于關(guān)鍵字散列法位置的查找根據(jù)被查找的數(shù)據(jù)集合位置內(nèi)查找：整個(gè)查找過程都在內(nèi)存進(jìn)行；外存，如B-樹和B+樹外查找：若查找過程中需要哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-65.1 基本概念和術(shù)語（Cont.）查找的分類：根據(jù)查找方法是否改變數(shù)據(jù)集合？靜態(tài)查找：查找+提取數(shù)據(jù)元素屬性信息被查找的數(shù)據(jù)集合經(jīng)查找之后并不改變，就是說，既不新的，也不刪除原有。動(dòng)態(tài)查找：查找+（或刪除元素）被查找的數(shù)據(jù)集合經(jīng)查

4、找之后可以改變，就是說，可以新的，也可以刪除原有。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-75.1 基本概念和術(shù)語（Cont.）查找表的操作SEARCH（k ，F(xiàn)）：在數(shù)據(jù)集合(查找表、文件) F 中查找關(guān)鍵字值等于k 的）。若查找成功，則返回包含 k 的數(shù)據(jù)元素（的位置；否則，返回一個(gè)特定的值。INSERT（R，F(xiàn) ）：在動(dòng)態(tài)環(huán)境下的不成功，則DELETE(k，F(xiàn))：操作。在F 中查找R，若查找R；否則不R。在動(dòng)態(tài)環(huán)境下的刪除操作。在 F 中查找關(guān)鍵字值等于k的數(shù)據(jù)元素（）。若查找成功，則刪除關(guān)鍵字值等于k 的，否則不刪除任何。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/

5、23Slide 5-85.1 基本概念和術(shù)語（Cont.）查找（表）結(jié)構(gòu)：面向查找操作的數(shù)據(jù)結(jié)構(gòu) ，即查找所使用的數(shù)據(jù)結(jié)構(gòu)。查找結(jié)構(gòu)決定查找方法。主要的查找結(jié)構(gòu) ：集合線性表、樹表、散列表線性表：適用于靜態(tài)查找，主要采用線性（順序）查找技術(shù)、折半查找技術(shù)。樹表：靜態(tài)和動(dòng)態(tài)查找均適用，主要采用BST和AVL的查找技術(shù)。散列表：靜態(tài)和動(dòng)態(tài)查找均適用，主要采用散列技術(shù)。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-95.1 基本概念和術(shù)語（Cont.）查找表結(jié)點(diǎn)（數(shù)據(jù)元素、struct records）的類型定義：keytypekey;fields other;查找的性能查找算法時(shí)間

6、性能由關(guān)鍵字的比較次數(shù)來度量。同一查找集合、同一查找算法，關(guān)鍵字的比較次數(shù)與哪些有關(guān)呢？查找算法的時(shí)間復(fù)雜度是問題規(guī)模n和待查關(guān)鍵字在查找集合中的位置k的函數(shù)，記為T(n，k)。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-105.1 基本概念和術(shù)語（Cont.）查找的性能平均查找長(zhǎng)度：把給定值與關(guān)鍵字進(jìn)行比較的次數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度-ASL(Average Length)。Search計(jì)算公式：假設(shè)查找集合中的個(gè)數(shù)pi為查找表中第i的概率，pi=1，ci為查找第i 個(gè)個(gè)所進(jìn)行的n比較次數(shù)，則pcASL iii=1在等概率情況下，即pi = 1/n時(shí)

7、，n 1 ncASLii=1哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-115.2線性查找線性（順序）查找基本：從線性表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于k的結(jié)點(diǎn)，則查找失敗。線性（順序）查找對(duì)結(jié)構(gòu)要求結(jié)構(gòu)適用于靜態(tài)查找結(jié)構(gòu)也適用于動(dòng)態(tài)查找既適用于線性表的順序也適用于線性表的鏈?zhǔn)焦ご笥?jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-125.2線性查找（Cont.）順序表上的查找適合于靜態(tài)查找順序表的類型定義typedefrecords LISTMaxSiz

8、e ;LISTF ;SEARCH操作的實(shí)現(xiàn)：k=350123456789FiiiiiINSERT操作的實(shí)現(xiàn)DELETE操作的實(shí)現(xiàn)不適合順序表哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-13哨兵351098555.2 基本概念和術(shù)語（Cont.）SEARCH (keytypek,last, LISTF )，若找到，則返回該/* 在F1Flast中查找關(guān)鍵字為k的所在的下表，否則返回 0 */i ; F0.key = k ;i = last ;/* F0為偽或哨兵 */while ( Fi.key != k ) i = i 1 ;return i ;/*時(shí)間復(fù)雜度 O( n )

9、；ASL成功=(n+1)/2,ASL失敗=n+1 */哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-145.2線性查找（Cont.）單向表上的查找也適合于動(dòng)態(tài)查找單向表的類型定義struct celltyperecords data ;celltype* next ;typedef celltype *LIST ;INSERT操作的實(shí)現(xiàn) DELETE操作的實(shí)現(xiàn)時(shí)間復(fù)雜度 O( n ) ；ASL成功=(n+1)/2,哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院ASL失敗=n+12010/12/23Slide 5-15LIST SEARCH(keytype k, LIST F)/*在不帶表頭的單向鏈

10、表中查找關(guān)鍵字為k 的，返回其指針*/LIST p =F ;while ( p! = NULL )if ( p-data.key = k ) return p ;elsep = p-next ; return p ;5.3折半查找折半查找（也稱二分查找）的要求：查找表（被查找的數(shù)據(jù)集合）必須采用順序式結(jié)構(gòu)；查找表中的數(shù)據(jù)元素（）必須按關(guān)鍵字有序。FF0.key F1.key F2.key Flast.key或 F0.key F1.key F2.key Flast.key注意：折半查找只適合于靜態(tài)查找！哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-165.3折半查找（Cont.）

11、折半查找的基本：在有序表中，取中間作為比較對(duì)象，若給定值與中間的關(guān)鍵碼相等，則查找成功；若給定值小于中間的關(guān)鍵碼，則在中間的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間的關(guān)鍵碼，則在中間的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。k k1 kmid-1 rmid kmid+1 kn 如果kkmid查找右半?yún)^(qū)哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-17（mid=(1+n)/2）5.3折半查找的示例：折半查找（Cont.）k = 21Flow=1low=1mid=6up=5up=11mid=3low=mid=4 up=5k = 85Flow=1mid

12、=6up=11low=7mid=9up=11low=mid=10 up=11low=10 up=9哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-185.3折半查找（Cont.）折半查找的非遞歸算法實(shí)現(xiàn)步驟初態(tài)化：令low ,up分別表示查找范圍的上、下界，初始時(shí)low = 0, up = last;折半：令mid = (low+up)/2，取查找范圍中間位置元素下標(biāo);比較：k與Fmid.key若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key k，low不變，調(diào)整up = mid - 1，查找范圍縮小一半；3.3 若Fmid.key up 時(shí)，查找失

13、敗，返回 0。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-195.3折半查找（Cont.）折半查找的非遞歸算法實(shí)現(xiàn)BinSearch1(keytype low , up , mid ;low = 1 ; up = last ;while ( low k)elsereturnmid ;up = mid 1 ;low = mid + 1 ;return 0; /* F必須是順序有序表(此處為增序);時(shí)間復(fù)雜度 :(log2 n)*/Slide 5-20哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/235.3折半查找（Cont.）折半查找的遞歸算法實(shí)現(xiàn)步驟初態(tài)化：設(shè)置查找范圍的上界up

14、和下界low;測(cè)試查找范圍：如果low up，則查找失??；否則，3.取查找范圍中間位置元素下標(biāo)令mid = (low+up)/2；比較 k與Fmid.key：3.1 若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key k，遞歸地在左半部分查找（low不變，調(diào)整up = mid 1）；3.3 若Fmid.keyup) return 0; else mid=(low+up)/2;if (k Fmid.key)return BinSearch2(F, mid+1, up, k);else return mid; /* F必須是順序有序表(此處為增序);時(shí)間復(fù)雜度 :(lo

15、g2 n)*/Slide 5-22哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/235.3折半查找的判定樹：折半查找（Cont.）折半查找的過程可以用二叉樹來描述，樹中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)，結(jié)點(diǎn)的值為該在表中的位置。通常稱這個(gè)描述折半查找過程的二叉樹為折半查找判定樹，簡(jiǎn)稱判定樹。折半查找的判定樹的構(gòu)造當(dāng)n=0時(shí)，折半查找判定樹為空；當(dāng)n0時(shí)，折半查找判定樹的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2的樹是與有序表F1 ，根結(jié)點(diǎn)的Fmid-1相對(duì)應(yīng)的折半查找判定樹，根結(jié)點(diǎn)的右 Fmid+1 Fn相對(duì)應(yīng)的折半查找判定樹。是與哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-235

16、.3折半查找（Cont.）判定樹的構(gòu)造F693714108251111外部結(jié)點(diǎn)-失敗結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)-查找成功哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-2410118978564523129106734 15.3折半查找（Cont.）折半查找的ASL若有n個(gè)關(guān)鍵字，則判定樹結(jié)點(diǎn)數(shù)為n+1個(gè)ASL成功=（1*1+2*2+3*4+4*4）/11 = 25/11ASL失敗=（3*4+4*8）/12 = 44/12693714108251111Slide 5-25哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/2310118978564523129106734 15.3折半查找（Cont.）

17、折半查找的判定樹高度nASLbs= pi ci/* pi=1/n */ h/*S=2S - S*/i=1h1= 1/n j 2j-1j= (n+1)/nlog2(n+1)-125當(dāng)n 很大時(shí)，ASLbs log2(n+1)-1作為查找成功時(shí)的平均查找長(zhǎng)度。在查找不成功和情況下查找成功所需關(guān)鍵字的比較次數(shù)都不超過判定樹的高度。因?yàn)榕卸涞闹卸刃∮? 的結(jié)點(diǎn)只能出現(xiàn)在下面兩層上，所以n 個(gè)結(jié)點(diǎn)的判定樹高度和n 個(gè)結(jié)點(diǎn)的完全二叉樹的高度相同，即log2(n+1) 。由此可見，折半查找的能相當(dāng)接近。性能與平均性哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-265.4分塊查找線性查找+折

18、半查找分塊查找的基本均勻分塊，塊間有序，塊內(nèi)無序：首先將表中的元素均勻地分成若干塊，每一塊中的元素的任意排列，而各塊之間要按順序排列；若按從小到大的順序排列，則第一塊中的所有元素的關(guān)鍵字都小于第二塊中的所有元素的關(guān)鍵二塊中的所有元素的關(guān)鍵字都小于第三塊中的所有元素的關(guān)鍵字，如此等等等。建塊索引:然后再建一個(gè)線性表，用以存放每塊中最大(或最小)的關(guān)鍵字，此線性表稱為索引表，它是一個(gè)有序表.012224474索引表IX01234567891011121314F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-2722121398334244382448605874475.4分塊查找（C

19、ont.）分塊查找算法的要點(diǎn)：假設(shè)在帶索引的線性表中查找已知關(guān)鍵字為k 的，則首先查找索引表，確定k 可能出現(xiàn)的塊號(hào)；然后到此塊中進(jìn)行進(jìn)行順序查找。算法的實(shí)現(xiàn)typedeftypedefrecords LISTmaxsize ;/* 線性表主表 */keytypeINDEXmaxblock ;/* 線性表索引表*/012索引表224474IX01234567891011121314F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-2822121398334244382448605874475.4index_search(keytype k,i =0, j ;分塊查找（Cont.）

20、last,blocks, INDEX ix, LIST F,L )while ( k ixi)&( i blocks) /*查索引表,確定k 所在塊i*/i+ ;if( iblocks ) j = i*L;/* 第i 塊的起始下標(biāo) */while( k != Fj.key )&( j = (i+1)*L-1 )&( j data.key，則查找成功；否則，k data.key，則遞歸地在F 的k F-data.key，則遞歸地在F 的右10樹查找k；否則查找k。318哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-355.5二叉查找樹BST （Cont.）二叉查找樹的查找操作：B

21、STNode * SearchBST( keytypek, BSTF )BSTNode * p = F ;if ( p = NULL | k = p-data.key ) /* 遞歸終止條件 */returnp;if ( k data.key ) return ( SearchBST ( k,elsereturn ( SearchBST ( k,p-lchild ) ) ; /* 查找樹 */p-rchild ) ) ; /* 查找右*/哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-365.5二叉查找樹的二叉查找樹BST （Cont.）操作若二叉排序樹為空樹，則新根結(jié)點(diǎn)；否則，

22、新的結(jié)點(diǎn)為的結(jié)點(diǎn)必為一個(gè)新的葉結(jié)點(diǎn).的結(jié)點(diǎn)一定是查找新不成功時(shí)，查找路徑上最后一個(gè)結(jié)點(diǎn)的左兒子或右兒子。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-37void InsertBST(records R, BST F)if ( F =NULL ) F = new BSTNode ; F-data = R ;F-lchild = NULL ；F-rchild = NULL ;else if ( R.key data.key )InsertBST( R , F-lchild )； else if ( R.key F-data.key )InsertBST( R , F-rchild

23、 ); /若R.key=F-data.key,則返回5.5二叉查找樹BST （Cont.）二叉查找樹的建立BST CreateBST ( void )注意：在建立二叉查找樹時(shí)，若按關(guān)鍵字有序順序BST F = NULL; /*初始時(shí)F為空*/輸入各，則keytypekey;產(chǎn)生的二叉cinkey其他字段;/*讀入一個(gè)*/查找樹單鏈表while( key ) /*假設(shè)key=0是輸入結(jié)束標(biāo)志*/如何防止？隨機(jī)輸入各結(jié)點(diǎn)InsertBST( R , F )；/*R */cinkey其他字段 ;/*讀入下個(gè)*/在建立、和刪return除各結(jié)點(diǎn)過程中平衡相關(guān)結(jié)點(diǎn)的F;/*返回建立的二叉查找樹的根*/左

24、、右。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-385.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作刪除某結(jié)點(diǎn)，并保持二叉排序樹特性，分三種情況處理：1）如果刪除的是葉結(jié)點(diǎn)，則直接刪除；2）如果刪除的結(jié)點(diǎn)只有一株樹或右，則直接繼承：將該移到被刪結(jié)點(diǎn)位置；3）如果刪除的結(jié)點(diǎn)有兩株，則用繼承結(jié)點(diǎn)代替被刪結(jié)點(diǎn)，這相當(dāng)于刪除繼承結(jié)點(diǎn)按 1) 或 2) 處理繼承結(jié)點(diǎn)。1051671815哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-395.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作的實(shí)現(xiàn)步驟1. 若結(jié)點(diǎn)p是葉子，則直接刪除結(jié)點(diǎn)p；若結(jié)點(diǎn)p只有若結(jié)

25、點(diǎn)p只有右若結(jié)點(diǎn)p的左右樹，則只需重接p的，則只需重接p的右不空，則樹；3.1 查找結(jié)點(diǎn)p的右上的最左下結(jié)點(diǎn)s及其雙親結(jié)點(diǎn)par；3.2 將結(jié)點(diǎn)s數(shù)據(jù)域替換到被刪結(jié)點(diǎn)p的數(shù)據(jù)域；3.3 若結(jié)點(diǎn)p的右孩子無樹，則將s的右接到par的右上；否則，將s的右3.4 刪除結(jié)點(diǎn)s；接到結(jié)點(diǎn)par的樹上；哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-405.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作的實(shí)現(xiàn)void DeleteB( keytype k, BST &F )recordsdeletemin(BST&F ) if ( F != NULL )records tmp ; B

26、STp ;if ( k data.key ) DeleteB( k, f-lchild ) ;else if ( k F-data.key ) DeleteB( k, f-rchild );elseif ( F-rchild = NULL ) F = F-lchild ;else if( F-lchild = NULL ) F = F-rchild ;elseF-data =deletemin(F-rchild);if ( F-lchild = NULL ) p = F ;tmp = F-data ; F = F-rchild ; delete p ; return tmp ;elseretu

27、rn(deletemin( F-lchild) ;哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-415.5二叉查找樹BST （Cont.）二叉查找樹的查找性能二叉排序樹的查找性能取決于二叉排序樹的形態(tài)，在O(log2n)和O(n)之間。在次情況下，二叉查找樹是通過把有序表的n 個(gè)結(jié)點(diǎn)依而生成的，此時(shí)所得到的二叉查找樹為一株高度為n 的單支樹，它的平均查找長(zhǎng)度和單鏈表上的順序查找相同，(n+1)/2。在最好情況下，二叉查找樹的形態(tài)比較均勻，最終得到一株形態(tài)與折半查找的判定樹相似，此時(shí)的平均查找長(zhǎng)度約為log2 n。二叉查找樹的平均高度為O(log2 n)。因此平均情況下，三種操作

28、的平均時(shí)間復(fù)雜性為O(log2 n)就平均性能而言，二叉查找樹上的查找和二分查找差不多就表的有序性而言，二叉查找樹更有效。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-425.6AVL樹AVL樹（Balanced Binary Tree or Height-Balanced Tree）AVL樹或者是空二叉樹，或者是具有如下性質(zhì)的BST：高度之差的絕對(duì)值不超過1；根結(jié)點(diǎn)的左、右仍然是AVL樹。且根結(jié)點(diǎn)樹和右結(jié)點(diǎn)的平衡因子BF（Balanced Factor）一個(gè)結(jié)點(diǎn)的樹與右的高度之差。-1 11AVL樹中的任意結(jié)點(diǎn)的BF只可能是-1，0和1。0+1AVL樹的ASL可保持在O(lo

29、g2n)AVL樹的查找操作與BST的相同00000016Slide 5-43哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/235.6AVL樹的平衡化處理AVL樹（Cont.）向AVL樹結(jié)點(diǎn)可能造成不平衡，此時(shí)要調(diào)整樹的結(jié)構(gòu)，使之重新達(dá)到平衡希望任何初始序列的二叉樹都是AVL樹示例：假設(shè)25，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。127027-125025-225RR旋轉(zhuǎn)030030125025-127027012030哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-445.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)2

30、5，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。227127127LL旋轉(zhuǎn)0110030030227030225012125025112012011-13012LR旋轉(zhuǎn)125011018哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-455.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。227030-112LR旋轉(zhuǎn)125011哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-46-127001118305.6AV

31、L樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。025125125-127-127-127012-112-112030030030018018011118011011020014014哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-475.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。225RL旋轉(zhuǎn)-127-212030118011020-114015哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)

32、院2010/12/23Slide 5-481250-112011205.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是一關(guān)鍵字序列，并以上述順序建立AVL樹。LR旋轉(zhuǎn)-1225-1140-1112-1011022哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-4925182714203010121522142510 -1-1111200011225.6AVL樹的平衡化處理在一棵AVL樹上AVL樹（Cont.）結(jié)點(diǎn)可能會(huì)破壞樹的平衡性，需要平衡化處理恢復(fù)平衡，且保持BST的結(jié)構(gòu)性質(zhì)。若用Y表示新的結(jié)點(diǎn)，A表示離新結(jié)

33、點(diǎn)Y最近的，且平衡因子變?yōu)?的祖先結(jié)點(diǎn)?？梢杂?種旋轉(zhuǎn)進(jìn)行平衡化處理: LL型：新結(jié)點(diǎn)Y RR型：新結(jié)點(diǎn)Y LR型：新結(jié)點(diǎn)Y RL型：新結(jié)點(diǎn)Y入到 A 的入到 A 的右入到 A 的 入到 A 的右樹的的右樹的右的樹上（順）上（逆）上（逆、順）樹上（順、逆）哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-505.6AVL樹的平衡化處理 LL型：新結(jié)點(diǎn)YAVL樹（Cont.）入到 A 的樹的樹上（順）B0AA+ 2+ 10 ACDBBC+ 10DECEED(c) 右向旋轉(zhuǎn)后的AVL樹(b) D中結(jié)點(diǎn)(a)AVL樹哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-51hhh

34、hhh+1hh+1h5.6AVL樹的平衡化處理 RR型：新結(jié)點(diǎn)YAVL樹（Cont.）入到 A 的右的右上（逆）CA0A-1-2BA0ECB0C-1EBDDED(c)左向旋轉(zhuǎn)后的AVL樹(b)E中結(jié)點(diǎn)(a)AVL樹哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-52hhhhhh+1hh+1h5.6AVL樹的平衡化處理 LR型：新結(jié)點(diǎn)YAVL樹（Cont.）入到 A 的A上(逆,順)E樹的右A+ 20CC-1ABEBDGEDFGC+1BFFGD(b)繞E，將B逆時(shí)針轉(zhuǎn)后哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(c)繞E，將A順時(shí)針轉(zhuǎn)后(a)F結(jié)點(diǎn)高度變?yōu)閔2010/12/23Slide 5-53

35、hhh-1hhh-1hhhh-1hh5.6AVL樹的平衡化處理 RL型：新結(jié)點(diǎn)YAVL樹（Cont.）入到 A 的右樹上(順, 逆)的AAD-20BCBACD+1DFECBFGE1FGGE(c)繞D，A逆時(shí)針轉(zhuǎn)之后Slide 5-54(a)G結(jié)點(diǎn)(b)繞D，C順時(shí)針轉(zhuǎn)之后哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院高度變?yōu)閔2010/12/23hhhh-1hhh- 1hh-1hhh5.6AVL樹（Cont.）AVL樹的操作與建立對(duì)于一組關(guān)鍵字的輸入序列，從空開始不斷地結(jié)點(diǎn)，AVL樹一個(gè)結(jié)點(diǎn)后就應(yīng)判斷從該結(jié)點(diǎn)到根的路徑上有無結(jié)最后每點(diǎn)發(fā)生不平衡不平衡問題，利用旋轉(zhuǎn)方法進(jìn)行樹的調(diào)整，衡化建AVL樹過程是不斷結(jié)點(diǎn)和必

36、要時(shí)進(jìn)行平衡化的過程哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-555.6AVL樹的刪除操作AVL樹（Cont.）刪除操作與衡化次數(shù)多。操作是對(duì)稱的（鏡像），但可能需要的平因?yàn)槠胶饣粫?huì)增加度。在有可能使樹增高的增高；的高度，但可能會(huì)減少的高操作中，一次平衡化能抵消掉樹而在有可能使樹減低的刪除操作中，平衡化可能會(huì)帶來祖先結(jié)點(diǎn)的不平衡。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-565.6AVL樹的性能分析AVL樹（Cont.）令Nh是高為h的AVL樹中結(jié)點(diǎn)個(gè)數(shù)的最小值，在最稀疏情況下，這棵AVL樹的一棵樹的高度為h2，這兩棵的高度為h1，而另一棵子也都是AV

37、L樹。因此， Nh =Nh-1+Nh-2+1，其中N0=0，N1=1，N2=2?？梢园l(fā)現(xiàn)， Nh的遞歸定義與Fibonacci數(shù)的定義Fn = Fn-1 +Fn-2（其中 F0 = 0，F(xiàn)1 =1）相似可以用數(shù)學(xué)歸納法證明，Nh = Fh+21 （h 0） Fhh/5,其中=(1+5 )/2，所以，Nhh+2/5-1所以，一棵包含n個(gè)結(jié)點(diǎn)的AVL樹，其高度h至多為log(n+1)2因此，對(duì)于包含n個(gè)結(jié)點(diǎn)的AVL樹，其時(shí)間為O(log n)情況下的哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-575.7B-樹和B+樹（Cont.）當(dāng)符號(hào)表的大小超過內(nèi)存容量時(shí)，由于必須從磁盤等輔助

38、存儲(chǔ)設(shè)備上去這些查找樹結(jié)構(gòu)中的結(jié)點(diǎn)，每次只能根據(jù)需要一個(gè)結(jié)點(diǎn)，因此，AVL樹性能就不是很高。在AVL樹在結(jié)點(diǎn)高度上采用相對(duì)平衡的策略，使其平均性能接近于BST的最好情況下的性能。如果保持查找樹在高度上的絕對(duì)平衡，而允許查找樹結(jié)點(diǎn)的個(gè)數(shù)（分支個(gè)數(shù)）在一定范圍內(nèi)變化，能否獲得很好的查找性能呢？基于這樣的想法，人們?cè)O(shè)計(jì)了許多在高度上保持絕對(duì)平衡，而在寬度上保持相對(duì)平衡的查找結(jié)構(gòu)如B-樹及其各種變形結(jié)構(gòu)，這些查找結(jié)構(gòu)不再是二叉結(jié)構(gòu)，而是m-路查找樹（m-way search tree），且以其高為其基本性質(zhì)，在實(shí)際中都有著廣泛的應(yīng)用。保持等哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-

39、585.7B-樹和B+樹（Cont.）m-路查找樹：一棵m-路查找樹或者是一棵空樹, 或者是滿足如下性質(zhì)的樹：根結(jié)點(diǎn)最多有 m 棵, 并具有如下的結(jié)構(gòu)：n, A0, ( K1, A1 ), ( K2, A2 ), , ( Ki, Ai ), , ( Kn, An )的指針，0 i n m；Ki 是關(guān)鍵字值，其中，Ai 是指向1 i n m。 Ki Ki+1, 1 i n。Ai 中所有的關(guān)鍵字值都小于Ki+1而大于Ki，0 i n。An 中所有的關(guān)鍵字值都大于Kn；A0 中的所有關(guān)鍵字值都小于 K1。Ai 也是 m -路查找樹，0 i n3-路查找樹每棵哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/

40、23Slide 5-595.7B-樹和B+樹（Cont.）B-樹：一棵 m 階B-樹是一棵 m-路查找樹，它或者是空樹，或者是滿足下列性質(zhì)的樹：樹中每個(gè)結(jié)點(diǎn)至多有m棵；(2m)根結(jié)點(diǎn)至少有 2 棵；m/2 m除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外，所有結(jié)點(diǎn)至少有 m/2 棵；所有的終端結(jié)點(diǎn)或葉子結(jié)點(diǎn)（失敗結(jié)點(diǎn)）都位于同一層。非B-樹B-樹F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-60 第5找 章 查5.735B-樹和B+樹（Cont.）B-樹示例1h 1查找失敗的結(jié)點(diǎn)(mi1)/(mhm1)h 0哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-61外結(jié)點(diǎn)葉子結(jié)點(diǎn)終端結(jié)點(diǎn)在同一

41、層上包含其結(jié)點(diǎn)的塊號(hào)5.7B-樹和B+樹（Cont.）B-樹高度h與關(guān)鍵字個(gè)數(shù) N 之間的關(guān)系設(shè) m 階B-樹的高為h，失敗結(jié)點(diǎn)位于第 h+1層，在這棵B-樹中關(guān)鍵字個(gè)數(shù) N 最小能達(dá)到多少？從B-樹的定義知,1層2層3層4層1 個(gè)結(jié)點(diǎn)至少 2 個(gè)結(jié)點(diǎn)至少 2 m / 2 個(gè)結(jié)點(diǎn)至少 2 m / 2 2 個(gè)結(jié)點(diǎn)如此類推，h 層 至少有2 m / 2 h-2個(gè)結(jié)點(diǎn)。上述的所有結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-625.7B-樹和B+樹（Cont.）設(shè) m若樹中關(guān)鍵字有 N 個(gè), 則失敗結(jié)點(diǎn)數(shù)為 N +1，即N +1 = 失敗結(jié)點(diǎn)數(shù) = 位于第 h+1

42、 層的結(jié)點(diǎn)數(shù) 2 m / 2h -1N 2 m / 2h-1-1反之，如果在一棵 m 階B-樹中有 N 個(gè)關(guān)鍵字，則h-1 log m / 2 ( N + 1 ) / 2 )例，若B-樹的階數(shù) m = 199，關(guān)鍵字總數(shù) N = 1999999，則 B-樹的高度 h 不超過log 199 / 2 (1999999 +1) / 2 ) + 1 =log100 1000000 +1= 4若B-樹的階數(shù) m = 3，高度 h = 4，則關(guān)鍵字總數(shù)至少為N = 2 3 / 2 4-1 1 =15哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-635.7B-樹的階m值的選擇B-樹和B+樹（

43、Cont.）如果提高B-樹的階數(shù) m，可以減少樹的高度，從而減少讀入結(jié)點(diǎn)的次數(shù)，因而可減少讀磁盤的次數(shù)。但是，m 受到內(nèi)存可使用空間的限制。當(dāng) m很大超出內(nèi)存工作區(qū)容量時(shí)，結(jié)點(diǎn)不能一次讀入到內(nèi)存，增加了讀盤次數(shù)，也增加了結(jié)點(diǎn)內(nèi)查找的難度。m值的選擇：應(yīng)使得在B-樹中找到關(guān)鍵字 x 的時(shí)間總量達(dá)到最小這個(gè)時(shí)間由兩部分組成：從磁盤中讀入結(jié)點(diǎn)所用時(shí)間在結(jié)點(diǎn)中查找 x 所用時(shí)間哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-645.7B-樹的查找操作B-樹和B+樹（Cont.）B-樹的查找過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找交替進(jìn)行的過程。因此，B-樹的查找時(shí)間與B-樹的階數(shù)m和 B-

44、樹的高度h直接有關(guān)，必須加以權(quán)衡。在B-樹上進(jìn)行查找，查找成功所需的時(shí)間取決于關(guān)鍵字值所在的層次；查找不成功所需的時(shí)間取決于樹的高度。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-655.7B-樹和B+樹（Cont.）B-樹的操作與建立B-樹的是從空樹起，逐個(gè)關(guān)鍵字而生成的。在B-樹，每個(gè)非失敗結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)都在 m/2 -1, m-1之間。操作，首先執(zhí)行查找操作以確定可以終端結(jié)點(diǎn) p；新關(guān)鍵字的如果在關(guān)鍵字后，結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)超出了上界m-1，則結(jié)點(diǎn)需要“”，否則可以直接。實(shí)現(xiàn)結(jié)點(diǎn)“字，當(dāng)再”的原則是：設(shè)結(jié)點(diǎn) p 中已經(jīng)有 m-1 個(gè)關(guān)鍵一個(gè)關(guān)鍵字后結(jié)點(diǎn)中的狀態(tài)為：( m

45、, A0, K1, A1, K2, A2, , Km, Am)其中 Ki Ki+1, 1 i 0, 1,2, ,B 1稱為散列函數(shù)（哈希函數(shù)，雜湊函數(shù)）0U散列函數(shù)hh(ki)kiKB1F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-83ri5.8 散列技術(shù)（Cont.）散列技術(shù)的相關(guān)概念數(shù)組 F 稱為散列表（Hash表，雜湊表）。數(shù)組 F 中的每個(gè)單元稱為桶(bucket)。對(duì)于任意關(guān)鍵字kU，函數(shù)值h ( k )稱為 k 的散列地址（Hash地址，散列值，地址，桶號(hào)）0U散列函數(shù)hh(k)k散列地址KB1F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-84數(shù)

46、組下標(biāo)散列表r5.8 散列技術(shù)（Cont.）散列技術(shù)的相關(guān)概念將結(jié)點(diǎn)（）按其關(guān)鍵字的散列地址到散列表中的(colli)（碰過程稱為散列。不同的關(guān)鍵字具有相同散列地址的現(xiàn)象稱為散列的兩個(gè)關(guān)鍵字稱為同義詞(synonym)。撞）。而發(fā)生0UKh(k )ikih(kj)kjB1F哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-85散列表r5.8 散列技術(shù)（Cont.）散列技術(shù)僅僅是一種查找技術(shù)嗎？散列既是一種查找技術(shù)，也是一種技術(shù)。散列是一種完整的散列只是通過結(jié)構(gòu)嗎？的關(guān)鍵字的值定位該，沒有表達(dá)記錄之間的邏輯關(guān)系，所以散列主要是面向查找的散列技術(shù)適用于何種場(chǎng)合？結(jié)構(gòu)通常用于實(shí)際出現(xiàn)的關(guān)

47、鍵字的數(shù)目遠(yuǎn)小于關(guān)鍵字所有可能取值的數(shù)量。散列技術(shù)適合于哪種類型的查找？不適用于允許多個(gè)有同樣關(guān)鍵字值的情況。也不適用于范圍查找，如在散列表中，找最大或最小關(guān)鍵值的，也不可能找到在某一范圍內(nèi)的。散列技術(shù)最適合回答的問題是：如果有的話，哪個(gè)鍵字的值等于待查值。的關(guān)哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-865.8 散列技術(shù)（Cont.）散列技術(shù)需解決的關(guān)鍵問題：散列函數(shù)的構(gòu)造。如何設(shè)計(jì)一個(gè)簡(jiǎn)單、均勻、的處理利用率高的散列函數(shù)如何采取合適的處理散列結(jié)構(gòu)上的查找、散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造的原則：方法來解決和刪除。計(jì)算簡(jiǎn)單：散列函數(shù)不應(yīng)該有很大的計(jì)算量，否則會(huì)降低查找效率。分

48、布均勻：散列函數(shù)值即散列地址，要盡量均勻分布在地址空間，這樣才能保證空間的有效利用并減少。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-875.8 散列技術(shù)（Cont.）散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法直接定址法散列函數(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，則散列表為：0123456789適用情況：事先知道關(guān)鍵字的值，關(guān)鍵字取值集合不是很大且連續(xù)性較好。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-881030

49、507080905.8 散列技術(shù)（Cont.）散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法質(zhì)數(shù)除余法散列函數(shù)為：h(key)=key%m一般情況下，選m為小于或等于表長(zhǎng)B的最大質(zhì)數(shù)。示例：關(guān)鍵字的取值集合為14, 21, 28, 35, 42, 49, 56, 63，表長(zhǎng)B=12。則選取m=11，散列函數(shù)為h(key)=key/11，則散列表為：345678910適用情況：質(zhì)數(shù)除余法是一種最簡(jiǎn)單、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-89563528215.8 散列技術(shù)（Cont.）散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法平方

50、取中法取 key2 的中間的幾位數(shù)作為散列地址擴(kuò)大相近數(shù)的差別，然后根據(jù)表長(zhǎng)取中間幾位作為散列值，使地址值與關(guān)鍵字的每一位都相關(guān)。散列地址的位數(shù)要根據(jù)B來確定，有時(shí)要設(shè)一個(gè)比例因子，限制地址越界。適用情況：事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-90keykey2HashA01000 010 000010I11001 210 000210J12001 440 000440I011601 370 400370P120614 310 541310P220624 314 704314Q121614 734 741734Q221624

51、741 304741Q321634 745 6517455.8 散列技術(shù)（Cont.）散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法折疊法若關(guān)鍵字位數(shù)較多，可根據(jù)B的位數(shù)將關(guān)鍵字分割成位數(shù)相同的若干段（最后一段位數(shù)可以不同），然后將各段疊加和(舍去進(jìn)位)作為散列地址。示例：58644220+0410088: 0-442-20586-45864022404左：移位疊加Hash( key ) = 0088右：間界疊加Hash( key ) = 6092+6092適用情況：關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-915.8 散列技術(shù)（Cont.）散列函

52、數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法數(shù)字分析法根據(jù)關(guān)鍵字值在各個(gè)位上的分布情況，選取分布比較均勻的若干位組成散列地址。示例：假設(shè)散列表長(zhǎng)為10010，可取中間四位中的兩位為散列地址。82242878481419 355適用情況：若事先知道關(guān)鍵字集合，且關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-925.8 散列技術(shù)（Cont.）散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造方法隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值作為散列地址Hash ( key ) = random( key )，即其中random是某個(gè)偽隨機(jī)函數(shù)，且函數(shù)值在0, , B-1之間。適用情況：通常

53、，當(dāng)關(guān)鍵字長(zhǎng)度不等時(shí)采用此法較恰當(dāng)小結(jié)：構(gòu)造Hash函數(shù)應(yīng)注意以下幾個(gè)問題：計(jì)算Hash函數(shù)所需時(shí)間關(guān)鍵字的長(zhǎng)度散列表的大小關(guān)鍵字的分布情況的查找頻率哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算簡(jiǎn)單分布均勻2010/12/23Slide 5-935.8 散列技術(shù)（Cont.）處理的方法開放定址法基本當(dāng)：發(fā)生時(shí)，使用某些探測(cè)技術(shù)在散列表中形成一個(gè)探列，沿此序列逐個(gè)單元查找，直到找到給定的關(guān)鍵字或者碰到一個(gè)開放地址（即該空的地址單元、空桶）或者既未找到給定的關(guān)鍵字也沒碰到一個(gè)開放地址為止。常用的探測(cè)技術(shù)如何尋找下一個(gè)空的散列地址?線性探測(cè)法線性補(bǔ)償探測(cè)法二次探測(cè)法隨機(jī)探測(cè)法閉散列表：用開放定址法處理得到的散列表

54、叫閉散列表.哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-945.8 散列技術(shù)（Cont.）處理的方法-開放定址法線性探測(cè)法(c=1)基本：當(dāng)發(fā)生時(shí)，從位置的下一個(gè)位置起，依次尋找空的散列地址。列：設(shè)關(guān)鍵字值key的散列地址為h(key)，閉散列表的探長(zhǎng)度為B，則發(fā)生時(shí)，尋找下一個(gè)散列地址的公式為：hi=(h(key)di) % B（di=1，2，m-1）示例：關(guān)鍵字取值集合為 47, 7, 29, 11, 16, 92, 22, 8, 3，散列函數(shù)為h(key)=key %11，用線性探測(cè)法處理，則散列表為：01234567893293堆積現(xiàn)象：在處理的過程中出現(xiàn)的非同義詞之

55、間對(duì)同一個(gè)散列地址爭(zhēng)奪的現(xiàn)象。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-95114792375.8 散列技術(shù)（Cont.）處理的方法開放定址法線性補(bǔ)償探測(cè)法：當(dāng)發(fā)生式為：時(shí)，尋找下一個(gè)散列地址的公hi=(h(key)di) % B（di=1c，2c，）二次探測(cè)法:當(dāng)發(fā)生時(shí)，尋找下一個(gè)散列地址的公式為：hi=(h(key)di) % B（di=12，12，22，22，q2，q2且qB/2）隨機(jī)探測(cè)法：當(dāng)發(fā)生時(shí)，下一個(gè)散列地址的位移量是一個(gè)隨機(jī)數(shù)列，即尋找下一個(gè)散列地址的公式為：hi=(h(key)di) % B（其中，d1, d2, ,dB-1是1, 2, , B-1的隨機(jī)序列。）注意：、刪除和查找時(shí)，要使用同一個(gè)隨機(jī)序列。哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-965.8 散列技術(shù)（Cont.）處理的方法-開放定址法-線性探測(cè)法(c=1)的的實(shí)現(xiàn)查找算法實(shí)現(xiàn)結(jié)構(gòu)定義struct recordskeytypekey;fields other;typedef records HASHB; Search算法的實(shí)現(xiàn) Insert算法的實(shí)現(xiàn)Delete算法的實(shí)現(xiàn)哈工大計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2010/12/23Slide 5-97Search(keytype k, HASH F)locate= h(k),rehash=0; wh