數(shù)據(jù)結(jié)構(gòu)（第2版）（C語言實現(xiàn)）課件：查找

查找

本書在第2章至第6章中已經(jīng)介紹了各種線性和非線性的數(shù)據(jù)結(jié)構(gòu)，在這一章將討論另一種在實際應(yīng)用中大量使用的重要技術(shù)──查找。在計算機處理非數(shù)值問題時，查找是一種經(jīng)常使用和非常重要的操作。本章主要介紹查找的基本概念、靜態(tài)查找、動態(tài)查找、哈希表及查找。

本章重點和難點：

1、折半查找

2、索引順序表的查找

3、二叉排序樹和平衡二叉樹

4、B-樹

5、哈希表的構(gòu)造與查找7.1查找的基本概念

關(guān)鍵字(key)與主關(guān)鍵字(primarykey)：數(shù)據(jù)元素中某個數(shù)據(jù)項的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標識一個數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字(secondarykey)。特別地，如果數(shù)據(jù)元素只有一個數(shù)據(jù)項，則數(shù)據(jù)元素的值即是關(guān)鍵字。查找表(searchtable)：是由同一種類型的數(shù)據(jù)元素構(gòu)成的集合。查找表中的數(shù)據(jù)元素是完全松散的，數(shù)據(jù)元素之間沒有直接的聯(lián)系。7.1查找的基本概念

查找(searching)：根據(jù)關(guān)鍵字在特定的查找表中找到一個與給定關(guān)鍵字相同的數(shù)據(jù)元素的操作。如果在表中找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則，稱查找是失敗的。例如，表7.1中為學(xué)生學(xué)籍信息，如果要查找入學(xué)年份為“2008年”并且姓名是“劉華平”的學(xué)生，則可以先利用姓名將記錄定位（如果有重名的），然后在入學(xué)年份中查找為“2008”的記錄。表7.1學(xué)生學(xué)籍信息表7.1查找的基本概念

關(guān)鍵字（Key）與主關(guān)鍵字（PrimaryKey）：數(shù)據(jù)元素中某個數(shù)據(jù)項的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標識一個數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字。特別地，如果數(shù)據(jù)元素只有一個數(shù)據(jù)項，則數(shù)據(jù)元素的值即是關(guān)鍵字。

靜態(tài)查找（StaticSearchTable）：指的是僅僅在數(shù)據(jù)元素集合中查找是否存在與關(guān)鍵字相等的數(shù)據(jù)元素。在靜態(tài)查找過程中的存儲結(jié)構(gòu)稱為靜態(tài)查找表。

動態(tài)查找（DynamicSearchTable）：在查找過程中，同時在數(shù)據(jù)元素集合中插入數(shù)據(jù)元素，或者在數(shù)據(jù)元素集合中刪除某個數(shù)據(jù)元素，這樣的查找稱為動態(tài)查找。動態(tài)查找過程中所使用的存儲結(jié)構(gòu)稱為動態(tài)查找表。7.1查找的基本概念

平均查找長度(averagesearchlength)：是指在查找過程中，需要比較關(guān)鍵字的平均次數(shù)，它是衡量查找算法的效率標準。平均查找長度的數(shù)學(xué)定義為：ASL=。其中，Pi表示查找表中第i個數(shù)據(jù)元素的概率，Ci表示在找到第i個數(shù)據(jù)元素時，與關(guān)鍵字比較的次數(shù)。

7.2靜態(tài)查找7.2.1順序表的查找順序表的存儲結(jié)構(gòu)如下。

#defineMaxSize100typedefstruct{KeyTypekey;}DataType;typedefstruct{DataTypelist[MaxSize];intlength;}SSTable;7.2靜態(tài)查找順序表的查找算法描述如下：intSeqSearch(SSTableS,DataTypex)/*在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=0;while(i<S.length&&S.list[i].key!=x.key)/*從順序表的第一個元素開始比較*/i++;if(S.list[i].key==x.key)returni+1;elsereturn0;}7.2靜態(tài)查找以上算法也可以通過設(shè)置監(jiān)視哨的方法實現(xiàn)，其算法描述如下：intSeqSearch2(SSTableS,DataTypex)/*設(shè)置監(jiān)視哨S.list[0]，在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=S.length;S.list[0].key=x.key; /*將關(guān)鍵字存放在第0號位置，防止越界*/while(S.list[i].key!=x.key)/*從順序表的最后一個元素開始向前比較*/i--;returni;}7.2靜態(tài)查找下面分析帶監(jiān)視哨查找算法的效率。假設(shè)表中有n個數(shù)據(jù)元素，且數(shù)據(jù)元素在表中的出現(xiàn)的概率都相等即，則順序表在查找成功時的平均查找長度為：

即查找成功時平均比較次數(shù)約為表長的一半。在查找失敗時，即要查找的元素沒有在表中，則每次比較都需要進行n+1次。7.2靜態(tài)查找7.2.2有序順序表的查找所謂有序順序表，就是順序表中的元素是以關(guān)鍵字進行有序排列的。對于有序順序表的查找有兩種方法：順序查找和折半查找。

1．順序查找有序順序表的順序查找算法與順序表的查找算法類似。在通常情況下，無須比較表中的所有元素。如果要查找的元素在表中，則返回該元素的序號，否則返回0。7.2靜態(tài)查找intSeqSearch2(SSTableS,DataTypex)/*設(shè)置監(jiān)視哨S.list[0]，在有序順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{inti=S.length;S.list[0].key=x.key;/*將關(guān)鍵字存放在第0號位置，防止越界*/while(S.list[i].key>x.key) /*從有序順序表的最后一個元素開始向前比較*/

i--;if(S.list[i].key==x.key)

returni;return0;}7.2靜態(tài)查找

設(shè)表中的元素個數(shù)為n且要查找的數(shù)據(jù)元素在表中出現(xiàn)的概率相等即為，則有序順序表在查找成功時的平均查找長度為：

即查找成功時平均比較次數(shù)約為表長的一半。在查找失敗時，即要查找的元素沒有在表中，則有序順序表在查找失敗時的平均查找長度為：7.2靜態(tài)查找2．折半查找折半查找（binarysearch）又稱為二分查找，這種查找算法要求待查找的元素序列必須是從小到大排列的有序序列。折半查找的算法描述如下：將待查找元素與表中間的元素進行比較，如果兩者相等，則說明查找成功；否則利用中間位置將表分成兩部分，如果待查找元素小于中間位置的元素值，則繼續(xù)與前一個子表的中間位置元素進行比較；否則與后一個子表的中間位置元素進行比較。不斷重復(fù)以上操作，直到找到與待查找元素相等的元素，表明查找成功。如果子表變?yōu)榭毡恚砻鞑檎沂　?.2靜態(tài)查找

例如，一個有序順序表為（9，23，26，32，36，47，56，63，79，81）,如果要查找56。利用以上折半查找思想，折半查找的過程如圖11.1所示。其中，圖中l(wèi)ow和high表示兩個指針，分別指向待查找元素的下界和上界，指針mid指向low和high的中間位置，即mid=(low+high)/2。7.2靜態(tài)查找折半查找的算法描述如下。intBinarySearch(SSTableS,DataTypex)/*在有序順序表中折半查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0*/{ intlow,high,mid; low=0,high=S.length-1; /*設(shè)置待查找元素范圍的下界和上界*/ while(low<=high) { mid=(low+high)/2; if(S.list[mid].key==x.key) /*如果找到元素，則返回該元素所在的位置*/ returnmid+1; elseif(S.list[mid].key<x.key) /*如果mid所指示的元素小于關(guān)鍵字，則修改low指針*/ low=mid+1; elseif(S.list[mid].key>x.key) /*如果mid所指示的元素大于關(guān)鍵字，則修改high指針*/ high=mid-1; } return0;}7.2靜態(tài)查找

用折半查找算法查找關(guān)鍵字56的元素時，需要比較的次數(shù)為4個。從圖7.1中可以看出，查找元素36時需要比較1次，查找元素63時需要比較2次，查找元素47時需要比較3次，查找56需要比較4次。整個查找過程可以用圖7.2所示的二叉判定樹來表示。。7.2靜態(tài)查找對于具有n個結(jié)點的有序表剛好能夠構(gòu)成一個深度為h的滿二叉樹，則有h=。二叉樹中第i層的結(jié)點個數(shù)是2i-1，假設(shè)表中每個元素的查找概率相等，即Pi=。則有序表的折半查找成功時的平均查找長度為：

查找失敗時，有序表的折半查找失敗時的平均查找長度為：7.2靜態(tài)查找7.2.3索引順序表的查找當順序表中的數(shù)據(jù)量非常大時，無論使用前述哪種查找算法都需要很長的時間，此時提高查找效率的一個常用方法就是在順序表中建立索引表。建立索引表的方法是將順序表分為幾個單元，然后分別為這幾個單元建立一個索引，我們把原來的順序表稱為主表，提供索引的表稱為索引表。索引表中只存放主表中要查找的數(shù)據(jù)元素的主關(guān)鍵字和索引信息。圖7.3是一個主表和一個按關(guān)鍵字建立的索引表結(jié)構(gòu)圖。7.2靜態(tài)查找因索引表中的元素的關(guān)鍵字是有序的，故在確定元素所在主表的單元時，既可采用順序查找法也可采用折半查找法，但對于主表，只能采用順序法查找。索引順序表的平均查找長度可以表示為：ASL=Lindex+Lunit。其中，Lindex是索引表的平均查找長度，Lunit是單元中元素的平均查找長度。假設(shè)主表中的元素個數(shù)為n，并將該主表平均分為b個單元，且每個單元有s個元素，即b=n/s。如果表中的元素查找概率相等，則每個單元中元素的查找概率就是1/s，主表中每個單元的查找概率是1/b。如果用順序查找法查找索引表中的元素，則索引順序表查找成功時的平均查找長度為：ASL成功=。7.2靜態(tài)查找

當然，如果主表中每個單元中的元素個數(shù)是不相等的時候，就需要在索引表中增加一項，即用來存儲主表中每個單元元素的個數(shù)。將這種利用索引表示的順序表稱為不等長索引順序表。例如，一個不等長的索引表如圖7.4所示。7.3動態(tài)查找7.3.1二叉排序樹二叉排序樹也稱為二叉查找樹。二叉排序樹的查找是一種常用的動態(tài)查找方法。

1．什么是二叉排序樹所謂二叉排序樹（binarysorttree），或者是一棵空二叉樹，或者二叉樹具有以下性質(zhì)：（1）如果二叉樹的左子樹不為空，則左子樹上的每一個結(jié)點的值均小于其對應(yīng)根結(jié)點的值；（2）如果二叉樹的右子樹不為空，則右子樹上的每一個結(jié)點的值均大于其對應(yīng)根結(jié)點的值；（3）該二叉樹的左子樹和右子樹也滿足性質(zhì)（1）和（2），即左子樹和右子樹也是一棵二叉排序樹。7.3動態(tài)查找一棵二叉排序樹如圖7.5所示。

從圖7.5中可以看出，圖中的每個結(jié)點的值都大于其所有左子樹結(jié)點的值，而小于其所有右子樹中結(jié)點的值。如果要查找與二叉樹中某個關(guān)鍵字相等的結(jié)點，可以從根結(jié)點開始，與給定的關(guān)鍵字比較，如果相等，則查找成功。如果給定的關(guān)鍵字小于根結(jié)點的值，則在該根結(jié)點的左子樹中查找。如果給定的關(guān)鍵字大于根結(jié)點的值，則在該根結(jié)點的右子樹中查找。7.3動態(tài)查找

2．查找算法采用鏈式存儲結(jié)構(gòu)的二叉排序樹的類型定義如下：

typedefstructNode{DataTypedata;structNode*lchild,*rchild;}BiTreeNode,*BiTree;7.3動態(tài)查找BiTreeBSTSearch(BiTreeT,DataTypex)/*二叉排序樹的查找，如果找到元素x，則返回指向結(jié)點的指針，否則返回NULL*/{ BiTreeNode*p; if(T!=NULL) /*如果二叉排序樹不為空*/ { p=T; while(p!=NULL) { if(p->data.key==x.key)/*找到則返回指向該結(jié)點的指針*/ returnp; elseif(x.key<p->data.key)/*如果關(guān)鍵字小于p指向的結(jié)點的值，則在左子樹中查找*/ p=p->lchild; else p=p->rchild; /*如果關(guān)鍵字大于p指向的結(jié)點的值，則在右子樹中查找*/ } }returnNULL;}7.3動態(tài)查找

在二叉排序樹的查找過程中，查找某個結(jié)點的過程正好是走了從根結(jié)點到要查找結(jié)點的路徑，其比較的次數(shù)正好是路徑長度+1，這類似于折半查找，與折半查找不同的是由n個結(jié)點構(gòu)成的判定樹是唯一的，而由n個結(jié)點構(gòu)成的二叉排序樹則不唯一。例如，圖7.6為兩棵二叉排序樹，其元素的關(guān)鍵字序列分別是{57，21，71，12，51，67，76}和{12，21，51，57，67，71，76}。7.3動態(tài)查找2．二叉排序樹的插入二叉排序樹的結(jié)構(gòu)不是一次生成的，而是在查找的過程中，當樹中不存在關(guān)鍵字等于給定值的結(jié)點時再進行插入。新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。二叉排序樹的插入操作過程其實就是二叉排序樹的建立過程。在算法的實現(xiàn)過程中，需要設(shè)置一個指向下一個要訪問結(jié)點的雙親結(jié)點指針parent，記下前驅(qū)結(jié)點的位置，以便在查找失敗時進行插入操作。7.3動態(tài)查找intBSTInsert(BiTree*T,DataTypex)/*二叉排序樹的插入操作，如果樹中不存在元素x，則將x插入到正確的位置并返回1，否則返回0*/{ BiTreeNode*p,*cur,*parent=NULL; cur=*T; while(cur!=NULL) { if(cur->data.key==x.key) /*二叉樹中存在元素為x的結(jié)點，則返回0*/ return0; parent=cur; /*parent指向cur的前驅(qū)結(jié)點*/ if(x.key<cur->data.key) /*如果關(guān)鍵字小于p指向的結(jié)點的值，則在左子樹中查找*/ cur=cur->lchild; else cur=cur->rchild; /*如果關(guān)鍵字大于p指向的結(jié)點的值，則在右子樹中查找*/ }7.3動態(tài)查找p=(BiTreeNode*)malloc(sizeof(BiTreeNode)); /*生成結(jié)點*/ if(!p) exit(-1); p->data=x; p->lchild=NULL; p->rchild=NULL; if(!parent) /*如果二叉樹為空，則第一結(jié)點成為根結(jié)點*/ *T=p; elseif(x.key<parent->data.key) /*如果關(guān)鍵字小于parent指向的結(jié)點，則將x成為parent的左孩子*/ parent->lchild=p; else/*如果關(guān)鍵字大于parent指向的結(jié)點，則將x成為parent的右孩子*/ parent->rchild=p; return1; }

對于一個關(guān)鍵字序列{37，32，35，62，82，95，73，12，5}，根據(jù)二叉排序樹的插入算法思想，插入過程如圖7.7所示。7.3動態(tài)查找7.3動態(tài)查找3．二叉排序樹的刪除如何在二叉樹排序樹中刪除一個結(jié)點呢？假設(shè)要刪除的結(jié)點由指針s指示，指針p指向s的雙親結(jié)點，設(shè)s為p的左孩子結(jié)點。刪除一個結(jié)點分為3種情況討論。刪除情形如圖7.8所示。（1）如果s指向的結(jié)點為葉子結(jié)點，其左子樹和右子樹為空，刪除葉子結(jié)點不會影響到樹的結(jié)構(gòu)特性，因此只需要修改p的指針即可。（2）如果s指向的結(jié)點只有左子樹或只有右子樹，在刪除了結(jié)點*s后，只需要將s的左子樹sL或右子樹sR作為p的左孩子即p->lchild=s->lchild或p->lchid=s->rchild。（3）若s存在左子樹和右子樹，在刪除結(jié)點T之前，二叉排序樹的中序序列為{…QLQ…XLXYLYTTRP…}，因此，在刪除了結(jié)點S之后，使該二叉樹仍然保持原來的性質(zhì)不變的調(diào)整方法有兩種：（1）使結(jié)點T的左子樹作為結(jié)點P的左子樹，結(jié)點T的右子樹作為結(jié)點Y的右子樹。（2）使結(jié)點T的直接前驅(qū)取代結(jié)點T，并刪除T的直接前驅(qū)結(jié)點Y，然后令結(jié)點Y原來的左子樹作為結(jié)點X的右子樹。如圖7.8所示。7.3動態(tài)查找二叉排序樹的刪除操作算法描述如下。intBSTDelete(BiTree*T,DataTypex)/*在二叉排序樹T中存在值為x的數(shù)據(jù)元素時，刪除該數(shù)據(jù)元素結(jié)點，并返回1，否則返回0*/{ if(!*T) /*如果不存在值為x的數(shù)據(jù)元素，則返回0*/ return0; else { if(x.key==(*T)->data.key)/*如果找到值為x的數(shù)據(jù)元素，則刪除該結(jié)點*/ DeleteNode(T); elseif((*T)->data.key>x.key) /*如果當前元素值大于x的值，則在該結(jié)點的左子樹中查找并刪除之*/ BSTDelete(&(*T)->lchild,x); else /*如果當前元素值小于x的值，則在該結(jié)點的右子樹中查找并刪除之*/ BSTDelete(&(*T)->rchild,x); return1; }}7.3動態(tài)查找voidDeleteNode(BiTree*s)/*從二叉排序樹中刪除結(jié)點s，并使該二叉排序樹性質(zhì)不變*/{ BiTreeq,x,y; if(!(*s)->rchild) /*如果s的右子樹為空，重接左子樹*/ { q=*s; *s=(*s)->lchild; free(q); } elseif(!(*s)->lchild) /*如果s的左子樹為空，重接右子樹*/ { q=*s; *s=(*s)->rchild; free(q); }7.3動態(tài)查找7.3動態(tài)查找 else /*如果s的左、右子樹都存在，則使s的直接前驅(qū)結(jié)點代替s，并使其直接前驅(qū)結(jié)點的左子樹成為其雙親結(jié)點的右子樹結(jié)點*/ { x=*s; y=(*s)->lchild; while(y->rchild) /*查找s的直接前驅(qū)結(jié)點，y為s的直接前驅(qū)結(jié)點，x為y的雙親結(jié)點*/ { x=y; y=y->rchild; } (*s)->data=y->data; /*結(jié)點s被y取代*/ if(x!=*s) /*如果結(jié)點s的左孩子結(jié)點存在右子樹*/ x->rchild=y->lchild;/*使y的左子樹成為x的右子樹*/ else /*如果結(jié)點s的左孩子結(jié)點不存在右子樹*/ x->lchild=y->lchild; /*使y的左子樹成為x的左子樹*/ free(y); }}5．二叉排序樹應(yīng)用舉例

【例7.1】給定一組元素序列{37,32,35,62,82,95,73,12,5}，利用二叉排序樹的插入算法創(chuàng)建一棵二叉排序樹，然后查找元素值為73的元素，并刪除元素32，然后以中序序列輸出該元素序列。7.3動態(tài)查找7.3.2平衡二叉樹若二叉排序樹的深度為n，在最壞的情況下平均查找長度為n。因此，為了減小二叉排序樹的查找次數(shù)，需要對二叉樹排序樹進行平衡化處理，平衡化處理得到的二叉樹稱為平衡二叉樹。

1．什么是平衡二叉樹平衡二叉樹（balancedbinarytree）又稱為AVL樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。7.3動態(tài)查找若將二叉樹中結(jié)點的平衡因子BF（balancefactor）定義為結(jié)點的左子樹的深度減去右子樹的深度，則平衡二叉樹中每個結(jié)點的平衡因子只可能是-1、0和1。如圖7.12所示為兩棵平衡二叉樹，結(jié)點的右邊表示平衡因子，因為該二叉樹既是二叉排序樹又是平衡樹，因此，該二叉樹稱為平衡二叉排序樹。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。如圖7.11所示為兩棵不平衡的二叉樹。7.3動態(tài)查找2．二叉排序樹的平衡處理在二叉排序樹中插入一個新結(jié)點后，如何保證該二叉樹是平衡二叉排序樹呢？設(shè)有一個關(guān)鍵字序列{7，36，45，78，65}，依照此關(guān)鍵字序列建立二叉排序樹，且使該二叉排序樹是平衡二叉排序樹。初始時，二叉樹為空樹，因此是平衡二叉樹。插入結(jié)點7和36后，該二叉樹依然是平衡的，結(jié)點7和結(jié)點36的平衡因子分別為-1和0。當插入結(jié)點45后，結(jié)點7的平衡因子變?yōu)?2，二叉樹變?yōu)椴黄胶?，這需要進行調(diào)整。以結(jié)點36為軸進行逆時針旋轉(zhuǎn)，將二叉樹變?yōu)橐?6為根，各個結(jié)點的平衡因子都為0，二叉樹恢復(fù)了平衡。7.3動態(tài)查找

繼續(xù)插入結(jié)點76，二叉樹仍然是平衡的。當插入結(jié)點65時，該二叉樹失去了平衡，如果仍然按照上述方法僅僅以結(jié)點45為軸進行旋轉(zhuǎn)，就會失去二叉排序樹的性質(zhì)。為了保持二叉排序樹的性質(zhì)，又要保證該二叉樹是平衡的，需要進行兩次調(diào)整：先以結(jié)點76為軸進行順時針旋轉(zhuǎn)，然后以結(jié)點65為軸進行逆時針旋轉(zhuǎn)。7.3動態(tài)查找

通過上述平衡化處理，我們得出一個結(jié)論：通過讓插入點最近的祖先結(jié)點恢復(fù)平衡，從而使上一層祖先結(jié)點恢復(fù)平衡。因此，為了使二叉排序樹恢復(fù)平衡，需要從離插入點最近的結(jié)點開始調(diào)整。平衡化二叉排序樹可分為以下4種情形。（1）LL型。LL型是指在離插入點最近的失衡結(jié)點的左子樹的左子樹中插入結(jié)點，導(dǎo)致二叉排序樹失去平衡。如圖7.13所示。距離插入點最近的失衡結(jié)點為A，插入新結(jié)點X后，結(jié)點A的平衡因子由1變?yōu)?，該二叉排序樹失去平衡。為了使二叉樹恢復(fù)平衡且保持二叉排序樹的性質(zhì)不變，可以使結(jié)點A作為結(jié)點B的右子樹，結(jié)點B的右子樹作為結(jié)點A的左子樹。這樣就恢復(fù)了該二叉排序樹的平衡，這相當于以結(jié)點B為軸，對結(jié)點A進行順時針旋轉(zhuǎn)。7.3動態(tài)查找

為平衡二叉排序樹的每個結(jié)點增加一個域bf，用來表示對應(yīng)結(jié)點的平衡因子。平衡二叉排序樹的類型如下：

typedefstructBSTNode /*平衡二叉排序樹的類型定義*/{ DataTypedata; intbf; /*結(jié)點的平衡因子*/ structBSTNode*lchild,*rchild;/*左、右孩子指針*/}BSTNode,*BSTree;7.3動態(tài)查找

對LL型二叉排序樹的平衡化處理代碼如下：

BSTreeb; b=p->lchild; /*lc指向p的左子樹的根結(jié)點*/ p->lchild=b->rchild; /*將lc的右子樹作為p的左子樹*/ b->rchild=p; p->bf=b->bf=0; /*修改平衡因子*/7.3動態(tài)查找

（2）LR型。LR型是指在離插入點最近的失衡結(jié)點的左子樹的右子樹中插入結(jié)點，導(dǎo)致二叉排序樹失去平衡。如圖7.14所示。這相當于以結(jié)點B為軸，對結(jié)點C先做了一次逆時針旋轉(zhuǎn)；然后以結(jié)點C為軸對結(jié)點A做了一次順時針旋轉(zhuǎn)。7.3動態(tài)查找7.3動態(tài)查找

（3）RL型。RL型是指在離插入點最近的失衡結(jié)點的右子樹的左子樹中插入結(jié)點，導(dǎo)致二叉排序樹失去平衡。如圖7.15所示。這相當于以結(jié)點B為軸，對結(jié)點C先做了一次順時針旋轉(zhuǎn)；然后以結(jié)點C為軸對結(jié)點A做了一次逆時針旋轉(zhuǎn)。7.3動態(tài)查找（4）RR型。RR型是指在離插入點最近的失衡結(jié)點的右子樹的右子樹中插入結(jié)點，導(dǎo)致二叉排序樹失去平衡。如圖7.16所示。這相當于以結(jié)點B為軸，對結(jié)點A做了一次逆時針旋轉(zhuǎn)。7.3動態(tài)查找

綜上以上4種情形，在平衡二叉排序樹中插入一個結(jié)點e后，若仍需保持二叉排序樹平衡的算法描述如下：（1）若平衡二叉排序樹是空樹，則插入的結(jié)點e作為根結(jié)點，并使該樹的深度增1；（2）若二叉樹中已存在與結(jié)點e的關(guān)鍵字相等的結(jié)點，則無須插入；（3）若結(jié)點e的關(guān)鍵字小于要插入位置的結(jié)點的關(guān)鍵字，則將e插入到該結(jié)點的左子樹位置，并使該結(jié)點的左子樹高度增1，同時修改該結(jié)點的平衡因子；如果該結(jié)點的平衡因子絕對值大于1，則需要進行平衡化處理；（4）若結(jié)點e的關(guān)鍵字大于要插入位置的結(jié)點的關(guān)鍵字，則將e插入到該結(jié)點的右子樹位置，并將該結(jié)點的右子樹高度增1，同時修改該結(jié)點的平衡因子；如果該結(jié)點的平衡因子絕對值大于1，則進行平衡化處理。7.3動態(tài)查找1．LL型的平衡處理對于LL型的失去平衡的情形，只需要對離插入點最近的失衡結(jié)點進行一次順時針旋轉(zhuǎn)處理即可。其算法實現(xiàn)如下。voidRightRotate(BSTree*p)/*對以*p為根的二叉排序樹進行右旋，處理之后p指向新的根結(jié)點，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點*/{ BSTreelc; lc=(*p)->lchild; /*lc指向p的左子樹的根結(jié)點*/ (*p)->lchild=lc->rchild; /*將lc的右子樹作為p的左子樹*/ lc->rchild=*p; (*p)->bf=lc->bf=0; *p=lc; /*p指向新的根結(jié)點*/}7.3動態(tài)查找2．LR型的平衡處理對于LR型的失去平衡的情形，需要進行兩次旋轉(zhuǎn)處理：先進行一次逆時針旋轉(zhuǎn)，然后再進行一次順時針旋轉(zhuǎn)處理。其算法實現(xiàn)如下。7.3動態(tài)查找3．RL型的平衡處理對于RL型的失去平衡的情形，需要進行兩次旋轉(zhuǎn)處理：先進行一次順時針旋轉(zhuǎn)，然后再進行一次逆時針旋轉(zhuǎn)處理。其算法實現(xiàn)如下。7.3動態(tài)查找4．RR型的平衡處理對于RR型的失去平衡的情形，只需要對離插入點最近的失衡結(jié)點進行一次逆時針旋轉(zhuǎn)處理即可。算法實現(xiàn)如下。voidLeftRotate(BSTree*p)/*對以*p為根的二叉排序樹進行左旋，處理之后p指向新的根結(jié)點，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點*/{ BSTreerc; rc=(*p)->rchild; /*rc指向p的右子樹的根結(jié)點*/ (*p)->rchild=rc->lchild;/*將rc的左子樹作為p的右子樹*/ rc->lchild=*p; *p=rc; /*p指向新的根結(jié)點*/}7.3.3紅黑樹紅黑二叉查找樹（red-blackBST），簡稱紅黑樹，顧名思義，它也是一種二叉查找樹，在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是紅或黑。紅黑樹是一種接近平衡的二叉樹。1．紅黑樹的定義紅黑樹是一棵具有以下特點的二叉查找樹：（1）每個結(jié)點不是紅色，就是黑色；（2）根結(jié)點的顏色為黑色；（3）葉子結(jié)點是空節(jié)點且為黑色；（4）若一個結(jié)點是紅色的，則孩子結(jié)點一定是黑色的，即從根結(jié)點到葉子結(jié)點的路徑中，不存在連續(xù)的紅色結(jié)點；（5）從任何一個結(jié)點出發(fā)到葉子結(jié)點的路徑上，包含相同數(shù)目的黑色結(jié)點。2．紅黑樹的基本運算1）紅黑樹的插入紅黑樹的插入也是在葉子結(jié)點處進行，插入的新結(jié)點作為紅黑樹的葉子結(jié)點。插入的結(jié)點被著色為紅色，然后以二叉排序樹的插入方法插入到紅黑樹中。假設(shè)插入的結(jié)點為T，其雙親結(jié)點P為紅色的，則P的雙親結(jié)點是黑色的。插入結(jié)點后，可分為兩種情況進行調(diào)整。（1）T的雙親結(jié)點P的兄弟結(jié)點U是黑色的情況如圖7-18(b)所示。圖中的a、b、c、d、e分別表示相應(yīng)的子樹。（2）T的雙親結(jié)點P的兄弟結(jié)點U是紅色的情況若T的雙親結(jié)點P的兄弟結(jié)點U是紅色時，不能再通過簡單的一次旋轉(zhuǎn)或兩次旋轉(zhuǎn)，調(diào)整兩個結(jié)點的顏色來恢復(fù)原有紅黑樹的性質(zhì)了。插入的結(jié)點T為紅色，當雙親結(jié)點P也為紅色時，則P的雙親結(jié)點G為黑色。若P的兄弟結(jié)點U為紅色，這需要重新對紅黑樹進行著色，即將G著色為紅色，P和U著色為黑色。如圖7.21所示。2）紅黑樹的刪除與插入操作一樣，在刪除了紅黑樹中的結(jié)點后，仍要使紅黑樹保持原有性質(zhì)不變。如果刪除的是葉子結(jié)點，刪除的結(jié)點可能為紅色或者黑色，若刪除的是紅色結(jié)點，由于刪除該結(jié)點不會影響到分支結(jié)點的數(shù)量，則直接刪除即可。如果刪除的是黑色結(jié)點，則需要進行調(diào)整操作。（1）D的兄弟結(jié)點S為黑色，且S至少有一個孩子結(jié)點是紅色。（2）D的兄弟結(jié)點S為黑色，且S的兩個孩子結(jié)點也是黑色的。（3）D的兄弟結(jié)點為紅色結(jié)點。7.4B-樹與B+樹7.4.1B-樹與二叉排序樹類似，B-樹是一種特殊的m叉動態(tài)查找樹。下面介紹B-樹的結(jié)構(gòu)與查找算法。

1．什么是B-樹

B-是一種平衡的多路查找樹，也稱為m路（叉）查找樹，它在文件系統(tǒng)中很有用。一棵m路（階）B-樹或者是一棵空樹，或者是滿足以下性質(zhì)的m叉樹：（1）任何一個結(jié)點最多有m棵子樹；（2）或者是根結(jié)點或者是葉子結(jié)點，或者至少有兩棵子樹；（3）除根結(jié)點外，所有非終端結(jié)點至少有棵子樹；（4）所有的非終端結(jié)點的結(jié)構(gòu)如下：7.4B-樹與B+樹

其中，n為結(jié)點中關(guān)鍵字的個數(shù)，-1≤n≤m-1，Pi為指向子樹根結(jié)點的指針，并且Pi指向子樹的每個結(jié)點關(guān)鍵字都小于Ki+1(i=0,1,…,n-1)。（5）所有葉子結(jié)點處于同一層次上，且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在）。例如，一棵深度為4的4階的B-樹如圖7.17所示。7.4B-樹與B+樹2．B-樹的查找

B-樹的查找其實是對二叉排序樹查找的擴展，與二叉排序樹不同的地方是，B-樹中每個結(jié)點有不止一棵子樹。在B-樹中查找某個結(jié)點時，需要先判斷要查找的結(jié)點在哪棵子樹上，然后在結(jié)點中逐個查找目標結(jié)點。B-樹的類型描述如下：

#definem4 /*B-樹的階數(shù)*/typedefstructBTNode /*B-樹類型定義*/{ intkeynum; /*每個結(jié)點中的關(guān)鍵字個數(shù)*/ structBTNode*parent; /*指向雙親結(jié)點*/ KeyTypedata[m+1]; /*結(jié)點中關(guān)鍵字信息*/ structBTNode*ptr[m+1]; /*指針向量*/}BTNode,*BTree;7.4B-樹與B+樹3．B-樹的插入操作在B-樹上插入結(jié)點與在二叉樹上插入結(jié)點類似，都是插入前后，保證B-樹仍然是一棵排序樹，即結(jié)點左子樹中每個結(jié)點的關(guān)鍵字小于根結(jié)點的關(guān)鍵字，右子樹結(jié)點的關(guān)鍵字大于根結(jié)點的關(guān)鍵字。但由于B-樹結(jié)點中的關(guān)鍵字個數(shù)必須≥-1，因此每次插入一個關(guān)鍵字不是在樹中添加一個葉子結(jié)點，而是首先在最低層的某個非終端結(jié)點中添加一個關(guān)鍵字，若該結(jié)點的關(guān)鍵字個數(shù)不超過m-1，則插入完成，否則對該結(jié)點進行分裂。7.4B-樹與B+樹

例如，圖7.18為一棵3階的B-樹（省略了葉子結(jié)點），當給定一棵B-樹的階之后，就確定了這棵樹的最少子樹個數(shù)為和最多子樹個數(shù)，確定了每個結(jié)點要求最少1個關(guān)鍵字，最多2個關(guān)鍵字。插入關(guān)鍵字42：首先需要從根結(jié)點開始，確定關(guān)鍵字42應(yīng)插入的位置應(yīng)該是結(jié)點E。因為插入后結(jié)點E中的關(guān)鍵字個數(shù)大于1（-1）小于2（m-1），所以插入成功。插入后B-樹如圖7.19所示。。7.4B-樹與B+樹插入關(guān)鍵字25：插入關(guān)鍵字78：7.4B-樹與B+樹

此時，結(jié)點C的關(guān)鍵字個數(shù)大于2，因此，需要將結(jié)點C進行分裂為兩個結(jié)點。將中間的關(guān)鍵字73插入到雙親結(jié)點A中，關(guān)鍵字83保留在C中，關(guān)鍵字67被插入到新結(jié)點C’中，并使關(guān)鍵字56的右指針指向結(jié)點C’，關(guān)鍵字73的右指針指向結(jié)點C。結(jié)點C的分裂過程如圖8.22所示。插入關(guān)鍵字43：7.4B-樹與B+樹

此時，結(jié)點B中的關(guān)鍵字個數(shù)大于2，需要進一步分解結(jié)點B，其中關(guān)鍵字32被插入到雙親結(jié)點A中，關(guān)鍵字24被保留在結(jié)點B中，關(guān)鍵字32被插入到新結(jié)點B’中，關(guān)鍵字24的左、右指針分別指向結(jié)點D和D’，關(guān)鍵字32的左、右指針分別指向結(jié)點E和E’。結(jié)點B被分裂的過程如圖7.25所示。。結(jié)點A被分裂的過程如圖7.26所示。7.4B-樹與B+樹4．B-樹的刪除操作

B-樹的刪除操作可分為3種情況：（1）要刪除的關(guān)鍵字所在結(jié)點的關(guān)鍵字個數(shù)大于等于，則只需要將關(guān)鍵字Ki和對應(yīng)的指針Pi從該結(jié)點中刪除即可。因為刪除該關(guān)鍵字后，該結(jié)點的關(guān)鍵字個數(shù)仍然不小于-1。例如，圖7.27顯示了從結(jié)點E中刪除關(guān)鍵字35的情形。7.4B-樹與B+樹

（2）被刪除的關(guān)鍵字所在結(jié)點的關(guān)鍵字個數(shù)等于，而與該結(jié)點相鄰的的右兄弟（或左兄弟）結(jié)點中的關(guān)鍵字個數(shù)大于-1，則刪除關(guān)鍵字后，需要將其兄弟結(jié)點中最小（或最大）的關(guān)鍵字上移至雙親結(jié)點中，將雙親結(jié)點中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點中。例如，將關(guān)鍵字89刪除后，需要將關(guān)鍵字73向上移動到雙親結(jié)點C中，并將關(guān)鍵字83下移到結(jié)點H中，得到如圖7.28所示的B-樹。7.4B-樹與B+樹

（3）被刪除的關(guān)鍵字所在結(jié)點和其相鄰的兄弟結(jié)點中的關(guān)鍵字個數(shù)均等于

，假設(shè)該結(jié)點有右兄弟，且其右兄弟結(jié)點地址由雙親結(jié)點中的指針Pi所指，則在刪除關(guān)鍵字之后，它所在的結(jié)點中剩余的關(guān)鍵字和指針，加上雙親結(jié)點中的關(guān)鍵字Ki一起，合并到Pi所指的兄弟結(jié)點中。若沒有右兄弟結(jié)點，則合并至左兄弟結(jié)點中。例如，將關(guān)鍵字83刪除后，需要將關(guān)鍵字83的左兄弟結(jié)點的關(guān)鍵字69與其雙親結(jié)點中的關(guān)鍵字73合并到一起，得到如圖7.29所示的B-樹。7.4B-樹與B+樹7.4.2B+樹

B+樹是B-樹的一種變型樹。一棵m階的B+樹和m階的B-樹的差異在于：（1）有n棵子樹的結(jié)點必有n個關(guān)鍵字，即關(guān)鍵字個數(shù)與結(jié)點的子樹個數(shù)相等；（2）所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小從小到大順序鏈接。（3）所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹（根結(jié)點）中的最大（或最小）關(guān)鍵字。7.5哈希表7.5.1什么是哈希表如何在查找元素的過程中，不與給定的關(guān)鍵字進行比較，就能確定所查找元素的存放位置。這就需要在元素的關(guān)鍵字與元素的存儲位置之間建立起一種對應(yīng)關(guān)系，使得元素的關(guān)鍵字與唯一的存儲位置對應(yīng)。有了這種對應(yīng)關(guān)系，在查找某個元素時，只需要利用這種確定的對應(yīng)關(guān)系，由給定的關(guān)鍵字就可以直接找到該元素。用key表示元素的關(guān)鍵字，f表示對應(yīng)關(guān)系，則f(key)表示元素的存儲地址，將這種對應(yīng)關(guān)系f稱為哈希函數(shù)，利用哈希函數(shù)可以建立哈希表。哈希表也稱為散列函數(shù)。表7.2哈希表示例7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)的目的主要是使哈希地址盡可能地均勻分布以減少或避免產(chǎn)生沖突、使計算方法盡可能地簡便以提高運算效率。哈希函數(shù)的構(gòu)造方法主要有以下幾種：

1．直接定址法

2．平方取中法

3．折疊法折疊法是將元素平均分割為若干等份，最后一個部分如果不夠可以空缺，然后將這幾個等份疊加求和作為哈希地址。這種方法主要用在元素的位數(shù)特別多且每一個元素的位數(shù)分布大體相當?shù)那闆r。例如，給定一個元素為23478245983，可以按照3位將該元素分割為幾個部分，其折疊計算過程如下：7.5哈希表4．除留余數(shù)法通過對元素取余，將得到的余數(shù)作為哈希地址。設(shè)哈希表長為m，p為小于等于m的最大質(zhì)數(shù)，則哈希函數(shù)為h(key)=key%p。例如，給定一組關(guān)鍵字{75，150，123，183，230，56，37，91}，設(shè)哈希表長m為14，取p=13則這組關(guān)鍵字的哈希地址存儲情況為7.5哈希表7.5.3處理沖突的方法處理沖突的方法常用的主要有：開放定址法、再哈希法和鏈地址法。

1．開放定址法開放定址法是解決沖突比較常用的方法。開放定址法就是利用哈希表中的空地址存儲產(chǎn)生沖突的關(guān)鍵字。當沖突發(fā)生時，按照下列公式處理沖突：

hi=(h(key)+di)%m,其中i=1,2,…,m-1

其中，h(key)為哈希函數(shù)，m為哈希表長，di為地址增量。地址增量di可以以下三種方法獲得：（1）線性探測再散列：在沖突發(fā)生時，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1;

（2）二次探測再散列：在沖突發(fā)生時，地址增量di依次取自然數(shù)的平方，即di=12，-12，22，-22,…,k2，-k2。（3）偽隨機數(shù)再散列：在沖突發(fā)生時，地址增量di依次取隨機數(shù)序列。7.5哈希表

例如，在長度為14的哈希表中，在將關(guān)鍵字183，123，230，91存放在哈希表中的情況如圖7.31所示。

當要插入關(guān)鍵字149時，由哈希函數(shù)h(149)=149%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測再散列法解決沖突，即h1=(6+1)%14=7，將149存儲在單元7中。如圖7.32所示。當要插入元素227時，7.5哈希表2．再哈希法再哈希法就是在沖突發(fā)生時，利用另外一個哈希函數(shù)再次求哈希函數(shù)的地址，直到?jīng)_突不再發(fā)生為止.3．鏈地址法鏈地址法就是將具有相同散列地址的關(guān)鍵字用一個線性鏈表存儲起來。每個線性鏈表設(shè)置一個頭指針指向該鏈表。鏈地址法的存儲表示類似于圖的鄰接表表示。在每一個鏈表中，所有的元素都是按照關(guān)鍵字有序排列。鏈地址法的主要優(yōu)點是在哈希表中增加元素和刪除元素方便。7.5哈希表

例如，一組關(guān)鍵字序列{23，35，12，56，123，39，342，90，78，110}，按照哈希函數(shù)h(key)=key%13和鏈地址法處理沖突，其哈希表如圖7.35所示。。7.5哈希表7.5.4哈希表查找與分析在哈希查找過程中，查找效率的高低除了與解決沖突的方法有關(guān)外，在處理沖突方法相同的情況下，其平均查找時間還依賴于哈希表的裝填因子，哈希表的裝填因子定義為：

裝填因子越小，表中填入的記錄就越小，發(fā)生沖突的可能性就會越??；反之，表中已填入的記錄越多，再繼續(xù)填充記錄時，發(fā)生沖突的可能性就越大，則查找時進行關(guān)鍵字查找的比較次數(shù)就會越多。7.5哈希表7.5.5哈希表應(yīng)用舉例

【例7.2】將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲在散列表中，散列表的存儲空間是一個下標從0開始的一維數(shù)組，散列函數(shù)為H(key)=(key*3)MOD7，處理沖突采用線性探測再散列法，要求裝填因子為0.7。

（1）請畫出構(gòu)造的散列表。

（2）分別計算等概率情況下查找成功和查找失敗時的平均查找長度。

【分析】（1）由題目已知條件裝填因子=0.7，可得到表長m為10。根據(jù)散列函數(shù)H(key)=(key*3)MOD7和處理沖突方法構(gòu)造哈希表。對于關(guān)鍵字7，H(7)=7*3%7=0對于關(guān)鍵字8，H(8)=8*3%7=3對于關(guān)鍵字30，H(30)=30*3%7=6對于關(guān)鍵字11，H(11)=11*3%7=57.5哈希