查找

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

本章重點和難點：

1、折半查找

2、索引順序表的查找

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

4、B-樹

5、哈希表的構造與查找7.1查找的基本概念

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

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

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

靜態查找（StaticSearchTable）：指的是僅僅在數據元素集合中查找是否存在與關鍵字相等的數據元素。在靜態查找過程中的存儲結構稱為靜態查找表。

動態查找（DynamicSearchTable）：在查找過程中，同時在數據元素集合中插入數據元素，或者在數據元素集合中刪除某個數據元素，這樣的查找稱為動態查找。動態查找過程中所使用的存儲結構稱為動態查找表。7.1查找的基本概念

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

7.2靜態查找7.2.1順序表的查找順序表的存儲結構如下。

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

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

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

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

returni;return0;}7.2靜態查找

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

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

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

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

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

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

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

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

2．查找算法采用鏈式存儲結構的二叉排序樹的類型定義如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1．什么是B-樹

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

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

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

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

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

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

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

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

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

（3）被刪除的關鍵字所在結點和其相鄰的兄弟結點中的關鍵字個數均等于

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

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

1．直接定址法

2．平方取中法

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

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

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

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

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

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

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

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

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

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

（1）請畫出構造的散列表。

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

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