數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（第二版）課件 第8章 查找

第八章查找西安科技大學(xué)計(jì)算機(jī)學(xué)院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)第八章查找

現(xiàn)在數(shù)據(jù)存儲(chǔ)量一般很大，為了在大量信息中找到所需信息，就需用到查找技術(shù)。查找是對(duì)查找表進(jìn)行的操作，而查找表是一種非常靈活、方便的數(shù)據(jù)結(jié)構(gòu)。其數(shù)據(jù)元素之間僅存在“同屬于一個(gè)集合”的這一種關(guān)系。在日常生活中，人們幾乎每天都要進(jìn)行“查找”工作。在手機(jī)通訊錄中查找電話號(hào)碼，在英文字典中查找某個(gè)單詞的讀音和含義等?！巴ㄓ嶄洝焙汀坝⑽淖值洹本褪遣檎冶怼?/p>

在計(jì)算機(jī)各種系統(tǒng)軟件或應(yīng)用軟件中，查找表也是一種最常見(jiàn)的結(jié)構(gòu)之一。如編譯程序中符號(hào)表、信息處理系統(tǒng)中的信息表等。所有需要被查的數(shù)據(jù)所在的集合就是查找表。

查找表(searchtable)：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)，可以是線性表、樹(shù)、圖。

所謂“查找”，即為在一個(gè)含有眾多的數(shù)據(jù)元素(或記錄)的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素(或記錄)。為了便于討論，必須給出這個(gè)“特定的”詞的確切含義，引入“關(guān)鍵字”的概念。

關(guān)鍵字(key)：數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)(識(shí)別)一個(gè)數(shù)據(jù)元素(或記錄)。如果一個(gè)關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則稱其為主關(guān)鍵字；否則為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)元素的值就是關(guān)鍵字。查找靜態(tài)查找表動(dòng)態(tài)查找表哈希表基本概念查找查找表平均查找長(zhǎng)度順序查找折半查找分塊查找二叉排序樹(shù)平衡二叉樹(shù)（了解）B樹(shù)（了解）哈希函數(shù)處理沖突的方法平均查找長(zhǎng)度

顯然，在一個(gè)結(jié)構(gòu)中查找某個(gè)數(shù)據(jù)元素的過(guò)程依賴于這個(gè)數(shù)據(jù)元素在結(jié)構(gòu)中所處的位置。因此，對(duì)表進(jìn)行查找的方法取決于表中數(shù)據(jù)元素依賴何種關(guān)系(這個(gè)關(guān)系是人為地加上的)組織在一起的。

查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間僅存在著“同屬一個(gè)集合”的松散關(guān)系，給查找?guī)?lái)不便。為此，需在數(shù)據(jù)元素之間人為地加上一些關(guān)系，以便按某種規(guī)則進(jìn)行查找，即以另一種數(shù)據(jù)結(jié)構(gòu)來(lái)表示查找表。

本章所討論的查找表分兩大類：

靜態(tài)查找表、動(dòng)態(tài)查找表。

靜態(tài)查找表：只做查找操作的查找表。它的主要操作有：

(1)查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中。

(2)查找某個(gè)“特定的”數(shù)據(jù)元素的各種屬性。靜態(tài)查找表在查找之前已經(jīng)存在，查找是在已經(jīng)有的數(shù)據(jù)集中找我們需要的。但是，隨著時(shí)間的推移，新的信息不斷出現(xiàn)，查找表也應(yīng)該不斷更新。為此，引進(jìn)了動(dòng)態(tài)查找表。動(dòng)態(tài)查找表：在查找的過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者刪除已經(jīng)存在的某個(gè)數(shù)據(jù)元素。顯然動(dòng)態(tài)查找表的操作就是兩個(gè)：

(1)查找時(shí)插入數(shù)據(jù)元素。

(2)查找時(shí)刪除數(shù)據(jù)元素。此外，還有一種表——哈希表，它是一種既適合于靜態(tài)查找也適合于動(dòng)態(tài)查找的查找表，具體技術(shù)會(huì)在8.4節(jié)詳細(xì)介紹。

查找基于的數(shù)據(jù)結(jié)構(gòu)是集合，集合中記錄之間沒(méi)有本質(zhì)的關(guān)系，可是要想獲得較高的查找性能，我們可以改變數(shù)據(jù)元素之間的關(guān)系，在存儲(chǔ)時(shí)可以將查找集合組成線性表、樹(shù)、圖等結(jié)構(gòu)。

平均查找長(zhǎng)度(averagesearchlength)：為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字次數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。對(duì)于長(zhǎng)度為n的查找表，查找成功時(shí)的平均查找長(zhǎng)度為其中，Pi為查找表中查找第i個(gè)記錄的概率，且

Ci為找到表中其關(guān)鍵字與給定值相等的第i個(gè)記錄時(shí)，和給定值已進(jìn)行過(guò)比較的關(guān)鍵字次數(shù)，顯然Ci隨查找過(guò)程不同而不同。由于查找算法的基本操作是關(guān)鍵字之間的比較操作，所以可以用平均查找長(zhǎng)度來(lái)衡量查找算法的性能。

基于靜態(tài)查找表主要有順序表、有序順序表、索引順序表、倒排表，查找法可分為順序查找法、折半查找法和分塊查找法。8.2.1順序表在順序表上查找的基本思想是：用給定關(guān)鍵字與順序表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗(所有元素均不成功)。存儲(chǔ)結(jié)構(gòu)可為順序存儲(chǔ)結(jié)構(gòu)，也可為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。這種查找方法叫做順序查找。8.2靜態(tài)查找表下面給出順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義：

#defineLISTSIZE20typedefstruct{KeyTypekey;/*關(guān)鍵字域*/…/*其他域*/}ElemType;typedefstruct{ElemTyper[LISTSIZE];intlength;}STable;STablest;

st就是查找表，st.r[1]～st.r[length]?存儲(chǔ)記錄，將給定的關(guān)鍵字存放在st.r[0]中，即st.r[0].key=k，st.r[0]作為哨兵，稱為監(jiān)視哨，可以起到防止越界的作用。查找過(guò)程可用下述算法描述之：1intSearchSeq(STablest,KeyTypek)

/*在順序表中查找關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/2{3inti;4st.r[0].key=k;5i=st.length;6while(st.r[i].key!=k)i--;7return(i);8}K=26K=78假設(shè)表長(zhǎng)為n，那么查找第i個(gè)數(shù)據(jù)元素時(shí)需要進(jìn)行n-i+1次比較，即Ci=n-i+1，又假設(shè)查找每個(gè)元素的概率相等，即Pi=1/n，則順序查找算法查找成功時(shí)的平均查找長(zhǎng)度為：

順序查找算法查找失敗時(shí)，關(guān)鍵字從第n個(gè)一直比較到第0個(gè)，所以需要進(jìn)行n+1次比較，因此，平均查找長(zhǎng)度為n+1。順序查找法的特點(diǎn)是算法簡(jiǎn)單且適應(yīng)面廣，對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論記錄是否按關(guān)鍵字有序均可應(yīng)用，而且，上述所有討論對(duì)線性鏈表也同樣適用。其缺點(diǎn)是平均查找長(zhǎng)度較大(與后面將要討論的其他查找算法相比)，特別是當(dāng)n很大時(shí)，查找效率較低。8.2.2有序順序表在有序順序表上查找的算法主要有順序查找、折半查找和插值查找方法。

1.順序查找在有序順序表上順序查找的方法和8.2.1節(jié)討論的順序表上的查找方法類似，但一般情況下不需要比較到st.r[0]?就可判斷出要查找的數(shù)據(jù)元素不在數(shù)據(jù)元素集合中。例如，

要查找的數(shù)據(jù)元素是50，當(dāng)順序查找與38比較后就可確定50不在數(shù)據(jù)元素集合中。有序順序表的查找算法如下：1intSearchSeq(STablest,KeyTypek)

/*在有序順序表中查找關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/2{inti;3st.r[0].key=k;4i=st.length;5while(st.r[i].key>k)i--;6if(st.r[i].key==k)return(i);7elsereturn(0);8}假設(shè)表長(zhǎng)為n，那么查找第i個(gè)數(shù)據(jù)元素時(shí)需要進(jìn)行n-i+1次比較，即Ci?=?n-i+1，又假設(shè)查找每個(gè)元素的概率相等，即Pi?=?1/n，則有序順序查找算法的平均查找長(zhǎng)度為查找失敗的情況分析：因?yàn)殛P(guān)鍵字是有序的，查找大于第n個(gè)元素的需要比較1次，查找大于第n-1小于第n個(gè)元素的，比較次數(shù)為2次，依次類推，查找大于第i-1且小于第i個(gè)元素的，比較次數(shù)為n-i+1次，在等概率情況下，查找不成功的平均查找長(zhǎng)度為2.折半查找折半查找又稱為二分查找法，這種方法要求待查找的表順序存儲(chǔ)而且表中關(guān)鍵字大小有序排列。其查找過(guò)程是：先確定待查記錄所在的范圍(區(qū)間)，然后逐步縮小范圍直到找到或找不到記錄為止。具體方法是：將表中間位置的關(guān)鍵字與查找關(guān)鍵字進(jìn)行比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，查找成功，或直到子表不存在為止，此時(shí)查找不成功。

查找key?=?26的查找此時(shí)st.r[mid].key與key相等，則查找成功key?=?85的查找過(guò)程此時(shí)low?>?high，則表明表中沒(méi)有等于key的元素，查找不成功。折半查找的算法如下：1intBinSearch(STablest,KeyTypekey)2{intlow,high,mid;3low=1;high=st.length;/*置區(qū)間初值*/4while(low<=high)5{6mid=(low+high)/2;/*折半*/7if(key==st.r[mid].key)8return(mid); /*找到待查元素*/9else10if(key<st.r[mid].key)11high=mid-1; /*繼續(xù)在前半?yún)^(qū)間進(jìn)行查找*/12else13low=mid+1; /*繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/14}15return(0);16}查找不成功的節(jié)點(diǎn)折半查找在查找不成功時(shí)和給定值進(jìn)行的比較次數(shù)最多也不超過(guò)。

對(duì)于n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為。折半查找在查找成功時(shí)，所進(jìn)行的關(guān)鍵字比較次數(shù)至多為。所以，折半查找的時(shí)間復(fù)雜度為O(lb?n)，顯然比順序查找效率高。折半查找的效率要好于順序查找，特別是在表長(zhǎng)較大時(shí)，其差別更大。但是折半查找只能對(duì)順序存儲(chǔ)結(jié)構(gòu)的有序表進(jìn)行。對(duì)需要經(jīng)常進(jìn)行查找操作的應(yīng)用來(lái)說(shuō)，以一次排序的投入而使多次查找收益，顯然是合算的。3.插值查找

為什么一定是折半呢，可不可以折四分之一或者其他?比如在英文字典中查“apple”,我們會(huì)在前面的頁(yè)面查，如果查“zero”，會(huì)在后面的頁(yè)面查，顯然不會(huì)折半從中間去查。也就是說(shuō)，折半查找算法中的語(yǔ)句6：mid=(low+high)/2，我們可以進(jìn)行修改。求取中點(diǎn)，其中l(wèi)ow和high分別為表的兩個(gè)端點(diǎn)下標(biāo)，kx為給定值。若kx?<?st.r[mid].key，則high?=?mid-1，繼續(xù)左半?yún)^(qū)查找；若kx?>?st.r[mid].key，則low?=?mid+1，繼續(xù)右半?yún)^(qū)查找；若kx?=?st.r[mid].key，查找成功。8.2.3索引順序表當(dāng)順序表中的數(shù)據(jù)元素個(gè)數(shù)非常大時(shí)，為了提高查找速度，可在順序表上建立索引表。我們把要在其上建立索引表的順序表稱為主表，主表中存放著數(shù)據(jù)元素的全部信息，索引表中只存放主表中要查找數(shù)據(jù)元素的主關(guān)鍵字和索引信息。要使索引表的查找效率高，索引表必須有序。但主表中的數(shù)據(jù)元素不一定要按關(guān)鍵字有序，但是要分塊有序。分塊查找過(guò)程如下：第一步，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。具體可用順序查找法或折半查找法進(jìn)行。第二步，用順序查找法，在相應(yīng)的塊內(nèi)查找關(guān)鍵字為K的記錄。查找41

分塊查找的平均查找長(zhǎng)度由兩部分構(gòu)成，即查找索引表時(shí)的平均查找長(zhǎng)度LB以及在相應(yīng)的塊內(nèi)進(jìn)行順序查找的平均查找長(zhǎng)度LW，即

ASLbs=LB+LW

假定將長(zhǎng)度為n的表分成b塊，且每塊含s個(gè)數(shù)據(jù)元素，則b=n/s。又假定表中每個(gè)元素的查找概率相等，則每個(gè)索引項(xiàng)的查找概率為1/b，塊中每個(gè)元素的查找概率為1/s。若用順序查找法確定待查元素所在塊，則有：

將b=代入，得：

可見(jiàn)，此時(shí)的平均查找長(zhǎng)度不僅和表長(zhǎng)n有關(guān)，而且和每一個(gè)塊中元素個(gè)數(shù)s有關(guān)。在給定n的前提下，s是可以選擇的。容易證明，當(dāng)s取時(shí)，ASLbs取最小值+?1。這個(gè)值比順序查找有了很大改進(jìn)，但遠(yuǎn)不及折半查找，因此在確定所在塊的過(guò)程中，由于塊間有序，所以可以應(yīng)用折半、插值等手段來(lái)提高效率。若用折半查找法確定待查元素所在的塊，則有：LB?=?lb?(b+1)?-?1

8.2.4倒排表

大家都用過(guò)互聯(lián)網(wǎng)上的搜索引擎，在搜索信息時(shí)，能夠在極短的時(shí)間內(nèi)給出一些結(jié)果。是什么樣的查找技術(shù)能達(dá)到這樣高效呢?

比如有2篇文章，這里舉例比較簡(jiǎn)單，也就是2個(gè)句子，編號(hào)分別為1、2，有1.?Agoodmedicinetasksbitter2.?Agoodbookisagoodfriend.假設(shè)，我們忽略大小寫(xiě)，可以整理出一個(gè)單詞表，英文單詞文章編號(hào)a1，2book2bitter1friend2good1,2medicine1is2tasks1

有了這樣一個(gè)單詞表，在查找文章時(shí)就很方便了，比如，搜索“good”，系統(tǒng)先在這張表中查找，找到后將它對(duì)應(yīng)文章編號(hào)的地址(一般在搜索引擎中就是標(biāo)題和鏈接)返回。由于單詞表是有序的，而且返回的只是文章編號(hào)，所以整體速度非常快。

這個(gè)表就是索引表，索引項(xiàng)通常包含次關(guān)鍵字和記錄號(hào)。它的特點(diǎn)是每項(xiàng)都包含一個(gè)屬性值和具有該屬性值的各記錄的地址，顯然在這個(gè)表中是由屬性(字段、次關(guān)鍵字)的值來(lái)查找記錄，不是通常的通過(guò)記錄號(hào)查找其屬性值，因此稱為倒排索引。

倒排索引的優(yōu)點(diǎn)就是查找記錄非?？欤谒饕砩芍?，查找不用去讀取記錄，就可以得到結(jié)果。但也有明顯的缺點(diǎn)，就是表中記錄號(hào)不定長(zhǎng)。如上面的例子中，如果文章比較多，倒排索引中的記錄號(hào)也就比較復(fù)雜，維護(hù)起來(lái)就比較困難，其插入、刪除操作就需要做相應(yīng)處理。可采用批量處理，也就是累積到一定規(guī)模后再處理。搜索技術(shù)在實(shí)際應(yīng)用中是非常復(fù)雜的，比如首先要提取單詞，英文比較方便，中文就要涉及分詞技術(shù)；還有搜索時(shí)檢索到的記錄有上千條，如何組織等。這里僅僅是拋磚引玉，希望引起讀者對(duì)搜索技術(shù)的興趣，相關(guān)的技術(shù)知識(shí)讀者可以查閱相關(guān)資料。8.3動(dòng)態(tài)查找表8.3.1二叉排序樹(shù)

1、二叉排序樹(shù)概念二叉排序樹(shù)又稱為二叉查找樹(shù)，它是一種特殊的二叉樹(shù)，其定義為：二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：①若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；②若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；③它的左、右子樹(shù)也分別是二叉排序樹(shù)。

由二叉排序樹(shù)的定義可以得出一個(gè)重要性質(zhì)：

中序遍歷一棵二叉排序樹(shù)時(shí)可以得到一個(gè)遞增有序序列。如對(duì)圖進(jìn)行中序遍歷，可得到序列：

06，15，39，58，67，76，80，88，97。2.二叉排序樹(shù)查找過(guò)程對(duì)二叉排序樹(shù)進(jìn)行查找的過(guò)程類似于在折半查找判定樹(shù)上所進(jìn)行的查找過(guò)程，其不同之處為：折半查找的判定樹(shù)是靜態(tài)的，二叉排序樹(shù)是動(dòng)態(tài)的。查找K=58K=78

二叉排序樹(shù)的操作中，使用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下：

typedefstructnode{ KeyTypekey;structnode*lchild,*rchild;}BSTNode,*BSTree;二叉排序樹(shù)的查找算法如下：1BSTreeSearchBST(BSTreebt,KeyTypekey)2{3if(!bt)returnNULL;4else5if(bt->key==key)returnbt;6else7if(key<bt->key)8returnSearchBST(bt->lchild,key);/*在左子樹(shù)查找*/9else10returnSearchBST(bt->rchild,key);/*在右子樹(shù)查找*/11}3.二叉排序樹(shù)的插入和生成已知一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)s，若將其插入到二叉排序樹(shù)中，只要保證插入后仍符合二叉排序樹(shù)的定義即可。插入過(guò)程可描述如下：①若二叉排序樹(shù)是空樹(shù)，則key成為二叉排序樹(shù)的根。②若二叉排序樹(shù)是非空樹(shù)，則將key與二叉排序樹(shù)的根進(jìn)行比較，如果key等于根結(jié)點(diǎn)的值，則停止插入；如果key小于根結(jié)點(diǎn)的值，則將key插入左子樹(shù)；如果key大于根結(jié)點(diǎn)的值，則將key插入右子樹(shù)。二叉排序樹(shù)的插入算法如下：1viodInsertBST(BSTree*bt,KeyTypekey)/*若在二叉排序樹(shù)中不存在關(guān)鍵字等于key的元素，插入該元素*/2{3BSTrees;4if(*bt==NULL)/*遞歸結(jié)束條件*/5{6s=(BSTree)malloc(sizeof(BSTNode));7s->key=key;8s->lchild=NULL;s->rchild=NULL;9*bt=s;10}11else12if(key<(*bt)->key)13InsertBST(&((*bt)->lchild),key);/*將s插入左子樹(shù)*/14else15if(key>(*bt)->key)16InsertBST(&((*bt)->rchild),key);/*將s插入右子樹(shù)*/17}二叉排序樹(shù)的插入是將待插元素插入到二叉排序樹(shù)的葉結(jié)點(diǎn)上，不需要移動(dòng)元素。

給定一個(gè)元素序列，利用二叉排序樹(shù)的插入算法動(dòng)態(tài)構(gòu)造一棵二叉排序樹(shù)。關(guān)鍵字序列：56，26，67，12，37，98，建立二叉排序樹(shù)假設(shè)KeyType為整型。構(gòu)造二叉排序樹(shù)的算法如下所示：voidCreateBST(BSTree*bt) 2{3KeyTypekey;4*bt=NULL;5scanf(″%d″,&key);6while(key!=ENDKEY)/*ENDKEY為自定義常數(shù)，作為結(jié)束標(biāo)識(shí)*/7{8InsertBST(bt,key);9scanf(″%d″,&key);10}11}

可以看出，對(duì)于同樣的元素，如果輸入順序不同，構(gòu)造的二叉排序樹(shù)形狀不同。26，67，12，37，56，9856，26，67，12，37，9812，26，37，56，67，984.二叉排序樹(shù)的刪除查找待刪結(jié)點(diǎn)，若找不到，空操作；否則，假設(shè)待刪除結(jié)點(diǎn)為p，結(jié)點(diǎn)p的雙親為f，并假設(shè)p是f的左孩子(右孩子的情況類似)下面分三種情況進(jìn)行討論：①p為葉子結(jié)點(diǎn)，由于刪去葉子結(jié)點(diǎn)不破壞整棵樹(shù)的結(jié)構(gòu)，則只需修改其雙親結(jié)點(diǎn)的指針即可：

f->lchild=NULL;free(p);下面分三種情況進(jìn)行討論：②p結(jié)點(diǎn)只有左子樹(shù)，或只有右子樹(shù)，則p的左子樹(shù)或右子樹(shù)直接改為其雙親結(jié)點(diǎn)f的左子樹(shù)：

f->lchild=p->lchild或f->lchild=p->rchild；free(p);③p結(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)，如圖所示，此時(shí)有兩種處理方法：方法一：首先找到p結(jié)點(diǎn)在二叉排序樹(shù)的中序遍歷序列中的直接前驅(qū)s結(jié)點(diǎn)(無(wú)右子樹(shù))，然后將p的左子樹(shù)改為f的左子樹(shù)，而將p的右子樹(shù)改為s的右子樹(shù)：f->lchild=p->lchild;s->rchild=p->rchild;free(p);

方法二：首先找到p結(jié)點(diǎn)在二叉排序樹(shù)的中序遍歷序列中的直接前驅(qū)s結(jié)點(diǎn)，q為s結(jié)點(diǎn)的雙親，如圖(a)所示。利用s結(jié)點(diǎn)的值代替p結(jié)點(diǎn)的值，原s結(jié)點(diǎn)的左子樹(shù)改為s結(jié)點(diǎn)的雙親q的右子樹(shù)，再將s結(jié)點(diǎn)刪除：

p->key=s->key;q->rchild=s->lchild;free(s);

若s結(jié)點(diǎn)是p結(jié)點(diǎn)的左子樹(shù)的根，q等于p，如圖(c)所示。利用s結(jié)點(diǎn)的值代替p結(jié)點(diǎn)的值，原s結(jié)點(diǎn)的左子樹(shù)改為s結(jié)點(diǎn)的雙親q的左子樹(shù)，再將s結(jié)點(diǎn)刪除：

p->key=s->key;q->lchild=s->lchild;free(s);

結(jié)果如圖(d)所示。將其三種情況綜合所得的刪除算法如下所示：1BSTreeDelBST(BSTreebt,KeyTypek)2{BSTreep,f,s,q;3p=bt;f=NULL;4while(p)5{6if(p->key==k)break;/*如果查找到關(guān)鍵字退出循環(huán)*/7f=p; /*f指向查找過(guò)程中當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)*/8if(p->key>k)p=p->lchild; /*在左子樹(shù)中查找*/9elsep=p->rchild; /*在右子樹(shù)中查找*/10};11if(p==NULL)returnbt;/*如果沒(méi)有查找到關(guān)鍵字返回*/12if(p->lchild&&p->rchild) /*p左右子樹(shù)不空*/13{q=p;14s=p->lchild;15while(s->rchild)/*找待刪節(jié)點(diǎn)的前驅(qū)*/16{q=s;17s=s->rchild;18}19p->key=s->key; /*s的值覆蓋p的值*/if(q!=p)/*原s結(jié)點(diǎn)的左子樹(shù)改為s結(jié)點(diǎn)的雙親q的右子樹(shù)*/q->rchild=s->lchild;elseq->lchild=s->lchild;24free(s);25}26else27{28if(!p->rchild) /*p左子樹(shù)不空*/29{q=p;30p=p->lchild;31}32else /*p右子樹(shù)不空*/33{q=p;34p=p->rchild;35}36if(!f)bt=p;37else38if(q==f->lchild)f->lchild=p;39elsef->rchild=p;40free(q);41}42returnbt;43}5.二叉排序樹(shù)的查找性能分析

在二叉排序樹(shù)上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到待查結(jié)點(diǎn)的路徑；若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。因此二叉排序樹(shù)的查找與折半查找過(guò)程類似，在二叉排序樹(shù)中查找到一個(gè)記錄時(shí)，其比較次數(shù)不超過(guò)樹(shù)的深度。但是，對(duì)于長(zhǎng)度為n的表來(lái)說(shuō)，折半查找的判定樹(shù)是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)卻不唯一，結(jié)點(diǎn)插入的順序不同，所構(gòu)成的二叉排序樹(shù)的形態(tài)和深度就不同。

而二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)，二叉排序樹(shù)的深度越淺，其平均查找長(zhǎng)度ASL越小。在二叉排序樹(shù)上進(jìn)行查找時(shí)的平均查找長(zhǎng)度與二叉排序樹(shù)的形態(tài)有關(guān)。

當(dāng)插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉排序樹(shù)是一單支樹(shù)，其深度為n，其平均查找長(zhǎng)度ASL=(n+1)/2，與順序查找相同，這是最壞情況。最好情況下，二叉排序樹(shù)在生成過(guò)程中，樹(shù)的形態(tài)比較均勻，最終得到的二叉排序樹(shù)形態(tài)與折半查找的判定樹(shù)形態(tài)相似，此時(shí)它的平均查找長(zhǎng)度大約是lbn。如果把n個(gè)結(jié)點(diǎn)按各種可能的次序插入到二叉排序樹(shù)中，則有n!?棵二叉排序樹(shù)(其中有形態(tài)相同的)，可以證明，對(duì)這些二叉排序樹(shù)的查找長(zhǎng)度進(jìn)行平均，得到的平均查找長(zhǎng)度仍然是O(lbn)。

就平均性能而言，二叉排序樹(shù)與折半查找的查找性能相差不大，并且在二叉排序樹(shù)上進(jìn)行插入和刪除十分方便，無(wú)需移動(dòng)大量結(jié)點(diǎn)。因此，對(duì)于需要經(jīng)常做插入、刪除、查找運(yùn)算的表，宜采用二叉排序樹(shù)結(jié)構(gòu)。當(dāng)查找表對(duì)查找性能要求比較高時(shí)，需要在生成二叉排序樹(shù)的過(guò)程中對(duì)二叉排序樹(shù)進(jìn)行“平衡化”處理，使所生成的二叉排序樹(shù)始終保持“平衡”狀態(tài)。8.3.2平衡二叉樹(shù)**

平衡二叉樹(shù)(balancedbinarytree)又稱為AVL樹(shù)，是一種二叉排序樹(shù)，具有以下性質(zhì)：

①它是一棵空樹(shù)或它的左、右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1；②左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。我們將二叉樹(shù)上結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)的深度的值稱為該結(jié)點(diǎn)的平衡因子BF(balancefactor)。那么，平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是

-1、0、1。如果二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹(shù)就不平衡了。AVL樹(shù)上任何結(jié)點(diǎn)的左、右子樹(shù)的深度之差不超過(guò)1，可以證明它的深度和lb?n是同數(shù)量級(jí)的(n是結(jié)點(diǎn)個(gè)數(shù))。由此，AVL樹(shù)的平均查找長(zhǎng)度也和lbn是同數(shù)量級(jí)。有一序列{13,24,37,90,53}，構(gòu)建二叉排序樹(shù)的過(guò)程如圖

一般情況下，假設(shè)由于二叉排序樹(shù)上插入結(jié)點(diǎn)而失去平衡的最小子樹(shù)的根結(jié)點(diǎn)指針為a(即離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值超過(guò)1的祖先結(jié)點(diǎn))，則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為以下四種情況：(1)?LL型平衡旋轉(zhuǎn)。b=a->lchild;a->lchild=b->rchild;a->BF=0;b->rchild=a;b->BF=0;(2)?RR型平衡旋轉(zhuǎn)b=a->rchild;a->rchild=b->lchild;a->BF=0;b->lchild=a;b->BF=0;(3)?LR型平衡旋轉(zhuǎn)。b=a->lchild;c=b->rchild;b->rchild=c->lchild;a->lchild=c->rchild;b->BF=0;a->BF=-1;c->lchild=b;c->rchild=ac->BF=0;(4)?RL型平衡旋轉(zhuǎn)b=a->rchild;c=b->lchild;b->lchild=c->rchild;a->rchild=c->lchild;b->BF=0;a->BF=1;c->lchild=a;c->rchild=bc->BF=0;

綜上所述，平衡旋轉(zhuǎn)是當(dāng)二叉排序樹(shù)在插入結(jié)點(diǎn)后產(chǎn)生不平衡時(shí)進(jìn)行的。因此，要建立一棵平衡的二叉排序樹(shù)，需要對(duì)前一小節(jié)的算法CreateBST作如下幾點(diǎn)修改：

(1)判別插入結(jié)點(diǎn)之后是否產(chǎn)生不平衡；

(2)找到失去平衡的最小子樹(shù)；

(3)判別旋轉(zhuǎn)類型并作相應(yīng)調(diào)整。

平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子的絕對(duì)值都不超過(guò)1。所以，在插入結(jié)點(diǎn)之后，若二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則說(shuō)明出現(xiàn)不平衡；同時(shí)，失去平衡的最小子樹(shù)的根結(jié)點(diǎn)必為離插入結(jié)點(diǎn)最近且插入之前的平衡因子的絕對(duì)值大于零(在插入結(jié)點(diǎn)之后，其平衡因子的絕對(duì)值才有可能大于1)的祖先結(jié)點(diǎn)。

在對(duì)CreateBST算法進(jìn)行修改時(shí)，假設(shè)插入結(jié)點(diǎn)為s，需要做到：

(1)在查找插入位置的過(guò)程中，記下離插入位置最近且平衡因子不等于零的結(jié)點(diǎn)，令指針a指向該結(jié)點(diǎn)。

(2)插入之后，修改自a到s路徑上所有結(jié)點(diǎn)的平衡因子值。

(3)判別樹(shù)是否失去平衡。即在插入結(jié)點(diǎn)之后，a結(jié)點(diǎn)的平衡因子絕對(duì)值是否大于1。若是，則需判別旋轉(zhuǎn)類型并作相應(yīng)處理，否則插入過(guò)程結(jié)束。在平衡二叉樹(shù)上進(jìn)行查找和二叉排序樹(shù)的查找相同，因此，在查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)不超過(guò)樹(shù)的深度。

如果我們需要查找的集合本身沒(méi)有順序，在頻繁查找的同時(shí)也需要經(jīng)常進(jìn)行插入和刪除操作，顯然需要建立一棵二叉排序樹(shù)，如果二叉排序樹(shù)不平衡的話，查找的效率是非常低的，因此在構(gòu)建時(shí)，就讓這棵二叉排序樹(shù)是平衡二叉樹(shù)，這樣查找的時(shí)間復(fù)雜度為O(lb?n)，而插入和刪除的平均查找長(zhǎng)度也是O(lb?n)。8.4哈希表的查找8.4.1什么是哈希表在數(shù)據(jù)元素的存儲(chǔ)位置和其關(guān)鍵字之間建立某種關(guān)系，那么在查找時(shí)，就無(wú)需進(jìn)行比較或只做少數(shù)比較就能直接由關(guān)鍵字找到相應(yīng)存儲(chǔ)位置。哈希表正是基于這種思想。哈希表又叫雜湊表或散列表。

其基本思想是：首先在數(shù)據(jù)元素的關(guān)鍵字k和數(shù)據(jù)元素的存儲(chǔ)位置addr之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得addr=H(k)，H稱為哈希函數(shù)。在建立哈希表時(shí)，把關(guān)鍵字為k的元素直接存入H(k)的單元中；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)地址addr=H(k)，從而達(dá)到了按關(guān)鍵字直接存取元素的目的。理想情況是希望不經(jīng)過(guò)任何比較，一次存取便能獲得所查記錄，也就是說(shuō)，哈希函數(shù)在關(guān)鍵字和地址之間建立一一對(duì)應(yīng)關(guān)系。這種理想狀態(tài)的哈希函數(shù)特別少。

當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)得到相同的地址，即k1≠k2，但H(k1)=H(k2)，這種現(xiàn)象稱為沖突。此時(shí)稱k1和k2為同義詞。實(shí)際應(yīng)用中，沖突是不可避免的，只能通過(guò)改進(jìn)哈希函數(shù)的性能來(lái)減少?zèng)_突。由此可以看出，哈希表的構(gòu)造及查找主要包括以下兩方面的內(nèi)容：①如何構(gòu)造哈希函數(shù)；②如何處理沖突。8.4.2哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)的方法很多，但如何構(gòu)造一個(gè)“好”的哈希函數(shù)是帶有很強(qiáng)的技術(shù)性和實(shí)踐性的問(wèn)題。這里“好”的哈希函數(shù)是指哈希函數(shù)的構(gòu)造方法簡(jiǎn)單并且發(fā)生沖突的可能性小。也就是說(shuō)，一個(gè)好的哈希函數(shù)能將給定的數(shù)據(jù)集合均勻地散列到地址區(qū)間中。下面介紹構(gòu)造哈希函數(shù)常用的六種方法。

(1)直接定址法。取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值作為哈希地址，即

H(key)=key或H(key)=a×key+b

其中a、b為常數(shù)，在使用時(shí)為了使哈希地址與存儲(chǔ)空間吻合可調(diào)整a、b的值。例如，查找表是一張從1歲到100歲的人口統(tǒng)計(jì)表，如表所示。若該查找表以年齡作為關(guān)鍵字，則哈希函數(shù)取關(guān)鍵字自身，這樣一來(lái)可以直接由年齡得到相應(yīng)元素的存儲(chǔ)地址。哈希函數(shù)：H(key)=key。

又如，有一個(gè)新中國(guó)成立后出生的人口調(diào)查表，關(guān)鍵字是年份，哈希函數(shù)取關(guān)鍵字加一常數(shù)：

H(key)?=?key?+?(-1948)

直接定址法的特點(diǎn)是地址集合和關(guān)鍵字集合的大小相同，即一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)存儲(chǔ)地址，因此不會(huì)發(fā)生沖突，而且構(gòu)造方法特別簡(jiǎn)單。但是在實(shí)際應(yīng)用中能使用這種哈希函數(shù)的情況很少，這種方法只適合于關(guān)鍵字分布基本連續(xù)，且關(guān)鍵字集合較小的情形。(2)數(shù)字分析法。

如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。例如，有90個(gè)記錄，關(guān)鍵字為8位十進(jìn)制整數(shù)：d1d2d3…d7d8，如果哈希表的地址空間為0～99，假設(shè)這90個(gè)關(guān)鍵字中的一部分如下所示：經(jīng)過(guò)分析，各關(guān)鍵字中d3和d7分布較均勻，則哈希函數(shù)可設(shè)置為：H(key)?=?H(d1d2d3…d7d8)?=?d3d7數(shù)字分析法適合于關(guān)鍵字是數(shù)字的情形，且可能出現(xiàn)的關(guān)鍵字均事先知道。(3)平方取中法。當(dāng)無(wú)法確定關(guān)鍵字中哪幾位分布比較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中的每一位都相關(guān)，故不同的關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。例如，某一查找表的關(guān)鍵字為十進(jìn)制4位整數(shù)，表長(zhǎng)為1000，則可取平方后的第2、3、4位作為哈希地址，如表8.4所示。(4)疊加法。按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分(最后一部分可以較短)，然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是哈希地址。具體方法有折疊法與移位法。折疊法是從一端向另一端沿分割界來(lái)回折疊，然后將各段相加；移位法是將分割后的每部分低位對(duì)齊相加。例如，key=67117278098765478，哈希表長(zhǎng)為1000，則應(yīng)把關(guān)鍵字分成3位一段，在此舍去最低的兩位78，分別進(jìn)行移位疊加和折疊疊加，求得哈希地址為264和155，如圖所示。(5)除留余數(shù)法。取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)的數(shù)除后所得余數(shù)作為哈希地址。假設(shè)表長(zhǎng)為m，p為小于等于m的最大素?cái)?shù)，則哈希函數(shù)為

H(key)?=?key%p其中%為求模運(yùn)算為了盡可能少地產(chǎn)生沖突，通常取p為不大于表長(zhǎng)且最接近表長(zhǎng)m的素?cái)?shù)，例如表長(zhǎng)m=1000時(shí)，可取p=997。除留余數(shù)法是一種最簡(jiǎn)單，也是最常用的構(gòu)造哈希函數(shù)的方法，不僅可以對(duì)關(guān)鍵字直接取模，也可以在對(duì)關(guān)鍵字進(jìn)行其他運(yùn)算之后取模。(6)偽隨機(jī)數(shù)法。采用一個(gè)偽隨機(jī)數(shù)作為哈希函數(shù)，即

H(key)=random(key)。在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況，靈活采用不同的方法，并用實(shí)際數(shù)據(jù)測(cè)試它的性能，以便作出判定。哈希函數(shù)的選擇，通常應(yīng)考慮以下五個(gè)因素：①計(jì)算哈希函數(shù)所需的時(shí)間；②關(guān)鍵字的長(zhǎng)度；③哈希表的長(zhǎng)度；④關(guān)鍵字的分布；⑤記錄查找的頻率。

8.4.3處理沖突的方法通過(guò)構(gòu)造性能良好的哈希函數(shù)可以減少?zèng)_突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個(gè)關(guān)鍵問(wèn)題。創(chuàng)建哈希表和查找哈希表都會(huì)遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)一致。常用的解決沖突的方法有以下四種。

1.開(kāi)放定址法開(kāi)放定址法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址addr=H(key)出現(xiàn)沖突時(shí)，以addr為基礎(chǔ)產(chǎn)生另一個(gè)哈希地址addr1，如果addr1仍沖突，再以addr1為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址addr2，…，直到找出一個(gè)不沖突的哈希地址addri，將相應(yīng)元素存入其中。(1)線性探測(cè)再散列。

di?=?1，2，3，…，m-1

發(fā)生沖突時(shí)，順序查看表中下一單元，直到找出一個(gè)空單元或查遍全表。

(2)二次探測(cè)再散列。

di?=?12，-12，22，-22，…，k2，-k2(k≤m/2)

發(fā)生沖突時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，比較靈活。

(3)偽隨機(jī)探測(cè)再散列。

di?=?偽隨機(jī)數(shù)序列具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，并給定一個(gè)隨機(jī)數(shù)作起點(diǎn)。

例如，哈希表長(zhǎng)為11，哈希函數(shù)為：H(key)=key%11。假定在表中已經(jīng)存入關(guān)鍵字為60，17，29的元素現(xiàn)有第4個(gè)元素，其關(guān)鍵字為38，H(38)?=?5，與60發(fā)生沖突；若用線性探測(cè)再散列的方法處理時(shí)，下一個(gè)哈希地址H1=(5+1)%11=6，仍沖突；再找下一哈希地址H2=(5+2)%11=7，仍沖突，繼續(xù)找下一哈希地址H3=(5+3)%11=8，此時(shí)不再?zèng)_突，

若用二次探測(cè)再散列的方法處理，第4個(gè)元素，其關(guān)鍵字為38，H(38)=5，與60發(fā)生沖突；下一個(gè)哈希地址H1=(5+12)%11=6，仍沖突；再找下一哈希地址H2=(5-12)%11=4，此時(shí)不再?zèng)_突，將元素存入4號(hào)單元中

可以看出，線性探測(cè)再散列容易產(chǎn)生“二次聚集”，即在處理同義詞的沖突時(shí)又導(dǎo)致非同義詞的沖突。線性探測(cè)再散列的特點(diǎn)是，只要哈希表不滿，就一定能找到一個(gè)不沖突的哈希地址，而二次探測(cè)再散列和偽隨機(jī)探測(cè)再散列則不一定。2.鏈地址法將所有關(guān)鍵字是同義詞的元素連接成一條線性鏈表，并將其鏈頭存在相應(yīng)的哈希地址所指的存儲(chǔ)單元中。因此，查找、插入和刪除主要在同義詞鏈中執(zhí)行。例如，已知一組關(guān)鍵字(71，27，26，30，16，46，19，42，24，49，64)，哈希表長(zhǎng)為13，哈希函數(shù)為：

H(key)=key%133.再哈希當(dāng)發(fā)生沖突時(shí)，再用另一個(gè)哈希函數(shù)來(lái)計(jì)算下一個(gè)哈希地址，如果再發(fā)生沖突，再使用另一個(gè)哈希函數(shù)，直到不發(fā)生沖突。這樣預(yù)先設(shè)置一個(gè)哈希函數(shù)的序列：

Hi=RHi(key)i?=?1，2，…，kRHi均是不同的哈希函數(shù)，在同義詞產(chǎn)生地址沖突時(shí)，計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。這種方法不易產(chǎn)生聚集，但增加了計(jì)算時(shí)間。

4.建立公共溢出區(qū)建立公共溢出區(qū)的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是與基本表發(fā)生沖突的元素一律填入溢出表。8.4.4哈希表的查找過(guò)程哈希表的查找過(guò)程與哈希表的創(chuàng)建過(guò)程基本一致，當(dāng)查找關(guān)鍵字為k的元素時(shí)，首先計(jì)算addr=H(k)。如果單元addr為空，則所查元素不存在；如果單元addr中元素的關(guān)鍵字為k，則找到所查元素；否則，按構(gòu)造哈希表時(shí)解決沖突的方法，找出下一個(gè)哈希地址，直到哈希表中的某個(gè)位置為空或表中所填記錄的關(guān)鍵字等于給定值為止。上述查找過(guò)程可表示如下：

(1)按給定關(guān)鍵字k求哈希地址addr=H(k)。

(2)若地址