1.教學(xué)目的

介紹數(shù)據(jù)結(jié)構(gòu)的重要技術(shù)——查找。為了在大量信息中找到所需信息，就需用到查找技術(shù)。2.教學(xué)要求①熟練掌握順序表和有序表的查找方法及其平均查找長(zhǎng)度的計(jì)算方法。②熟練掌握二叉排序樹(shù)的構(gòu)造和查找方法，掌握在二叉排序樹(shù)上插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的算法。③了解平衡二叉樹(shù)(AVL樹(shù))的定義及平衡旋轉(zhuǎn)技術(shù)。④簡(jiǎn)單了解B樹(shù)的特點(diǎn)以及其查找的過(guò)程。⑤熟練掌握哈希表的構(gòu)造方法。第八章查找3．教學(xué)重點(diǎn)：①折半查找的算法、二叉排序樹(shù)的構(gòu)建及查找、哈希函數(shù)的構(gòu)造方法、處理沖突的方法及其查找的算法。②各種查找方法在等概率情況下平均查找長(zhǎng)度的分析。4．教學(xué)難點(diǎn)：①二叉排序樹(shù)中結(jié)點(diǎn)的插入與刪除。②平衡二叉樹(shù)的平衡旋轉(zhuǎn)技術(shù)。③B樹(shù)的插入與刪除。8.1基本概念查找表(searchtable)：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)，可以是線性表、樹(shù)、圖。關(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)鍵字。查找（searching）：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。本章所討論的查找表分兩大類：靜態(tài)查找表、動(dòng)態(tài)查找表。靜態(tài)查找表：只做查找操作的查找表。它的主要操作有：(1)查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中。(2)查找某個(gè)“特定的”數(shù)據(jù)元素的各種屬性。動(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ù)元素。平均查找長(zhǎng)度：為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字次數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。對(duì)于長(zhǎng)度為n的查找表，查找成功時(shí)的平均查找長(zhǎng)度為其中，Pi為查找表中找第i個(gè)記錄的概率，且。8.2靜態(tài)查找表

8.2.1順序表在順序表上查找的基本思想是：用給定關(guān)鍵字與順序表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗(所有元素均不成功)。存儲(chǔ)結(jié)構(gòu)可為順序存儲(chǔ)結(jié)構(gòu)，也可為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?；陟o態(tài)查找表主要有順序表、有序順序表、索引順序表、倒排表，查找法可分為順序查找法、折半查找法和分塊查找法。下面給出順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義：#defineLISTSIZE20typedefstruct{KeyTypekey;/*關(guān)鍵字域*/…/*其他域*/}ElemType;typedefstruct{ElemTyper[LISTSIZE];intlength;}STable;STablest;順序查找過(guò)程可以描述為：從表的尾部開(kāi)始查找，逐個(gè)對(duì)記錄的關(guān)鍵字和給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功；反之，一定在最終的st.r[0]查找到，此時(shí)說(shuō)明查找失敗。顯然，查找成功返回記錄在表中的位置，查找失敗返回0。查找過(guò)程可用下述算法描述之（適合于表中數(shù)據(jù)無(wú)序）：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

}用平均查找長(zhǎng)度來(lái)分析順序查找算法的性能：假設(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。8.2.2有序順序表1、順序查找在有序順序表上順序查找的方法和8.2.1節(jié)討論的順序表上的查找方法類似，但一般情況下不需要比較到st.r[0]就可判斷出要查找的數(shù)據(jù)元素不在數(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)度為查找失敗的情況分析：在等概率情況下，查找不成功的平均查找長(zhǎng)度為由此可見(jiàn)，查找成功時(shí)，有序順序查找算法的平均查找長(zhǎng)度和順序表查找算法的平均查找長(zhǎng)度相同；但當(dāng)查找不成功時(shí)，有序順序表上的查找算法平均查找長(zhǎng)度是順序表上平均查找長(zhǎng)度的1/2。2、折半查找折半查找又稱為二分查找法，這種方法要求待查找的表順序存儲(chǔ)而且表中關(guān)鍵字大小有序排列。其查找過(guò)程是：先確定待查記錄所在的范圍(區(qū)間)，然后逐步縮小范圍直到找到或找不到記錄為止。具體方法是：將表中間位置的關(guān)鍵字與查找關(guān)鍵字進(jìn)行比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則查找后一子表。重復(fù)以上過(guò)程。例如，已知如下11個(gè)數(shù)據(jù)元素的有序表：現(xiàn)要查找關(guān)鍵字為26和85的數(shù)據(jù)元素。假設(shè)指針low和high分別指示待查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即mid=(low+high)/2。在此例中，low和high的初始值分別為1和11，當(dāng)high<low時(shí)，表示不存在這樣的子表空間，查找失敗。下面先看查找key=26的查找過(guò)程：st.r[mid].key與給定key=26比較，顯然，st.r[mid].key>key，說(shuō)明若待查找元素存在，則必在區(qū)間[low，mid-1]的范圍的子表中。令指針high指向第mid-1個(gè)元素，重新求得mid=(low+high)/2。仍以st.r[mid].key與給定key=26比較，顯然，st.r[mid].key<key，說(shuō)明若待查找元素存在，則必在區(qū)間[mid+1，high]的范圍的子表中。令指針low指向第mid+1個(gè)元素，重新求得mid=(low+high)/2。此時(shí)st.r[mid].key與key相等，則查找成功，所查找元素在表中序號(hào)等于指針mid的值。下面再看查找key=85的查找過(guò)程：st.r[mid].key<key，令low=mid+1，有st.r[mid].key>key，令high=mid-1，有st.r[mid].key<key，令low=mid+1，有st.r[mid].key<key，令low=mid+1，有此時(shí)low>high，則表明表中沒(méi)有等于key的元素，查找不成功。折半查找的算法如下：1intBinSearch(STablest,KeyTypekey)

/*在有序表st中折半查找其關(guān)鍵字等于key的元素，若找到，

則函數(shù)值為該元素在表中的位置*/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}為了分析折半查找的性能，可以用一棵二叉樹(shù)來(lái)描述折半查找的過(guò)程，稱此二叉樹(shù)為折半查找的判定樹(shù)。例如對(duì)上述含有11個(gè)記錄的有序表，查找過(guò)程的判定樹(shù)如圖8.1所示。圖8.1折半查找的判定樹(shù)假設(shè)每個(gè)記錄的查找概率相同，則從圖8.1所示判定樹(shù)可知，對(duì)長(zhǎng)度為11的表進(jìn)行折半查找，其查找成功時(shí)的平均查找長(zhǎng)度為查找表中任一元素的過(guò)程，即是與判定樹(shù)中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵字的比較次數(shù)，也即該元素結(jié)點(diǎn)在樹(shù)中的層次數(shù)。因此，折半查找在查找成功時(shí)進(jìn)行關(guān)鍵字比較的次數(shù)最多不超過(guò)樹(shù)的深度。對(duì)于n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為。折半查找在查找成功時(shí)，所進(jìn)行的關(guān)鍵字比較次數(shù)至多為。所以，折半查找的時(shí)間復(fù)雜度為O(lbn)，顯然比順序查找效率高。3、插值查找折半查找算法中的語(yǔ)句6：mid=(low+high)/2，我們可以進(jìn)行修改。插值查找通過(guò)下列公式：求取中點(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，查找成功。我們只要修改折半查找算法的語(yǔ)句6，就得到另一種有序順序表的查找方法。插值查找的時(shí)間效率依然是O(lbn)。8.2.3索引順序表當(dāng)順序表中的數(shù)據(jù)元素個(gè)數(shù)非常大時(shí)，為了提高查找速度，可在順序表上建立索引表。要使索引表的查找效率高，索引表必須有序。如圖8.2所示為一個(gè)索引順序表，其中包含3大塊，每一塊含有4個(gè)記錄。圖8.2索引順序表示例分塊查找又稱索引順序查找，其性能介于順序查找和折半查找之間，它適合于對(duì)關(guān)鍵字“分塊有序”的查找表進(jìn)行查找操作。分塊查找法要求將查找表組織成以下索引順序結(jié)構(gòu)：首先，將表分成若干塊(子表)。一般情況下，塊的長(zhǎng)度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無(wú)序，但塊與塊之間有序。然后，構(gòu)造一個(gè)索引表。其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字(或最小關(guān)鍵字)。索引表按關(guān)鍵字有序排列。分塊查找過(guò)程如下：第一步，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。具體可用順序查找法或折半查找法進(jìn)行。第二步，用順序查找法，在相應(yīng)的塊內(nèi)查找關(guān)鍵字為K的記錄。由以上分析可知，分塊查找的平均查找長(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。若用順序查找法確定待查元素所在塊，則有：可見(jiàn)，此時(shí)的平均查找長(zhǎng)度不僅和表長(zhǎng)n有關(guān)，而且和每一個(gè)塊中元素個(gè)數(shù)s有關(guān)。8.2.4倒排表最簡(jiǎn)單、最基礎(chǔ)的查找表的組織技術(shù)——倒排表。倒排索引的優(yōu)點(diǎn)就是查找記錄非常快，在索引表生成之后，查找不用去讀取記錄，就可以得到結(jié)果。但也有明顯的缺點(diǎn)，就是表中記錄號(hào)不定長(zhǎng)。倒排索引中的記錄號(hào)比較復(fù)雜，維護(hù)起來(lái)就比較困難，其插入、刪除操作就需要做相應(yīng)處理?？刹捎门刻幚恚簿褪抢鄯e到一定規(guī)模后再處理。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ù)。圖8.3所示為一個(gè)二叉排序樹(shù)。由二叉排序樹(shù)的定義可以得出一個(gè)重要性質(zhì)：中序遍歷一棵二叉排序樹(shù)時(shí)可以得到一個(gè)遞增有序序列。對(duì)圖8.3進(jìn)行中序遍歷，可得到序列：06，15，39，58，67，76，80，88，97圖8.3二叉排序樹(shù)示例2、二叉排序樹(shù)的查找過(guò)程對(duì)二叉排序樹(shù)進(jìn)行查找的過(guò)程類似于在折半查找判定樹(shù)上所進(jìn)行的查找過(guò)程，其不同之處為：折半查找的判定樹(shù)是靜態(tài)的，二叉排序樹(shù)是動(dòng)態(tài)的。在二叉排序樹(shù)中進(jìn)行查找的過(guò)程為：首先將給定值和根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等，則查找成功；否則，依據(jù)給定值小于或大于根結(jié)點(diǎn)的關(guān)鍵字，繼續(xù)在左子樹(shù)或右子樹(shù)中進(jìn)行查找，直到查找成功或者左子樹(shù)或右子樹(shù)為空，后者說(shuō)明查找不成功。二叉排序樹(shù)的特性：通過(guò)和根結(jié)點(diǎn)關(guān)鍵字的比較可將繼續(xù)查找的范圍縮小到某一棵子樹(shù)中。二叉排序樹(shù)的查找算法如下：SearchBST函數(shù)是一個(gè)遞歸函數(shù)，在二叉排序樹(shù)中進(jìn)行查找，其時(shí)間復(fù)雜度和樹(shù)的形態(tài)有關(guān)系。1BSTreeSearchBST(BSTreebt,KeyTypekey)/*在根指針bt所指二叉排序樹(shù)中，查找關(guān)鍵字等于key的元素，若查找成功，則返回指向該元素的指針，否則返回空指針*/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è)KeyType為整型，構(gòu)造二叉排序樹(shù)的算法如下所示：1voidCreateBST(BSTree*bt) /*從鍵盤輸入元素值，

建立相應(yīng)二叉排序樹(shù)*/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}有一關(guān)鍵字序列：56，26，67，12，37，98，按上述算法建立二叉排序樹(shù)的過(guò)程如圖8.4所示。圖8.4二叉排序樹(shù)的建立過(guò)程對(duì)于同樣的元素，如果輸入順序不同，構(gòu)造的二叉排序樹(shù)形狀不同。如果輸入順序?yàn)椋?6，67，12，37，56，98，則構(gòu)造的二叉排序樹(shù)如圖8.5所示。圖8.5輸入順序不同所建立的不同的二叉樹(shù)4、二叉排序樹(shù)的刪除在二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)，不能將以該結(jié)點(diǎn)為根的子樹(shù)全部刪除，只能刪除該結(jié)點(diǎn)并使得二叉樹(shù)依然滿足二叉排序樹(shù)的性質(zhì)。在二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)的過(guò)程描述如下：查找待刪結(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);②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ù)，如圖8.6(a)所示，此時(shí)有兩種處理方法：圖8.6二叉排序樹(shù)中刪除結(jié)點(diǎn)處理方法一圖示方法一：首先找到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);結(jié)果如圖8.6(b)所示。方法二：首先找到p結(jié)點(diǎn)在二叉排序樹(shù)的中序遍歷序列中的直接前驅(qū)s結(jié)點(diǎn)，q為s結(jié)點(diǎn)的雙親，如圖8.7(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);結(jié)果如圖8.7(b)所示。如果s結(jié)點(diǎn)是p結(jié)點(diǎn)的左子樹(shù)的根，q等于p，如圖8.7(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é)果如圖8.7(d)所示。圖8.7二叉排序樹(shù)中刪除結(jié)點(diǎn)處理方法二圖示將其三種情況綜合所得的刪除算法如下所示：1BSTreeDelBST(BSTreebt,KeyTypek)/*若二叉排序樹(shù)bt中存在關(guān)鍵字等于k的數(shù)據(jù)元素，則刪除之*/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的值*/20if(q!=p)q->rchild=s->lchild; /*原s結(jié)點(diǎn)的左子樹(shù)改為s結(jié)點(diǎn)的雙親q的右子樹(shù)*/21elseq->lchild=s->lchild;22free(s);23}24else25{26if(!p->rchild) /*p左子樹(shù)不空*/27{q=p;28p=p->lchild;29}30else /*p右子樹(shù)不空*/31{q=p;32p=p->rchild;33}34if(!f)bt=p;35else36if(q==f->lchild)f->lchild=p;37elsef->rchild=p;38free(q);39}40returnbt;41}5、二叉排序樹(shù)的查找性能分析在二叉排序樹(shù)上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到待查結(jié)點(diǎn)的路徑；若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。在二叉排序樹(shù)中查找到一個(gè)記錄時(shí)，其比較次數(shù)不超過(guò)樹(shù)的深度。二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)，二叉排序樹(shù)的深度越淺，其平均查找長(zhǎng)度ASL越小。例如，圖8.8所示的兩棵二叉排序樹(shù)，假設(shè)每個(gè)元素的查找概率相同，則它們的平均查找長(zhǎng)度分別是：(a)圖：(b)圖：圖8.8二叉排序樹(shù)的不同形態(tài)在二叉排序樹(shù)上進(jìn)行查找時(shí)的平均查找長(zhǎng)度與二叉排序樹(shù)的形態(tài)有關(guān)，對(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。如圖8.9(a)是一棵平衡二叉樹(shù)，(b)不是平衡二叉樹(shù)。圖8.9平衡二叉樹(shù)示例序列{13,24,37,90,53}，構(gòu)建二叉排序樹(shù)的過(guò)程如圖8.10所示。圖8.10平衡二叉樹(shù)生成過(guò)程假設(shè)由于二叉排序樹(shù)上插入結(jié)點(diǎn)而失去平衡的最小子樹(shù)的根結(jié)點(diǎn)指針為a，失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為以下四種情況：(1)LL型平衡旋轉(zhuǎn)。如圖8.11所示，在結(jié)點(diǎn)A的左子樹(shù)的左子樹(shù)上插入新結(jié)點(diǎn)S后導(dǎo)致失衡，為恢復(fù)平衡，可將A改為B的右子樹(shù)，B原來(lái)的右子樹(shù)BR改為A的左子樹(shù)，這相當(dāng)于以B為軸對(duì)A做了一次順時(shí)針旋轉(zhuǎn)。圖8.11LL型旋轉(zhuǎn)(2)RR型平衡旋轉(zhuǎn)。如圖8.12所示，在結(jié)點(diǎn)A的右子樹(shù)的右子樹(shù)上插入新結(jié)點(diǎn)S后導(dǎo)致失衡，為恢復(fù)平衡，可將A改為B的左子樹(shù)，B原來(lái)的左子樹(shù)BL改為A的右子樹(shù)，這相當(dāng)于以B為軸對(duì)A做了一次逆時(shí)針旋轉(zhuǎn)。圖8.12RR型旋轉(zhuǎn)(3)LR型平衡旋轉(zhuǎn)。如圖8.13所示，在結(jié)點(diǎn)A的左子樹(shù)的右子樹(shù)上插入新結(jié)點(diǎn)S后導(dǎo)致失衡，為恢復(fù)平衡，可將B改為C的左子樹(shù)，而C原來(lái)的左子樹(shù)CL改為B的右子樹(shù)，然后將A改為C的右子樹(shù)，C原來(lái)的右子樹(shù)CR改為A的左子樹(shù)。圖8.13LR型旋轉(zhuǎn)(4)RL型平衡旋轉(zhuǎn)。如圖8.14所示，在結(jié)點(diǎn)A的右子樹(shù)的左子樹(shù)上插入新結(jié)點(diǎn)S后導(dǎo)致失衡，為恢復(fù)平衡，可將B改為C的右子樹(shù)，而C原來(lái)的右子樹(shù)CR改為B的左子樹(shù)，然后將A改為C的左子樹(shù)，C原來(lái)的左子樹(shù)CL改為A的右子樹(shù)。圖8.14RL型旋轉(zhuǎn)平衡旋轉(zhuǎn)是當(dāng)二叉排序樹(shù)在插入結(jié)點(diǎn)后產(chǎn)生不平衡時(shí)進(jìn)行的,要建立一棵平衡的二叉排序樹(shù)，需要對(duì)前面的算法CreateBST作如下幾點(diǎn)修改：(1)判別插入結(jié)點(diǎn)之后是否產(chǎn)生不平衡；(2)找到失去平衡的最小子樹(shù)；(3)判別旋轉(zhuǎn)類型并作相應(yīng)調(diào)整。在對(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ù)是否失去平衡。若是，則需判別旋轉(zhuǎn)類型并作相應(yīng)處理，否則插入過(guò)程結(jié)束。8.3.3

B樹(shù)1、B樹(shù)及其查找B樹(shù)是一種平衡的多路查找樹(shù)，它在文件系統(tǒng)中很有用。其定義如下：一棵m階的B樹(shù)，或者為空樹(shù)，或?yàn)闈M足下列特性的m叉樹(shù)：(1)樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；(2)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)；(3)除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有

棵子樹(shù)；(4)所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：(n，A0，K1，A1，K2，…，Kn，An)其中：Ki為關(guān)鍵字，且Ki<Ki+1，Ai為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai-1所指結(jié)點(diǎn)的關(guān)鍵字均小于Ki，An所指結(jié)點(diǎn)的關(guān)鍵字均大于Kn。(5)所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息。如圖8.15所示為一棵4階的B樹(shù)，其深度為4。圖8.15一棵4階B樹(shù)在B樹(shù)上進(jìn)行查找的過(guò)程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交替進(jìn)行的過(guò)程。B樹(shù)主要用作文件的索引，因此它的查找涉及外存的存取，我們略去外存的讀寫，這里只作示意性描述。假設(shè)采用如下結(jié)點(diǎn)結(jié)構(gòu)：

＃definem<階數(shù)>

typedefstructMbtnode{

structMbtnode*parent;intkeynum;

/*結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)*/KeyTypekey[m+1];

/*關(guān)鍵字向量，0號(hào)單元未用*/structMbtnode*ptr[m+1];

/*子樹(shù)指針向量*/}Mbtnode,*Mbtree;在B樹(shù)中查找關(guān)鍵字為K的元素的算法描述如下：(1)從B樹(shù)的根結(jié)點(diǎn)開(kāi)始，在結(jié)點(diǎn)中查找K，如果找到則查找結(jié)束；否則，若Ki<K<Ki+1，則順著該結(jié)點(diǎn)的子樹(shù)指針Ai找到相應(yīng)結(jié)點(diǎn)。(2)如果Ai=NULL，則B樹(shù)中不存在K，查找失敗，否則在Ai所指的結(jié)點(diǎn)中查找K，如果找到則結(jié)束；若Ki<K<Ki+1，則順著該結(jié)點(diǎn)的子樹(shù)指針Ai找相應(yīng)結(jié)點(diǎn)，重復(fù)(2)。2、B樹(shù)查找分析在B樹(shù)上進(jìn)行查找包含兩種基本操作：①在B樹(shù)中找結(jié)點(diǎn)；②在結(jié)點(diǎn)中找關(guān)鍵字。在磁盤上查找比在內(nèi)存中查找耗費(fèi)的時(shí)間多得多，因此，待查關(guān)鍵字所在結(jié)點(diǎn)在B樹(shù)上的層次數(shù)，是決定B樹(shù)查找效率的首要因素。若m階B樹(shù)中具有N個(gè)關(guān)鍵字，則葉子結(jié)點(diǎn)即為查找不成功的結(jié)點(diǎn)有N+1個(gè)，假設(shè)，B樹(shù)的深度為h+1，即h+1層為葉子結(jié)點(diǎn)，則有：則有在含有N個(gè)關(guān)鍵字的B樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過(guò)。3、B樹(shù)的插入和刪除1）B樹(shù)的插入關(guān)鍵字的插入不是在葉結(jié)點(diǎn)上進(jìn)行的，而是在最底層的某個(gè)非葉子結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字。在m階B樹(shù)中插入一個(gè)關(guān)鍵字的算法如下：①在m階B樹(shù)中查找待插入關(guān)鍵字的插入位置，插入位置是最底層的某個(gè)非葉子結(jié)點(diǎn)。②把關(guān)鍵字插入到該結(jié)點(diǎn)中。③判斷插入后的結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，如果小于m-1，則插入成功。④如果關(guān)鍵字個(gè)數(shù)等于m-1，則分裂該結(jié)點(diǎn)，將相應(yīng)關(guān)鍵字上移到父結(jié)點(diǎn)。⑤重復(fù)③、④。圖8.16給出了一個(gè)B樹(shù)的插入實(shí)例。圖8.16B樹(shù)的插入實(shí)例圖8.16B樹(shù)的插入實(shí)例2）B樹(shù)的刪除在B樹(shù)上刪除一個(gè)關(guān)鍵字K，首先要查找到該關(guān)鍵字所在的結(jié)點(diǎn)，然后根據(jù)下面的兩種情況進(jìn)行刪除：(1)待刪除的關(guān)鍵字在最下層非葉子結(jié)點(diǎn)。圖8.17給出了在B樹(shù)最下層結(jié)點(diǎn)中刪除關(guān)鍵字的實(shí)例。(2)在非最下層結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字。圖8.18給出了在B樹(shù)的非最下層結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字的實(shí)例。圖8.17在B樹(shù)最下層結(jié)點(diǎn)中刪除關(guān)鍵字圖8.17在B樹(shù)最下層結(jié)點(diǎn)中刪除關(guān)鍵字圖8.18在B樹(shù)非最下層刪除關(guān)鍵字8.4哈希表的查找

8.4.1什么是哈希表哈希表又叫雜湊表或散列表。其基本思想是：在數(shù)據(jù)元素的關(guān)鍵字k和數(shù)據(jù)元素的存儲(chǔ)位置addr之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得addr=H(k)，H稱為哈希函數(shù)。理想情況是希望不經(jīng)過(guò)任何比較，一次存取便能獲得所查記錄，即哈希函數(shù)在關(guān)鍵字和地址之間建立一一對(duì)應(yīng)關(guān)系。當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)得到相同的地址，即k1≠k2，但H(k1)=H(k2)，這種現(xiàn)象稱為沖突。哈希表的構(gòu)造及查找主要包括以下兩方面的內(nèi)容：①如何構(gòu)造哈希函數(shù)；②如何處理沖突。8.4.2哈希函數(shù)的構(gòu)造方法一個(gè)好的哈希函數(shù)能將給定的數(shù)據(jù)集合均勻地散列到地址區(qū)間中。下面介紹構(gòu)造哈希函數(shù)常用的六種方法：(4)疊加法(5)除留余數(shù)法(6)偽隨機(jī)數(shù)法(1)直接定址法(2)數(shù)字分析法(3)平方取中法哈希函數(shù)的選擇，通常應(yīng)考慮以下五個(gè)因素：①計(jì)算哈希函數(shù)所需的時(shí)間②關(guān)鍵字的長(zhǎng)度③哈希表的長(zhǎng)度④關(guān)鍵字的分布⑤記錄查找的頻率8.4.3處理沖突的方法通過(guò)構(gòu)造性能良好的哈希函數(shù)可以減少?zèng)_突，但一般不可能完全避免沖突，創(chuàng)建哈希表和查找哈希表都會(huì)遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)一致。下面以創(chuàng)建哈希表為例說(shuō)明解決沖突的方法。常用的解決沖突的方法有以下四種：(1)開(kāi)放定址法(2)鏈地址法(3)再哈希(4)建立公共溢出區(qū)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)元素存入其中。這種方法利用下列公式計(jì)算求得下一個(gè)地址：

Hi=(H(key)+di)%m其中，H(key)為哈希函數(shù)；m為表長(zhǎng)，di稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也就不同。主要有以下三種：(1)線性探測(cè)再散列(2)二次探測(cè)再散列(3)偽隨機(jī)探測(cè)再散列圖8.20為開(kāi)放定址法處理沖突示例，哈希表長(zhǎng)為11，哈希函數(shù)為：H(key)=key%11。圖8.20開(kāi)放定址法處理沖突示例2、鏈地址法鏈地址法的基本思想是：將所有關(guān)鍵字是同義詞的元素連接成一條線性鏈表，并將其鏈頭存在相應(yīng)的哈希地址所指的存儲(chǔ)單元中。鏈地址法用于經(jīng)常進(jìn)行插入和刪除的情況。

例如，一組關(guān)鍵字(71，27，26，30，16，46，19，42，24，49，64)，哈希表長(zhǎng)為13，哈希函數(shù)為：H(key)=key%13，則用鏈地址法處理沖突的結(jié)果如圖8.21所示。圖8.21鏈地址法處理沖突時(shí)的哈希表3、再哈希再哈希的基本思想是：當(dāng)發(fā)生沖突時(shí)，再用另一個(gè)哈希函數(shù)來(lái)計(jì)算下一個(gè)哈