2022-02巖數(shù)據結構講義第5章查找2010秋

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

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

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

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

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

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

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

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

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

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

11、折半查找的基本：在有序表中，取中間作為比較對象，若給定值與中間的關鍵碼相等，則查找成功；若給定值小于中間的關鍵碼，則在中間的左半區(qū)繼續(xù)查找；若給定值大于中間的關鍵碼，則在中間的右半區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。k k1 kmid-1 rmid kmid+1 kn 如果kkmid查找右半區(qū)哈工大計算機科學與技術學院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哈工大計算機科學與技術學院2010/12/23Slide 5-185.3折半查找（Cont.）折半查找的非遞歸算法實現(xiàn)步驟初態(tài)化：令low ,up分別表示查找范圍的上、下界，初始時low = 0, up = last;折半：令mid = (low+up)/2，取查找范圍中間位置元素下標;比較：k與Fmid.key若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key k，low不變，調整up = mid - 1，查找范圍縮小一半；3.3 若Fmid.key up 時，查找失

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

14、和下界low;測試查找范圍：如果low up，則查找失??；否則，3.取查找范圍中間位置元素下標令mid = (low+up)/2；比較 k與Fmid.key：3.1 若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key k，遞歸地在左半部分查找（low不變，調整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必須是順序有序表(此處為增序);時間復雜度 :(lo

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

16、.3折半查找（Cont.）判定樹的構造F693714108251111外部結點-失敗結點內部結點-查找成功哈工大計算機科學與技術學院2010/12/23Slide 5-2410118978564523129106734 15.3折半查找（Cont.）折半查找的ASL若有n個關鍵字，則判定樹結點數(shù)為n+1個ASL成功=（1*1+2*2+3*4+4*4）/11 = 25/11ASL失敗=（3*4+4*8）/12 = 44/12693714108251111Slide 5-25哈工大計算機科學與技術學院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當n 很大時，ASLbs log2(n+1)-1作為查找成功時的平均查找長度。在查找不成功和情況下查找成功所需關鍵字的比較次數(shù)都不超過判定樹的高度。因為判定樹的中度小于2 的結點只能出現(xiàn)在下面兩層上，所以n 個結點的判定樹高度和n 個結點的完全二叉樹的高度相同，即log2(n+1) 。由此可見，折半查找的能相當接近。性能與平均性哈工大計算機科學與技術學院2010/12/23Slide 5-265.4分塊查找線性查找+折

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

19、ont.）分塊查找算法的要點：假設在帶索引的線性表中查找已知關鍵字為k 的，則首先查找索引表，確定k 可能出現(xiàn)的塊號；然后到此塊中進行進行順序查找。算法的實現(xiàn)typedeftypedefrecords LISTmaxsize ;/* 線性表主表 */keytypeINDEXmaxblock ;/* 線性表索引表*/012索引表224474IX01234567891011121314F哈工大計算機科學與技術學院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 塊的起始下標 */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哈工大計算機科學與技術學院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 ) ) ; /* 查找右*/哈工大計算機科學與技術學院2010/12/23Slide 5-365.5二叉查找樹的二叉查找樹BST （Cont.）操作若二叉排序樹為空樹，則新根結點；否則，

22、新的結點為的結點必為一個新的葉結點.的結點一定是查找新不成功時，查找路徑上最后一個結點的左兒子或右兒子。哈工大計算機科學與技術學院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 )注意：在建立二叉查找樹時，若按關鍵字有序順序BST F = NULL; /*初始時F為空*/輸入各，則keytypekey;產生的二叉cinkey其他字段;/*讀入一個*/查找樹單鏈表while( key ) /*假設key=0是輸入結束標志*/如何防止？隨機輸入各結點InsertBST( R , F )；/*R */cinkey其他字段 ;/*讀入下個*/在建立、和刪return除各結點過程中平衡相關結點的F;/*返回建立的二叉查找樹的根*/左

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

25、點p只有右若結點p的左右樹，則只需重接p的，則只需重接p的右不空，則樹；3.1 查找結點p的右上的最左下結點s及其雙親結點par；3.2 將結點s數(shù)據域替換到被刪結點p的數(shù)據域；3.3 若結點p的右孩子無樹，則將s的右接到par的右上；否則，將s的右3.4 刪除結點s；接到結點par的樹上；哈工大計算機科學與技術學院2010/12/23Slide 5-405.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作的實現(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) ;哈工大計算機科學與技術學院2010/12/23Slide 5-415.5二叉查找樹BST （Cont.）二叉查找樹的查找性能二叉排序樹的查找性能取決于二叉排序樹的形態(tài)，在O(log2n)和O(n)之間。在次情況下，二叉查找樹是通過把有序表的n 個結點依而生成的，此時所得到的二叉查找樹為一株高度為n 的單支樹，它的平均查找長度和單鏈表上的順序查找相同，(n+1)/2。在最好情況下，二叉查找樹的形態(tài)比較均勻，最終得到一株形態(tài)與折半查找的判定樹相似，此時的平均查找長度約為log2 n。二叉查找樹的平均高度為O(log2 n)。因此平均情況下，三種操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、樹的高度h直接有關，必須加以權衡。在B-樹上進行查找，查找成功所需的時間取決于關鍵字值所在的層次；查找不成功所需的時間取決于樹的高度。哈工大計算機科學與技術學院2010/12/23Slide 5-655.7B-樹和B+樹（Cont.）B-樹的操作與建立B-樹的是從空樹起，逐個關鍵字而生成的。在B-樹，每個非失敗結點的關鍵字個數(shù)都在 m/2 -1, m-1之間。操作，首先執(zhí)行查找操作以確定可以終端結點 p；新關鍵字的如果在關鍵字后，結點中的關鍵字個數(shù)超出了上界m-1，則結點需要“”，否則可以直接。實現(xiàn)結點“字，當再”的原則是：設結點 p 中已經有 m-1 個關鍵一個關鍵字后結點中的狀態(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哈工大計算機科學與技術學院2010/12/23Slide 5-83ri5.8 散列技術（Cont.）散列技術的相關概念數(shù)組 F 稱為散列表（Hash表，雜湊表）。數(shù)組 F 中的每個單元稱為桶(bucket)。對于任意關鍵字kU，函數(shù)值h ( k )稱為 k 的散列地址（Hash地址，散列值，地址，桶號）0U散列函數(shù)hh(k)k散列地址KB1F哈工大計算機科學與技術學院2010/12/23Slide 5-84數(shù)

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

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

48、布均勻：散列函數(shù)值即散列地址，要盡量均勻分布在地址空間，這樣才能保證空間的有效利用并減少。哈工大計算機科學與技術學院2010/12/23Slide 5-875.8 散列技術（Cont.）散列函數(shù)的構造散列函數(shù)的構造方法直接定址法散列函數(shù)是關鍵字值的線性函數(shù)，即：h(key) = a key + b（a，b為常數(shù)）示例：關鍵字的取值集合為10, 30, 50, 70, 80, 90，選取的散列函數(shù)為h(key)=key/10，則散列表為：0123456789適用情況：事先知道關鍵字的值，關鍵字取值集合不是很大且連續(xù)性較好。哈工大計算機科學與技術學院2010/12/23Slide 5-881030

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

50、取中法取 key2 的中間的幾位數(shù)作為散列地址擴大相近數(shù)的差別，然后根據表長取中間幾位作為散列值，使地址值與關鍵字的每一位都相關。散列地址的位數(shù)要根據B來確定，有時要設一個比例因子，限制地址越界。適用情況：事先不知道關鍵碼的分布且關鍵碼的位數(shù)不是很大哈工大計算機科學與技術學院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 散列技術（Cont.）散列函數(shù)的構造散列函數(shù)的構造方法折疊法若關鍵字位數(shù)較多，可根據B的位數(shù)將關鍵字分割成位數(shù)相同的若干段（最后一段位數(shù)可以不同），然后將各段疊加和(舍去進位)作為散列地址。示例：58644220+0410088: 0-442-20586-45864022404左：移位疊加Hash( key ) = 0088右：間界疊加Hash( key ) = 6092+6092適用情況：關鍵碼位數(shù)很多，事先不知道關鍵碼的分布。哈工大計算機科學與技術學院2010/12/23Slide 5-915.8 散列技術（Cont.）散列函

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

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

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

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