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

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

2、分）查找分塊查找BST-二叉查找樹AVL樹B-樹與B+樹散列技術(shù)5.15.25.35.45.55.65.75.8本章小結(jié)2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-4 第5章 查找5.1 基本概念和術(shù)語查找表：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合(文件)。 關(guān)鍵字：可以標(biāo)識一個記錄的某個數(shù)據(jù)項或數(shù)據(jù)項組合。 鍵值：關(guān)鍵字的取值。主關(guān)鍵字：可以唯一地標(biāo)識一個記錄的關(guān)鍵字。 次關(guān)鍵碼：不能唯一地標(biāo)識一個記錄的關(guān)鍵字。查找：在查找表中找出（確定）一個關(guān)鍵字值等于給定值的 數(shù)據(jù)元素（或記錄）。查找結(jié)果：若在查找集合中找到了與給定值相匹配的數(shù)據(jù)元 素記錄，則稱查找成功；否則，稱

3、查找失敗。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-5學(xué)號姓名性別年齡入學(xué)成績0001張亮男196250002張亮女286170003劉楠女19623 第5章 查找5.1 基本概念和術(shù)語（Cont.）查找的分類：根據(jù)查找方法取決于記錄的鍵值還是記錄的存儲位置？ 基于關(guān)鍵字比較的查找順序查找、折半查找、分塊查找、BST&AVL、B-樹 和B+樹基于關(guān)鍵字存儲位置的查找散列法根據(jù)被查找的數(shù)據(jù)集合存儲位置內(nèi)查找：整個查找過程都在內(nèi)存進行；外查找：若查找過程中需要訪問外存，如B-樹和B+樹2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-6 第5章

4、查找5.1 基本概念和術(shù)語（Cont.）查找的分類：根據(jù)查找方法是否改變數(shù)據(jù)集合？ 靜態(tài)查找：查找+提取數(shù)據(jù)元素屬性信息被查找的數(shù)據(jù)集合經(jīng)查找之后并不改變，就是說，既 不插入新的記錄，也不刪除原有記錄。動態(tài)查找：查找+（插入或刪除元素）被查找的數(shù)據(jù)集合經(jīng)查找之后可以改變，就是說，可 以插入新的記錄，也可以刪除原有記錄。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-7 第5章 查找5.1 基本概念和術(shù)語（Cont.）查找表的操作SEARCH（k ，F(xiàn)）：在數(shù)據(jù)集合(查找表、文件) F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則返回包含 k 的記錄的位置；否則，

5、返回一個特定的值。INSERT（R，F(xiàn) ）：在動態(tài)環(huán)境下的插入操作。在F 中查找記錄 R，若查找不成功，則插入R；否則不插入R。DELETE(k，F(xiàn))：在動態(tài)環(huán)境下的刪除操作。在 F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則刪除關(guān)鍵字值等 于k 的記錄，否則不刪除任何記錄。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-8 第5章 查找5.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ù)、折半查

6、找技術(shù)。樹表：靜態(tài)和動態(tài)查找均適用，主要采用BST和AVL的 查找技術(shù)。散列表：靜態(tài)和動態(tài)查找均適用，主要采用散列技術(shù)。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-9 第5章 查找5.1 基本概念和術(shù)語（Cont.）查找表結(jié)點（數(shù)據(jù)元素、記錄）的類型定義：structrecordskeytypekey;fields other;查找的性能查找算法時間性能由關(guān)鍵字的比較次數(shù)來度量。同一查找集合、同一查找算法，關(guān)鍵字的比較次數(shù)與哪些 因素有關(guān)呢？查找算法的時間復(fù)雜度是問題規(guī)模n和待查關(guān)鍵字在查找 集合中的位置k的函數(shù)，記為T(n，k)。2010/12/23哈工大計算機科學(xué)與

7、技術(shù)學(xué)院 張巖Slide 5-10 第5章 查找5.1 基本概念和術(shù)語（Cont.）查找的性能平均查找長度：把給定值與關(guān)鍵字進行比較的次數(shù)的期望值稱為查找算法在查找成功時的平均查找長度-ASL(Average Length)。Search計算公式：假設(shè)查找集合中的記錄個數(shù)pi為查找表中第i 個記錄的概率，pi=1，ci為查找第i 個記錄所進行的n比較次數(shù)，則åpcASL =iii=1在等概率情況下，即pi = 1/n時，n 1 nåc=ASL =ii=12010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-11 第5章 查找5.2線性查找線性（順序）查找基本思

8、想：從線性表的一端開始，順序掃描線性表，依次將掃描到的 結(jié)點關(guān)鍵字與給定值K相比較。若當(dāng)前掃描到的結(jié)點關(guān)鍵字與k相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于k的結(jié)點，則查找失 敗。線性（順序）查找對存儲結(jié)構(gòu)要求既適用于線性表的順序存儲結(jié)構(gòu)適用于靜態(tài)查找也適用于線性表的鏈式存儲結(jié)構(gòu)也適用于動態(tài)查找2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-12 第5章 查找5.2線性查找（Cont.）順序表上的查找適合于靜態(tài)查找順序表的類型定義typedefrecords LISTMaxSize ;LISTF ;SEARCH操作的實現(xiàn)：k=350123456789FiiiiiINS

9、ERT操作的實現(xiàn)DELETE操作的實現(xiàn)不適合順序表2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-13哨兵35109855 第5章 查找5.2 基本概念和術(shù)語（Cont.）intSEARCH (keytypek, int last, LISTF )/* 在F1Flast中查找關(guān)鍵字為k的記錄，若找到，則返回該記錄所在的下表，否則返回 0 */inti ;F0.key = k ;i = last ;/* F0為偽記錄或哨兵 */while ( Fi.key !=i = i 1 ; return i ;k )/*時間復(fù)雜度 O( n ) ；ASL成功=(n+1)/2,ASL失敗

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

11、k 的記錄，返回其指針*/LIST p =F ;while ( p! = NULL )if ( p->data.key = k ) return p ;elsep = p->next ; return p ; 第5章 查找5.3折半查找折半查找（也稱二分查找）的要求：查找表（被查找的數(shù)據(jù)集合）必須采用順序式存儲結(jié)構(gòu)； 查找表中的數(shù)據(jù)元素（記錄）必須按關(guān)鍵字有序。1234567891011FF0.key £ F1.key £ F2.key £ £ Flast.key或 F0.key ³ F1.key ³ F2.key

12、79; ³ Flast.key注意：折半查找只適合于靜態(tài)查找！2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-160513192137566475808892 第5章 查找5.3折半查找（Cont.）折半查找的基本思想：在有序表中，取中間記錄作為比較對象，若給定值與中間 記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄 的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大 于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。 不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記 錄，查找失敗。k k1 kmid-1 rmid kmid+1 kn 如果k<kmid

13、 查找左半?yún)^(qū)如果k>kmid 查找右半?yún)^(qū)2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-17（mid=(1+n)/2） 第5章 查找5.3折半查找的示例：折半查找（Cont.）1234567891011k = 21Flow=1low=1mid=6up=5up=11mid=3low=mid=4 up=51234567891011k = 85Flow=1mid=6up=11low=7mid=9up=11low=mid=10 up=11low=10 up=92010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-1805131921375664758088920

14、513192137566475808892 第5章 查找5.3折半查找（Cont.）折半查找的非遞歸算法實現(xiàn)步驟1. 初態(tài)化：令low ,up分別表示查找范圍的上、下界，初始時low = 0, up = last;2. 折半：令mid = (low+up)/2，取查找范圍中間位置元素下標(biāo);3. 比較：k與Fmid.key3.1 若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key > k，low不變，調(diào)整up = mid - 1， 查找范圍縮小一半；3.3 若Fmid.key < k，調(diào)整low = mid + 1，up不變， 查找范圍縮小一半；4. 重復(fù)

15、2 3 步。當(dāng)low > up 時，查找失敗，返回 0。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-19 第5章 查找5.3折半查找（Cont.）折半查找的非遞歸算法實現(xiàn)intBinSearch1(keytype int low , up , mid ; low = 1 ; up = last ;while ( low <= up ) k, LIST F )mid = ( low + up ) / 2 ; if ( Fmid.key = = k ) else if (Fmid.key > k)elsereturnmid ;up = mid 1 ;low

16、 = mid + 1 ;return 0; /* F必須是順序有序表(此處為增序);時間復(fù)雜度 :O(log2 n)*/2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-20 第5章 查找5.3折半查找（Cont.）折半查找的遞歸算法實現(xiàn)步驟1. 初態(tài)化：設(shè)置查找范圍的上界up和下界low;2. 測試查找范圍：如果low > up，則查找失??；否則，3.取查找范圍中間位置元素下標(biāo)令mid = (low+up)/2；比較k與Fmid.key：3.1 若Fmid.key = k，查找成功，返回 mid;3.2 若Fmid.key > k，遞歸地在左半部分查找（low不

17、變，調(diào)整up = mid 1）；3.3 若Fmid.key < k，遞歸地在右半部分查找（調(diào)整low = mid + 1，up不變。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-21 第5章 查找5.3折半查找（Cont.）折半查找的遞歸算法實現(xiàn)int BinSearch2(LIST F, int low, int up, keytype k )if (low>up) return 0; else mid=(low+up)/2;if (k < Fmid.key )return BinSearch2(F, low, mid-1, k); else if (

18、k>Fmid.key)return BinSearch2(F, mid+1, up, k); else return mid; /* F必須是順序有序表(此處為增序);時間復(fù)雜度 :O(log2 n)*/2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-22 第5章 查找5.3折半查找的判定樹：折半查找（Cont.）折半查找的過程可以用二叉樹來描述，樹中的每個結(jié)點對應(yīng)有序表中的一個記錄，結(jié)點的值為該記錄在表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定 樹，簡稱判定樹。折半查找的判定樹的構(gòu)造當(dāng)n=0時，折半查找判定樹為空；當(dāng)n0時，折半查找判定樹的根結(jié)點是有

19、序表中序號為mid=(n+1)/2的記錄，根結(jié)點的左子樹是與有序表F1 Fmid-1相對應(yīng)的折半查找判定樹，根結(jié)點的右子樹是與Fmid+1 Fn相對應(yīng)的折半查找判定樹。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-23 第5章 查找5.3折半查找（Cont.）1234567891011判定樹的構(gòu)造F6397141082511外部結(jié)點-失敗結(jié)點內(nèi)部結(jié)點-查找成功2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-241110118978564523129106734 10513192137566475808892 第5章 查找5.3折半查找（Cont.）折半

20、查找的ASL若有n個關(guān)鍵字，則判定樹的失敗結(jié)點數(shù)為n+1個ASL成功=（1*1+2*2+3*4+4*4）/11 = 25/11 ASL失敗=（3*4+4*8）/12 = 44/126397141082511112010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-2510118978564523129106734 1 第5章 查找5.3折半查找（Cont.）折半查找的判定樹高度nASLbs= pi · ci/* pi=1/n */ h/*S=2S - S*/i=1h1= 1/n · j · 2j-1j= (n+1)/n·log2(n+1)-

21、125當(dāng)n 很大時，ASLbs log2(n+1)-1作為查找成功時的平均查找長度。在查找不成功和最壞情況下查找成功所需關(guān)鍵字的比較次數(shù) 都不超過判定樹的高度。因為判定樹的中度小于2 的結(jié)點只能出現(xiàn)在下面兩層上，所以n 個結(jié)點的判定樹高度和n 個結(jié)點的完全二叉樹的高度相同，即élog2(n+1)ù 。由此可見，折半查找的最壞性能與平均性能相當(dāng)接近。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-26 第5章 查找5.4分塊查找線性查找+折半查找分塊查找的基本思想均勻分塊，塊間有序，塊內(nèi)無序：首先將表中的元素均勻 地分成若干塊，每一塊中的元素的任意排列，而

22、各塊之間 要按順序排列；若按從小到大的順序排列，則第一塊中的所有元素的關(guān)鍵字都小于第二塊中的所有元素的關(guān)鍵字，第二塊中的所有元素的關(guān)鍵字都小于第三塊中的所有元素的關(guān)鍵字，如此等等等。建塊索引:然后再建一個線性表，用以存放每塊中最大(或 最小)的關(guān)鍵字，此線性表稱為索引表，它是一個有序表.012224474索引表IX01234567891011121314F2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-272212139833424438244860587447 第5章 查找5.4分塊查找（Cont.）分塊查找算法的要點：假設(shè)在帶索引的線性表中查找已知關(guān) 鍵字為k 的記錄，

23、則首先查找索引表，確定k 可能出現(xiàn)的塊號； 然后到此塊中進行進行順序查找。算法的實現(xiàn)typedeftypedefrecords LISTmaxsize ;/* 線性表主表 */keytype INDEXmaxblock ;/* 線性表索引表*/012224474索引表IX01234567891011121314F2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-282212139833424438244860587447 第5章 查找5.4分塊查找（Cont.）intindex_search(keytype k, int last, int blocks, INDEX ix,

24、 LIST F, int L )inti =0, j ;while ( k > ixi)&&( i < blocks) /*查索引表,確定k 所在塊i*/i+ ;if( i<blocks ) j = i*L;/* 第i 塊的起始下標(biāo) */while( k != Fj.key )&&( j <= (i+1)*L-1 )&&( j < last )j = j + 1 ;if ( k = F j .key ) returnj ; /* 查找成功 */return1 ; /* 查找失敗 */ 2010/12/23哈工大計算機

25、科學(xué)與技術(shù)學(xué)院 張巖Slide 5-29 第5章 查找5.4分塊查找性能分析分塊查找（Cont.）設(shè)長度為n 的表分成b 塊，每塊長度為L， 則b = én / Lù， 又設(shè)表中每個元素的查找概率相等，則每塊查找的概率為1/b，塊中每個元素的查找概率為1/L。于是，bb= p · c =1 i索引表的ASLixiib i=1i=1LL1塊內(nèi)的平均查找長度： ASL=p · c = jj=1blkiiLj=1所以分塊查找平均長度為：ASL(L)=ASLix+ ASLblk = (b+1)/2+(L+1)/2=(n/L+L)/2+1令A(yù)SL(L)=0，知當(dāng)L

26、= n 時，ASL(L) = n +1 （最小值）。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-30 第5章 查找5.4分塊查找（Cont.）分塊查找局限性和改進只適合靜態(tài)查找； 改進：在索引表中保存各塊的下標(biāo)范圍，此時不必均勻分塊 各塊存放在不同的向量（一維數(shù)組）中；把同一塊中的元素組織成一個鏈表。動態(tài)環(huán)境的分塊查找?guī)饕淼逆湵硭惴ǖ膶崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)定義三個算法的實現(xiàn) IX2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-317448444233224474181222 第5章 查找5.5二叉查找樹BST二叉查找樹二叉搜索樹、二叉分類（排序）樹二叉查找

27、樹或者是空樹，或者是滿足下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的關(guān)鍵字的值 都小于根結(jié)點關(guān)鍵字的值；若它的右子樹不空，則右子樹上所有結(jié)點的關(guān)鍵字的值 都大于根結(jié)點關(guān)鍵字的值；它的左、右子樹本身又是一個二叉查找樹。10516718152010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-32 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的結(jié)構(gòu)特點：任意一個結(jié)點的關(guān)鍵字，都大于(小于)其左(右)子樹中任 意結(jié)點的關(guān)鍵字，因此各結(jié)點的關(guān)鍵字互不相同按中序遍歷二叉查找樹所得的中序序列是一個遞增的有序 序列，因此，二叉查找樹可以把無序序列變?yōu)橛行蛐蛄?。同一個

28、數(shù)據(jù)集合，可按關(guān)鍵字表示成不同的二叉查找樹， 即同一數(shù)據(jù)集合的二叉查找樹不唯一；但中序序列相同。10516718152010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-33 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的結(jié)構(gòu)特點：每個結(jié)點X的右子樹的最左結(jié)點Y，稱為X的繼承結(jié)點。有如 下性質(zhì)：(1)在此右子樹中，其關(guān)鍵字值最小，但大于X的關(guān)鍵字(2)最多有一個右子樹，即沒有左子樹。二叉查找樹的存儲結(jié)構(gòu)：10typedef struct celltype5recordsdata ;struct celltype *lchild,*rchild ; BSTNode；

29、typedefBSTNode* BST ;162010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-34 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的查找操作：在F 中查找關(guān)鍵字為k 的記錄如下： 若F = NULL，則查找失??；否則，k =F->data.key，則查找成功；否則，k < F->data.key，則遞歸地在F 的左子樹查找k；否則k > F->data.key，則遞歸地在F 的右子樹查找k。103182010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-35 第5章 查找5.5二叉查找樹BST （Con

30、t.）二叉查找樹的查找操作：BSTNode * SearchBST( keytypek, BSTF )BSTNode * p = F ;if ( p = NULL | k = p->data.key ) /* 遞歸終止條件 */returnp;if ( k < p->data.key ) return ( SearchBST ( k,elsereturn ( SearchBST ( k,p->lchild ) ) ; /* 查找左子樹 */p->rchild ) ) ; /* 查找右子樹 */2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-36

31、 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的插入操作若二叉排序樹為空樹，則新插入的結(jié)點為根結(jié)點；否則，新插入的結(jié)點必為一個新的葉結(jié)點.新插入的結(jié)點一定是查找不成功時，查找路徑上最后一個結(jié)點的左兒子或右兒子。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 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 < F->da

32、ta.key )InsertBST( R , F->lchild )； elseif ( R.key > F->data.key )InsertBST( R , F->rchild ); /若R.key=F->data.key,則返回 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的建立BST CreateBST ( void )注意：在建立二叉查找樹時，若按關(guān)鍵字有序順序輸入各記錄，則產(chǎn)生退化的二叉查找樹單鏈表BST F = NULL; /*初始時F為空*/keytypekey;cin>>key>>其他字段;/*讀入一個記錄

33、*/while( key ) /*假設(shè)key=0是輸入結(jié)束標(biāo)志*/ InsertBST( R , F )；/* 插入記錄R */ cin>>key>>其他字段 ;/*讀入下個記錄*/如何防止？隨機輸入各結(jié)點 在建立、插入和刪除各結(jié)點過程中平衡相關(guān)結(jié)點的左、右子樹。returnF;/*返回建立的二叉查找樹的根*/2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-38 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作刪除某結(jié)點，并保持二叉排序樹特性，分三種情況處理：1） 如果刪除的是葉結(jié)點，則直接刪除；2） 如果刪除的結(jié)點只有一株左子

34、樹或右子樹，則直接繼 承：將該子樹移到被刪結(jié)點位置；3） 如果刪除的結(jié)點有兩株子樹，則用繼承結(jié)點代替被刪結(jié)點，這相當(dāng)于刪除繼承結(jié)點按 1) 或 2) 處理繼承結(jié)點。10516718152010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-39 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作的實現(xiàn)步驟1. 若結(jié)點p是葉子，則直接刪除結(jié)點p；2. 若結(jié)點p只有左子樹，則只需重接p的左子樹； 若結(jié)點p只有右子樹，則只需重接p的右子樹；3. 若結(jié)點p的左右子樹均不空，則3.1 查找結(jié)點p的右子樹上的最左下結(jié)點s及其雙親結(jié)點par；3.2 將結(jié)點s數(shù)據(jù)域替換到被刪結(jié)

35、點p的數(shù)據(jù)域；3.3 若結(jié)點p的右孩子無左子樹，則將s的右子樹接到par的右子樹上；否則，將s的右子樹接到結(jié)點par的左子樹上；3.4 刪除結(jié)點s；2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-40 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的刪除操作的實現(xiàn)void DeleteB( keytype k, BST &F )recordsdeletemin(BST&F ) if ( F != NULL )records tmp ; BSTp ;if ( k < F->data.key ) DeleteB( k, f->lc

36、hild ) ;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

37、 ;elsereturn(deletemin( F->lchild) ;2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-41 第5章 查找5.5二叉查找樹BST （Cont.）二叉查找樹的查找性能二叉排序樹的查找性能取決于二叉排序樹的形態(tài)，在O(log2n)和O(n)之間。在最壞情況下，二叉查找樹是通過把有序表的n 個結(jié)點依次插入而生成的，此時所得到的二叉查找樹退化為一株高 度為n 的單支樹，它的平均查找長度和單鏈表上的順序查找相同，(n+1)/2。在最好情況下，二叉查找樹的形態(tài)比較均勻，最終得到一 株形態(tài)與折半查找的判定樹相似，此時的平均查找長度約 為log2 n。

38、二叉查找樹的平均高度為O(log2 n)。因此平均情況下，三種操作的平均時間復(fù)雜性為O(log2 n)就平均性能而言，二叉查找樹上的查找和二分查找差不多 就維護表的有序性而言，二叉查找樹更有效。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-42 第5章 查找5.6AVL樹AVL樹（Balanced Binary Tree or Height-Balanced Tree）AVL樹或者是空二叉樹，或者是具有如下性質(zhì)的BST： 根結(jié)點的左、右子樹高度之差的絕對值不超過1； 且根結(jié)點左子樹和右子樹仍然是AVL樹。結(jié)點的平衡因子BF（Balanced Factor）一個結(jié)點的左子樹

39、與右子樹的高度之差。-1 11AVL樹中的任意結(jié)點的BF只可能是-1，0和1。0+1AVL樹的ASL可保持在O(log2n)AVL樹的查找操作與BST的相同000000162010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-43 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）向AVL樹插入結(jié)點可能造成不平衡，此時要調(diào)整樹的結(jié)構(gòu)，使之重新達到平衡我們希望任何初始序列構(gòu)成的二叉樹都是AVL樹示例：假設(shè)25，27，30，12，11，18，14，20，15，22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。127027-125025-225RR旋轉(zhuǎn)030030125025-1

40、270270120302010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-44 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。227127127LL旋轉(zhuǎn)0110030227030030225012125025112012011-13012LR旋轉(zhuǎn)1250110182010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-45 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，

41、22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。227030-112LR旋轉(zhuǎn)1250112010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-46-12700111830 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。025125125-127-127-127012-112-1120300300300180180111180110110200140142010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-47 第5章 查找5.6AVL樹的平衡化處

42、理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。225RL旋轉(zhuǎn)-127-212030118011020-1140152010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-481250-1122710011143012020 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）示例：假設(shè)25，27，30，12，11，18，14，20，15，22是 一關(guān)鍵字序列，并以上述順序建立AVL樹。LR旋轉(zhuǎn)-1225-1140-1112-10110222010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張

43、巖Slide 5-4925182714203010121522142510 -1-111120001122 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）在一棵AVL樹上插入結(jié)點可能會破壞樹的平衡性，需要平 衡化處理恢復(fù)平衡，且保持BST的結(jié)構(gòu)性質(zhì)。若用Y表示新插入的結(jié)點，A表示離新插入結(jié)點Y最近的， 且平衡因子變?yōu)?#177;2的祖先結(jié)點?？梢杂?種旋轉(zhuǎn)進行平衡化處理: LL型：新結(jié)點Y 被插入到 A 的左子樹的左子樹上（順） RR型：新結(jié)點Y 被插入到 A 的右子樹的右子樹上（逆） LR型：新結(jié)點Y 被插入到 A 的左子樹的右子樹上（逆、順） RL型：新結(jié)點Y 被插入到 A

44、的右子樹的左子樹上（順、逆）2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-50 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）LL型：新結(jié)點Y 被插入到 A 的左子樹的左子樹上（順）B0A+ 2A+ 10 ACDBBC+ 10DECEED(c) 右向旋轉(zhuǎn)后的AVL樹(b) D子樹中插入結(jié)點(a)AVL樹2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-51hhhhhh+1hh+1h 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）RR型：新結(jié)點Y 被插入到 A 的右子樹的右子樹上（逆）C0AA-1-2A0EBCB0-1CEBDD

45、ED(c)左向旋轉(zhuǎn)后的AVL樹(b)E子樹中插入結(jié)點(a)AVL樹2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院張巖Slide 5-52hhhhhh+1hh+1h 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）LR型：新結(jié)點Y 被插入到 A 的左子樹的右子樹上(逆,順)AA+ 20ECC-1ABEBDGEDFGC+1BFFGD插入(b)繞E，將B逆時針轉(zhuǎn)后(c)繞E，將A順時針轉(zhuǎn)后(a)F子樹插入結(jié)點高度變?yōu)閔2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-53hhh-1hhh-1hhhh-1hh 第5章 查找5.6AVL樹的平衡化處理AVL樹（Cont.）R

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

47、行平衡化的過程2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-55 第5章 查找5.6AVL樹的刪除操作AVL樹（Cont.）刪除操作與插入操作是對稱的（鏡像），但可能需要的平衡化次數(shù)多。因為平衡化不會增加子樹的高度，但可能會減少子樹的高 度。在有可能使樹增高的插入操作中，一次平衡化能抵消掉樹 增高；而在有可能使樹減低的刪除操作中，平衡化可能會帶來祖 先結(jié)點的不平衡。2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-56 第5章 查找5.6AVL樹的性能分析AVL樹（Cont.）令Nh是高為h的AVL樹中結(jié)點個數(shù)的最小值，在最稀疏情 況下，這棵AVL樹的一

48、棵子樹的高度為h1，而另一棵子 樹的高度為h2，這兩棵子樹也都是AVL樹。因此， 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個結(jié)點的AVL樹，其高度h至多為log(n+1)2因此，對于包含n個結(jié)點的AVL樹，其最壞情況下的插入 時間為O(log n)2010/12/23哈工大計算機科學(xué)與技術(shù)學(xué)院 張巖Slide 5-57 第5章 查找5.7B-樹和B+樹（Cont.）當(dāng)符號表的大小超過內(nèi)存容量時，由于必須從磁盤等輔助存 儲設(shè)備上去