鐵路枕木鋸材項目可行性報告(發(fā)改委評審通過案例范文)-專家咨詢

第10章查找10.1查找的根本概念本章小結10.2線性表的查找10.3樹表的查找10.4哈希表查找10.1查找的根本概念被查找的對象是由一組記錄組成的表或文件，而每個記錄那么由假設干個數(shù)據(jù)項組成，并假設每個記錄都有一個能惟一標識該記錄的關鍵字。在這種條件下，查找的定義是：給定一個值k，在含有n個記錄的表中找出關鍵字等于k的記錄。假設找到，那么查找成功，返回該記錄的信息或該記錄在表中的位置；否那么查找失敗，返回相關的指示信息。采用何種查找方法?(1)使用哪種數(shù)據(jù)結構來表示“表〞，即表中記錄是按何種方式組織的。(2)表中關鍵字的次序。是對無序集合查找還是對有序集合查找?假設在查找的同時對表做修改運算(如插入和刪除)，那么相應的表稱之為動態(tài)查找表，否那么稱之為靜態(tài)查找表。由于查找運算的主要運算是關鍵字的比較，所以通常把查找過程中對關鍵字需要執(zhí)行的平均比較次數(shù)(也稱為平均查找長度)作為衡量一個查找算法效率優(yōu)劣的標準。平均查找長度ASL(AverageSearchLength)定義為：其中，n是查找表中記錄的個數(shù)。pi是查找第i個記錄的概率，一般地，均認為每個記錄的查找概率相等，即pi=1/n(1≤i≤n)，ci是找到第i個記錄所需進行的比較次數(shù)。10.2線性表的查找

在表的組織方式中，線性表是最簡單的一種。三種在線性表上進行查找的方法：

(1)順序查找(2)二分查找(3)分塊查找。因為不考慮在查找的同時對表做修改，故上述三種查找操作都是在靜態(tài)查找表上實現(xiàn)的。查找與數(shù)據(jù)的存儲結構有關，線性表有順序和鏈式兩種存儲結構。本節(jié)只介紹以順序表作為存儲結構時實現(xiàn)的順序查找算法。定義被查找的順序表類型定義如下：#defineMAXL<表中最多記錄個數(shù)>typedefstruct{ KeyTypekey; /*KeyType為關鍵字的數(shù)據(jù)類型*/ InfoTypedata; /*其他數(shù)據(jù)*/}NodeType;typedefNodeTypeSeqList[MAXL];/*順序表類型*/10.2.1順序查找順序查找是一種最簡單的查找方法。根本思路：從表的一端開始，順序掃描線性表，依次將掃描到的關鍵字和給定值k相比較，假設當前掃描到的關鍵字與k相等，那么查找成功；假設掃描結束后，仍未找到關鍵字等于k的記錄，那么查找失敗。例如，在關鍵字序列為{3，9，1，5，8，10，6，7，2，4}的線性表查找關鍵字為6的元素。 順序查找過程如下：開始:39158106724第1次比較:39158106724i=0第2次比較:39158106724i=1第3次比較:39158106724i=2第4次比較:39158106724i=3第5次比較:39158106724i=4第6次比較:39158106724i=5第7次比較:39158106724i=6查找成功，返回序號6順序查找的算法如下(在順序表R[0..n-1]中查找關鍵字為k的記錄，成功時返回找到的記錄位置，失敗時返回-1)：intSeqSearch(SeqListR，intn，KeyTypek){inti=0;while(i<n&&R[i].key!=k)i++;/*從表頭往后找*/if(i>=n)

return-1;else

returni;}從順序查找過程可以看到(不考慮越界比較i<n)，ci取決于所查記錄在表中的位置。如查找表中第1個記錄R[0]時，僅需比較一次；而查找表中最后一個記錄R[n-1]時，需比較n次，即ci=i。因此，成功時的順序查找的平均查找長度為：查找成功時的平均比較次數(shù)約為表長的一半。10.2.2二分查找二分查找也稱為折半查找，要求線性表中的結點必須已按關鍵字值的遞增或遞減順序排列。它首先用要查找的關鍵字k與中間位置的結點的關鍵字相比較，這個中間結點把線性表分成了兩個子表，假設比較結果相等那么查找完成；假設不相等，再根據(jù)k與該中間結點關鍵字的比較大小確定下一步查找哪個子表，這樣遞歸進行下去，直到找到滿足條件的結點或者該線性表中沒有這樣的結點。例如，在關鍵字有序序列{2，4，7，9，10，14，18，26，32，40}中采用二分查找法查找關鍵字為7的元素。 二分查找過程如下：開始:2479101418263240low=0high=9mid=(0+9)/2=4第1次比較:2479101418263240low=0high=3mid=(0+3)/2=1第2次比較:2479101418263240low=2high=3mid=(2+3)/2=2第3次比較:2479101418263240R[2].key=7查找成功，返回序號2其算法如下(在有序表R[0..n-1]中進行二分查找，成功時返回記錄的位置，失敗時返回-1)：intBinSearch(SeqListR，intn，KeyTypek){intlow=0，high=n-1，mid;while(low<=high){mid=(low+high)/2; if(R[mid].key==k)/*查找成功返回*/ returnmid; if(R[mid].key>k)/*繼續(xù)在R[low..mid-1]中查找*/

high=mid-1; else

low=mid+1;/*繼續(xù)在R[mid+1..high]中查找*/}return-1;}二分查找過程可用二叉樹來描述，我們把當前查找區(qū)間的中間位置上的記錄作為根，左子表和右子表中的記錄分別作為根的左子樹和右子樹，由此得到的二叉樹，稱為描述二分查找的判定樹或比較樹。R[0..10]的二分查線的判定樹(n=11)5280369-∞～-112～345～678～9100～11～23～44～56～77～89～1010～∞<>=<>=<>=<>=<>=<>=<>=<>=<>=<>=<>=例10.1對于給定11個數(shù)據(jù)元素的有序表{2，3，10，15，20，25，28，29，30，35，40}，采用二分查找，試問：(1)假設查找給定值為20的元素，將依次與表中哪些元素比較？(2)假設查找給定值為26的元素，將依次與哪些元素比較？(3)假設查找表中每個元素的概率相同，求查找成功時的平均查找長度和查找不成功時的平均查找長度。二分查找判定樹(2)假設查找給定值為26的元素，依次與25，30，28元素比較，共比較3次。(3)在查找成功時，會找到圖中某個圓形結點，那么成功時的平均查找長度：(1)假設查找給定值為20的元素，依次與表中25，10，15，20元素比較，共比較4次。在查找不成功時，會找到圖中某個方形結點，那么不成功時的平均查找長度：分塊查找

分塊查找又稱索引順序查找，它是一種性能介于順序查找和二分查找之間的查找方法。它要求表R是分塊有序的。要求按如下的索引方式來存儲線性表：將表R[0..n-1]均分為b塊，每一塊中的關鍵字不一定有序，但前一塊中的最大關鍵字必須小于后一塊中的最小關鍵字；抽取各塊中的最大關鍵字及其起始位置構成一個索引表IDX[0..b-1]，即IDX[i](0≤i≤b-1)中存放著第i塊的最大關鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個遞增有序表。索引表的數(shù)據(jù)類型定義如下：#defineMAXI<索引表的最大長度>typedefstruct{KeyTypekey;/*KeyType為關鍵字的類型*/intlink; /*指向?qū)獕K的起始下標*/}IdxType;typedefIdxTypeIDX[MAXI]; /*索引表類型*/例如，設有一個線性表，其中包含25個記錄，其關鍵字序列為{8，14，6，9，10，22，34，18，19，31，40，38，54，66，46，71，78，68，80，85，100，94，88，96，87}。假設將25個記錄分為5塊，每塊中有5個記錄，該線性表的索引存儲結構如以下圖所示。

采用二分查找索引表的分塊查找算法如下(索引表I的長度為m)：intIdxSearch(IDXI，intm，SeqListR，intn，KeyTypek){intlow=0，high=m-1，mid，i;intb=n/m; /*b為每塊的記錄個數(shù)*/

while(low<=high) /*在索引中二分查找*/{mid=(low+high)/2; if(I[mid].key>=k)high=mid-1; elselow=mid+1;}if(low<m)/*在塊中順序查找*/{i=I[low].link;while(i<=I[low].link+b-1&&R[i].key!=k)i++; if(i<=I[low].link+b-1)returni; elsereturn-1;}return-1;}假設以二分查找來確定塊，那么分塊查找成功時的平均查找長度為：假設以順序查找確定塊，那么分塊查找成功時的平均查找長度為：10.3樹表的查找當表的插入或刪除操作頻繁時，為維護表的有序性，需要移動表中很多記錄。這種由移動記錄引起的額外時間開銷，就會抵消二分查找的優(yōu)點。二分查找只適用于靜態(tài)查找表。假設要對動態(tài)查找表進行高效率的查找，可采用下頁介紹的幾種特殊的二叉樹或樹作為表的組織形式，在這里將它們統(tǒng)稱為樹表。10.3.1二叉排序樹10.3.2平衡二叉樹10.3.3B-樹10.3.4B+樹10.3.1二叉排序樹二叉排序樹(簡稱BST)又稱二叉查找(搜索)樹，其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：(1)假設它的左子樹非空，那么左子樹上所有記錄的值均小于根記錄的值；(2)假設它的右子樹非空，那么右子樹上所有記錄的值均大于根記錄的值；(3)左、右子樹本身又各是一棵二叉排序樹。503080209010854035252388例如:是二叉排序樹。66不二叉排序樹結點的類型定義如下：typedefstructnode /*記錄類型*/{ KeyTypekey; /*關鍵字項*/ InfoTypedata; /*其他數(shù)據(jù)域*/ structnode*lchild，*rchild; /*左右孩子指針*/}BSTNode;1.二叉排序樹上的查找二叉排序樹可看做是一個有序表，故在二叉排序樹上進行查找，也是一個逐步縮小查找范圍的過程。BSTNode*SearchBST(BSTNode*bt，KeyTypek)//在二叉排序樹bt上查找關鍵字為k的記錄，成功時返回該結點指針，否那么返回NULL{if(bt==NULL||bt->key==k) /*遞歸終結條件*/ returnbt;if(k<bt->key) returnSearchBST(bt->lchild，k);/*在左子樹中遞歸查找*/else returnSearchBST(bt->rchild，k);/*在右子樹中遞歸查找*/}50308020908540358832例如:二叉排序樹查找關鍵字==50,505035,503040355090,50809095,2.二叉排序樹的插入和生成在二叉排序樹中插入一個新記錄，要保證插入后仍滿足BST性質(zhì)。其插入過程是：假設二叉排序樹T為空，那么創(chuàng)立一個key域為k的結點，將它作為根結點；否那么將k和根結點的關鍵字比較，假設二者相等，那么說明樹中已有此關鍵字k，無須插入，直接返回0；假設k<T->key，那么將k插入根結點的左子樹中，否那么將它插入右子樹中。intInsertBST(BSTNode*&p，KeyTypek) /*在以*p為根結點的BST中插入一個關鍵字為k的結點。插入成功返回1，否那么返回0*/{if(p==NULL) /*原樹為空，新插入的記錄為根結點*/{p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;return1;}elseif(k==p->key)/*存在相同關鍵字的結點，返回0*/return0;elseif(k<p->key)returnInsertBST(p->lchild，k);/*插入到左子樹中*/elsereturnInsertBST(p->rchild，k);/*插入到右子樹中*/}二叉排序樹的生成，是從一個空樹開始，每插入一個關鍵字，就調(diào)用一次插入算法將它插入到當前已生成的二叉排序樹中。從關鍵字數(shù)組A[0..n-1]生成二叉排序樹的算法CreatBST()如下：BSTNode*CreatBST(KeyTypeA[]，intn)/*返回樹根指針*/{BSTNode*bt=NULL;/*初始時bt為空樹*/inti=0;while(i<n){InsertBST(bt，A[i]);/*將A[i]插入二叉排序樹T中*/ i++;}returnbt; /*返回建立的二叉排序樹的根指針*/}那么不僅要找到關鍵字為k的結點，還要找到其雙親結點?？稍O計遞歸查找算法如下：BSTNode*SearchBST1(BSTNode*bt,KeyTypek,BSTNode*f1,BSTNode*&f) /*在bt中查找關鍵字為k的結點，假設查找成功，該函數(shù)返回該結點的指針，f返回其雙親結點；否那么，該函數(shù)返回NULL。其調(diào)用方法：SearchBST(bt,x,NULL,f);其中，第3個參數(shù)f1僅作中間參數(shù)，用于求f，初始設為NULL*/查找成功時作刪除；不成功插入注釋：函數(shù)功能說明{ if(bt==NULL) { f=NULL; return(NULL); } elseif(k==bt->key) { f=f1; return(bt); } elseif(k<bt->key) returnSearchBST1(bt->lchild,k,bt,f);/*在左子樹中遞歸查找*/else returnSearchBST1(bt->rchild,k,bt,f);/*在右子樹中遞歸查找*/}顯然，在二叉排序樹上進行查找，假設查找成功，那么是從根記錄出發(fā)走了一條從根到待查記錄的路徑；假設查找不成功，那么是從根記錄出發(fā)走了一條從根到某個葉子的路徑。因此與二分查找類似，和關鍵字比較的次數(shù)不超過樹的深度。然而，二分查找法查找長度為n的有序表，其判定樹是惟一的，而含有n個記錄的二叉排序樹卻不惟一。對于含有同樣一組記錄的表，由于記錄插入的先后次序不同，所構成的二叉排序樹的形態(tài)和深度也可能不同。在二叉排序樹上進行查找時的平均查找長度和二叉排序樹的形態(tài)有關。在最壞情況下，根據(jù)有序表生成的二叉排序樹蛻化為一棵深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同。在最好情況下，二叉排序樹在生成的過程中，樹的形態(tài)比較勻稱，最終得到的是一棵形態(tài)與二分查找的判定樹相似的二叉排序樹，此時它的平均查找長度大約是log2n。根據(jù)關鍵字序列為{5,2,1,6,7,4,8,3,9}和{1,2,3,4,5,6,7,8,9}分別構造二叉排序樹。就平均時間性能而言，二叉排序樹上的查找和二分查找差不多。但就維護表的有序性而言，前者更有效，因為無須移動記錄，只需修改指針即可完成對二叉排序樹的插入和刪除操作，且其平均的執(zhí)行時間均為O(log2n)。例10.2一組關鍵字為{25，18，46，2，53，39，32，4，74，67，60，11}。按表中的元素順序依次插入到一棵初始為空的二叉排序樹中，畫出該二叉排序樹，并求在等概率的情況下查找成功的平均查找長度。解：生成的二叉排序樹如右圖所示。50308020908540358832〔1〕被刪除的結點是葉子結點例如:被刪關鍵字=2088其雙親結點中相應指針域的值改為“空〞3.二叉排序樹的結點刪除刪除操作必須首先進行查找，假設在查找過程結束時，已經(jīng)保存了待刪除結點及其雙親結點的地址。指針變量p指向待刪除的結點，指針變量q指向待刪除結點p的雙親結點。刪除過程如下：(1)假設待刪除的結點是葉子結點，直接刪去該結點。如圖(a)所示，直接刪除結點9。這是最簡單的刪除結點的情況。50308020908540358832〔2〕被刪除的結點只有左子樹或者只有右子樹其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹〞。被刪關鍵字=4080(2)假設待刪除的結點只有左子樹而無右子樹。根據(jù)二叉排序樹的特點，可以直接將其左子樹的根結點放在被刪結點的位置。如圖(b)所示，*p作為*q的右子樹根結點，要刪除*p結點，只需將*p的左子樹(其根結點為3)作為*q結點的右子樹。(3)假設待刪除的結點只有右子樹而無左子樹。與(2)情況類似，可以直接將其右子樹的根結點放在被刪結點的位置。如圖(c)所示，*p作為*q的左子樹根結點，要刪除*p結點，只需將*p的右子樹(其根結點為8)作為*q結點的右子樹。50308020908540358832〔3〕被刪除的結點既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結點被刪結點前驅(qū)結點被刪關鍵字=50(4)假設待刪除的結點同時有左子樹和右子樹。根據(jù)二叉排序樹的特點，可以從其左子樹中選擇關鍵字最大的結點或從其右子樹中選擇關鍵字最小的結點放在被刪去結點的位置上。假設選取左子樹上關鍵字最大的結點，那么該結點一定是左子樹的最右下結點。如圖(d)所示，假設要刪除*p(其關鍵字為5)結點，找到其左子樹最右下結點4，它的雙親結點為2，用它代替*p結點，并將其原來的左子樹(其根結點為3)作為原來的雙親結點2的右子樹。

刪除二叉排序樹結點的算法DeleteBST()如下(指針變量p指向待刪除的結點，指針變量q指向待刪除結點*p的雙親結點)：voidDelete1(BSTNode*p，BSTNode*&r)/*當被刪*p結點有左右子樹時的刪除過程*/{ BSTNode*q; if(r->rchild!=NULL)

Delete1(p，r->rchild); /*遞歸找最右下結點*/ else /*找到了最右下結點*r*/ {p->key=r->key;/*將*r的關鍵字值賦給*p*/ q=r;r=r->lchild;

/*用*r的左子樹的根結點取代*r的位置*/ free(q);/*釋放原*r的空間*/ }}voidDelete(BSTNode*&p)/*從二叉排序樹中刪除*p結點*/{BSTNode*q;if(p->rchild==NULL)/**p結點沒有右子樹的情況*/{q=p;p=p->lchild; /*其左子樹的根結點放在被刪結點的位置上*/free(q);}elseif(p->lchild==NULL)/**p結點沒有左子樹*/{q=p;p=p->rchild; /*將*p結點的右子樹作為雙親結點的相應子樹/free(q);}elseDelete1(p，p->lchild); /**p結點既有左子樹又有右子樹的情況*/}intDeleteBST(BSTNode*&bt，KeyTypek) /*在bt中刪除關鍵字為k的結點*/{if(bt==NULL)return0; /*空樹刪除失敗*/else{if(k<bt->key)returnDeleteBST(bt->lchild，k); /*遞歸在左子樹中刪除為k的結點*/ elseif(k>bt->key)returnDeleteBST(bt->rchild，k); /*遞歸在右子樹中刪除為k的結點*/ else {Delete(bt);/*調(diào)用Delete(bt)函數(shù)刪除*bt結點*/ return1; }}}p右子樹為空樹，那么只需重接它的左子樹。q=p;p=p->lchild;free(q);pqq左子樹為空樹，只需重接它的右子樹q=p;p=p->rchild;free(q);ppqqq=p;r=p->lchild;while(!r->rchild){q=r;r=r->rchild;}//r指向被刪結點的前驅(qū)左右子樹均不空p->data=r->data;if(q!=p)q->rchild=r->lchild;elseq->lchild=r->lchild;//重接*q的左子樹free(r);被刪結點前驅(qū)結點pqr…10.3.2平衡二叉樹假設一棵二叉樹中每個結點的左、右子樹的高度至多相差1，那么稱此二叉樹為平衡二叉樹。在算法中，通過平衡因子(balancdfactor，用bf表示)來具體實現(xiàn)上述平衡二叉樹的定義。平衡因子的定義是：平衡二叉樹中每個結點有一個平衡因子域，每個結點的平衡因子是該結點左子樹的高度減去右子樹的高度。從平衡因子的角度可以說，假設一棵二叉樹中所有結點的平衡因子的絕對值小于或等于1，即平衡因子取值為1、0或-1，那么該二叉樹稱為平衡二叉樹。548254821是平衡樹不是平衡樹平衡二叉樹和不平衡二叉樹定義AVL樹的結點的類型如下：typedefstructnode /*記錄類型*/{ KeyTypekey; /*關鍵字項*/ intbf; /*增加的平衡因子*/ InfoTypedata; /*其他數(shù)據(jù)域*/ structnode*lchild，*rchild;/*左右孩子指針*/}BSTNode;假定向平衡二叉樹中插入一個新結點后破壞了平衡二叉樹的平衡性，首先要找出插入新結點后失去平衡的最小子樹根結點的指針，然后再調(diào)整這個子樹中有關結點之間的鏈接關系，使之成為新的平衡子樹。當失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹。失去平衡的最小子樹是指以離插入結點最近，且平衡因子絕對值大于1的結點作為根的子樹。假設用A表示失去平衡的最小子樹的根結點，那么調(diào)整該子樹的操作可歸納為以下四種情況：構造二叉平衡〔查找〕樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術。例如：依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)426589426895向左旋轉(zhuǎn)一次繼續(xù)插入關鍵字9

(1)LL型調(diào)整h+1hh2h10

(2)RR型調(diào)整h+1hh-2h-10

(3)LR型調(diào)整h+1h+1h2h1h+1-1000-1

(4)RL型調(diào)整h+1h+1-2h1h+10000-116插入16,3,7377調(diào)整以16為根的不平衡子樹316

例10.3輸入關鍵字序列{16，3，7，11，9，26，18，14，15}，給出構造一棵AVL樹的步驟。7316119插入11,97311916調(diào)整以16為根的不平衡子樹7311916調(diào)整以7為根的不平衡子樹26931171626插入26在平衡的二叉排序樹b中插入一個關鍵字為e的結點的過程是：假設在b中不存在和e有相同關鍵字的結點，那么插入一個數(shù)據(jù)元素為e的新結點，并返回1，否那么返回0。假設因插入而使二叉排序樹失去平衡，需作平衡旋轉(zhuǎn)處理，變量taller表示b是否長高。對應的插入算法為InsertAVL()。intInsertAVL(BSTNode*&b,KeyTypee,int&taller)/*調(diào)用方式(定義:BSTNode*b;KeyTypex;intk)；InsertAVL(b,x,k);其中，整型變量k作為一個引用型參數(shù)*/{if(b==NULL) /*原為空樹,插入新結點，樹“長高〞,置taller為1*/ { b=(BSTNode*)malloc(sizeof(BSTNode)); b->key=e; b->lchild=b->rchild=NULL; b->bf=0; taller=1; }else{if(e==b->key)/*樹中已存在和e有相同關鍵字的結點那么不再插入*/ { taller=0; return0;}if(e<b->key) /*應繼續(xù)在*b的左子樹中搜索,即在左子樹中插入*/ {if((InsertAVL(b->lchild,e,taller))==0)/*未插入*/ return0; if(taller==1)/*已插入到*b的左子樹中且左子樹“長高〞*/ LeftProcess(b,taller); }從下層子樹返回到上層子樹時判斷并進行子樹調(diào)整else/*應繼續(xù)在*b的右子樹中搜索，即在右子樹中插入*/{ if((InsertAVL(b->rchild,e,taller))==0)/*未插入*/ return0; if(taller==1)/*已插入到b的右子樹且右子樹“長高〞*/ RightProcess(b,taller);}} return1;}voidLeftProcess(BSTNode*&p,int&taller)/*對以指針p所指結點為根的二叉樹作左平衡旋轉(zhuǎn)處理,本算法結束時，指針p指向新的根結點*/{ BSTNode*p1,*p2; if(p->bf==0) /*對應情況(1)*/ { p->bf=1; taller=1; /*子樹增高*/ }

elseif(p->bf==-1) /*對應情況(2)*/ { p->bf=0; taller=0; /*子樹沒有增高*/ }

hhph+10hhph+21h-1hph+1-1hhph+10else /*p->bf=1，對應情況(3)*/{ p1=p->lchild; /*p指向*p的左子樹根結點 if(p1->bf==1) /*對應情況1)，要作LL調(diào)整*/ { p->lchild=p1->rchild;

p1->rchild=p;

p->bf=p1->bf=0; p=p1; } elseif(p1->bf==-1)/*對應情況2),要作LR*/ { p2=p1->rchild;

p1->rchild=p2->lchild;

p2->lchild=p1;

p->lchild=p2->rchild;

p2->rchild=p;h+1hph+21h+2hph+32h+1hhhh+1h+1hhh+1if(p2->bf==0) /*對應情況①*/p->bf=p1->bf=0; elseif(p2->bf==1) /*對應情況②*/{ p1->bf=0;p->bf=-1;}else /*p2->bf=-1，對應情況③*/{ p1->bf=1;p->bf=0;}p=p2;p->bf=0;/*仍將p指向新的根結點，并置其bf值為0*/}taller=0; /*子樹沒有增高*/}}對應的插入右處理算法RightProcess()與LeftProcess()相似，只需將其中的所有l(wèi)child改為rchild，rchild改為lchild，1改為-1，-1改為1即可。在平衡二叉樹上進行查找的過程和在二叉排序樹上進行查找的過程完全相同，因此，在平衡二叉樹上進行查找關鍵字的比較次數(shù)不會超過平衡二叉樹的深度。在最壞的情況下，普通二叉排序樹的查找長度為O(n)。那么，平衡二叉樹的情況又是怎樣的呢？下面分析平衡二叉樹的高度h和結點個數(shù)n之間的關系。首先，構造一系列的平衡二叉樹T1，T2，T3，…，其中，Th〔h=1，2，3，…〕是高度為h且結點數(shù)盡可能少的平衡二叉樹，如下頁圖中所示的T1，T2，T3和T4。為了構造Th，先分別構造Th-1和Th-2，使Th以Th-1和Th-2作為左、右子樹。對于每一個Th，只要從中刪去一個結點，就會失去平衡或高度不再是h〔顯然，這樣構造的平衡二叉樹在結點個數(shù)相同的平衡二叉樹中具有最大高度〕。n=0空樹最大深度為0n=1最大深度為1n=2最大深度為2n=4最大深度為3n=7最大深度為4反過來：深度為h的二叉平衡樹中所含結點的最小值Nh

是多少？h=0N0=0h=1h=2h=3N1=1N2=2N3=4通過計算上述平衡二叉樹中的結點個數(shù)，來建立高度與結點個數(shù)之間的關系。設N(h)為Th的結點數(shù)，從圖中可以看出有以下關系成立：N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)當h>1時，此關系類似于定義Fibonacci數(shù)的關系：F(1)=1，F(xiàn)(2)=1，F(xiàn)(h)=F(h-1)+F(h-2)通過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的對應關系：N(h)=F(h+2)-1由于Fibonacci數(shù)滿足漸近公式：F(h)=其中，故由此可得近似公式：N(h)=即：h≈log2(N(h)+1)所以，含有n個結點的平衡二叉樹的平均查找長度為O(log2n)。10.3.3B-樹B-樹又稱為多路平衡查找樹，是一種組織和維護外存文件系統(tǒng)非常有效的數(shù)據(jù)結構。B-樹中所有結點的孩子結點最大值稱為B-樹的階，通常用m表示，從查找效率考慮，要求m≥3。一棵m階B-樹或者是一棵空樹，或者是滿足以下要求的m叉樹：(1)樹中每個結點至多有m個孩子結點(即至多有m-1個關鍵字)；(2)除根結點外，其他結點至少有m/2個孩子結點(即至少有m/2-1=(m-1)/2個關鍵字)；(3)假設根結點不是葉子結點，那么根結點至少有兩個孩子結點；(4)每個結點的結構為：np0k1p1k2p2…knpn

其中，n為該結點中的關鍵字個數(shù)，除根結點外，其他所有結點的n大于等于m/2-1，且小于等于m-1；ki(1≤i≤n)為該結點的關鍵字且滿足ki＜ki+1；pi(0≤i≤n)為該結點的孩子結點指針且滿足pi(0≤i≤n-1)結點上的關鍵字大于等于ki且小于ki+1，pn結點上的關鍵字大于kn。(5)所有葉子結點都在同一層上，即B-樹是所有結點的平衡因子均等于0的多路查找樹。一棵5階B-樹在B-樹的存儲結構中，各結點的類型定義如下：#defineMAXM10 /*定義B-樹的最大的階數(shù)*/typedefintKeyType; /*KeyType為關鍵字類型*/typedefstructnode /*B-樹結點類型定義*/{intkeynum; /*結點當前擁有的關鍵字的個數(shù)*/KeyTypekey[MAXM];/*[1..keynum]存放關鍵字，[0]不用*/structnode*parent; /*雙親結點指針*/structnode*ptr[MAXM];/*孩子結點指針數(shù)組[0..keynum]*/}BTNode;B-樹的查找在B-樹中查找給定關鍵字的方法類似于二叉排序樹上的查找，不同的是在每個記錄上確定向下查找的路徑不一定是二路(即二叉)的，而是n+1路的。因為記錄內(nèi)的關鍵字序列是有序的數(shù)量key[1..n]，故既可以用順序查找，也可以用折半查找。在一棵B-樹上順序查找關鍵字為k的方法為：將k與根結點中的key[i]進行比較：(1)假設k=key[i]，那么查找成功；(2)假設k＜key[1]，那么沿著指針ptr[0]所指的子樹繼續(xù)查找；(3)假設key[i]＜k＜key[i+1]，那么沿著指針ptr[i]所指的子樹繼續(xù)查找；(4)假設k＞key[n]，那么沿著指針ptr[n]所指的子樹繼續(xù)查找。2.B-樹的插入將關鍵字k插入到B-樹的過程分兩步完成：(1)利用前述的B-樹的查找算法找出該關鍵字的插入結點(注意B-樹的插入結點一定是葉子結點)。(2)判斷該結點是否還有空位置，即判斷該結點是否滿足n＜m-1:假設滿足n＜m-1，說明該結點還有空位置，直接把關鍵字k插入到該結點的適宜位置上(即滿足插入后結點上的關鍵字仍保持有序)；假設該結點有n=m-1，說明該結點已沒有空位置，需要把結點分裂成兩個。分裂的做法：取一新結點，把原結點上的關鍵字和k按升序排序后，從中間位置(即m/2=(m+1)/2之處)把關鍵字(不包括中間位置的關鍵字)分成兩局部，左局部所含關鍵字放在舊結點中，右局部所含關鍵字放在新結點中，中間位置的關鍵字連同新結點的存儲位置插入到父親結點中。如果父結點的關鍵字個數(shù)也超過Max，那么要再分裂，再往上插，直至這個過程傳到根結點為止。1267根據(jù)關鍵字序列：{1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15}創(chuàng)立一棵5階B-樹。插入116126711插入4124插入8,13781113插入10781113111378610插入51245插入1711131761016789插入9插入161113161711131720插入33610161245插入12,14,18,191112131417181920插入15141511121313163610插入20163103.B-樹的刪除B-樹的刪除過程與插入過程類似，只是稍為復雜一些。要使刪除后的結點中的關鍵字個數(shù)≥m/2-1，將涉及到結點的“合并〞問題。在B-樹上刪除關鍵字k的過程分兩步完成：(1)利用前述的B-樹的查找算法找出該關鍵字所在的結點。(2)在結點上刪除關鍵字k分兩種情況：一種是在葉子結點上刪除關鍵字；另一種是在非葉子結點上刪除關鍵字。(3)在非葉子結點上刪除關鍵字的過程：假設要刪除關鍵字key[i](1≤i≤n)，在刪去該關鍵字后，以該結點ptr[i]所指子樹中的最小關鍵字key[min]來代替被刪關鍵字key[i]所在的位置(注意ptr[i]所指子樹中的最小關鍵字key[min]一定是在葉子結點上)，然后再以指針ptr[i]所指結點為根結點查找并刪除key[min](即再以ptr[i]所指結點為B-樹的根結點，以key[min]為要刪除的關鍵字，然后再次調(diào)用B-樹上的刪除算法)，這樣也就把在非葉子結點上刪除關鍵字k的問題轉(zhuǎn)化成了在葉子結點上刪除關鍵字key[min]的問題。(4)在B-樹的葉子結點上刪除關鍵字共有以下三種情況：①假設被刪結點的關鍵字個數(shù)大于Min，說明刪去該關鍵字后該結點仍滿足B-樹的定義，那么可直接刪去該關鍵字。②假設被刪結點的關鍵字個數(shù)等于Min，說明刪去關鍵字后該結點將不滿足B-樹的定義，此時假設該結點的左(或右)兄弟結點中關鍵字個數(shù)大于Min，那么把該結點的左(或右)兄弟結點中最大(或最小)的關鍵字上移到雙親結點中，同時把雙親結點中大于(或小于)上移關鍵字的關鍵字下移到要刪除關鍵字的結點中，這樣刪去關鍵字k后該結點以及它的左(或右)兄弟結點都仍舊滿足B-樹的定義。③假設被刪結點的關鍵字個數(shù)等于Min，并且該結點的左和右兄弟結點(如果存在的話)中關鍵字個數(shù)均等于Min，這時，需把要刪除關鍵字的結點與其左(或右)兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點。如果因此使雙親結點中關鍵字個數(shù)小于Min，那么對此雙親結點做同樣處理，以致于可能直到對根結點做這樣的處理而使整個樹減少一層。(a)初始5階B-樹101415131636127891718192045111279刪8刪16，找下層替代者至葉子17131317181920刪15，借富有兄弟的14171814171920刪4，借不著，合并51235661013181318對于前例生成的B-樹，給出刪除8，16，15，4等四個關鍵字的過程。B+樹在索引文件組織中，經(jīng)常使用B-樹的一些變形，其中B+樹是一種應用廣泛的變形。一棵m階B+樹滿足以下條件：(1)每個分支結點至多有m棵子樹。(2)除根結點外，其他每個分支結點至少有(m+1)/2棵子樹。(3)根結點至少有兩棵子樹，至多有m棵子樹。(4)有n棵子樹的結點有n個關鍵字。(5)所有葉子結點包含全部(數(shù)據(jù)文件中記錄)關鍵字及指向相應記錄的指針(或存放數(shù)據(jù)文件分塊后每塊的最大關鍵字及指向該塊的指針)，而且葉子結點按關鍵字大小順序鏈接(可以把每個葉子結點看成是一個根本索引塊，它的指針不再指向另一級索引塊，而是直接指向數(shù)據(jù)文件中的記錄)。(6)所有分支結點(可看成是索引的索引)中僅包含它的各個子結點(即下級索引的索引塊)中最大關鍵字及指向子結點的指針。一棵4階的B+樹

m階的B+樹和m階的B-樹，定義中的前三點是相同的，主要的差異是：

(1)在B+樹中，具有n個關鍵字的結點含有n棵子樹，即每個關鍵字對應一棵子樹，而在B-樹中，具有n個關鍵字的結點含有(n+1)棵子樹。(2)在B+樹中，每個結點(除根結點外)中的關鍵字個數(shù)n的取值范圍是m/2≤n≤m，根結點n的取值范圍是1≤n≤m；而在B-樹中，它們的取值范圍分別是m/2-1≤n≤m-1和1≤n≤m-1。(3)B+樹中的所有葉子結點包含了全部關鍵字，即其他非葉子結點中的關鍵字包含在葉子結點中，而在B-樹中，葉子結點包含的關鍵字與其他結點包含的關鍵字是不重復的。(4)B+樹中所有非葉子結點僅起到索引的作用，即結點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲地址。而在B-樹中，每個關鍵字對應一個記錄的存儲地址。(5)通常在B+樹上有兩個頭指針，一個指向根結點，另一個指向關鍵字最小的葉子結點，所有葉子結點鏈接成一個不定長的線性鏈表。1.B+樹查找在B+樹中可以采用兩種查找方式，一種是直接從最小關鍵字開始進行順序查找，另一種就是從B+樹的根結點開始進行隨機查找。這種查找方式與B-樹的查找方法相似，只是在分支結點上的關鍵字與查找值相等時，查找并不結束，要繼續(xù)查到葉子結點為止，此時假設查找成功，那么按所給指針取出對應記錄即可。因此，在B+樹中，不管查找成功與否，每次查找都是經(jīng)過了一條從樹根結點到葉子結點的路徑。2.B+樹插入與B-樹的插入操作相似，B+樹的插入也從葉子結點開始，當插入后結點中的關鍵字個數(shù)大于m時要分裂成兩個結點，它們所含鍵值個數(shù)分別為(m+1)/2和(m+1)/2，同時要使得它們的雙親結點中包含有這兩個結點的最大關鍵字和指向它們的指針。假設雙親結點的關鍵字個數(shù)而大于m，應繼續(xù)分裂，依此類推。3.B+樹刪除B+樹的刪除也是從葉子結點開始，當葉子結點中最大關鍵字被刪除時，分支結點中的值可以作為“分界關鍵字〞存在。假設因刪除操作而使結點中關鍵字個數(shù)少于m/2時，那么從兄弟結點中調(diào)劑關鍵字或和兄弟結點合并，其過程和B-樹相似。10.4哈希表查找哈希表的根本概念哈希表(HashTable)又稱散列表，是除順序表存儲結構、鏈接表存儲結構和索引表存儲結構之外的又一種存儲線性表的存儲結構。哈希表存儲的根本思路是：設要存儲的對象個數(shù)為n，設置一個長度為m(m≥n)的連續(xù)內(nèi)存單元，以線性表中每個對象的關鍵字ki(0≤i≤n-1)為自變量，通過一個稱為哈希函數(shù)的函數(shù)h(ki)，把ki映射為內(nèi)存單元的地址(或稱下標)h(ki)，并把該對象存儲在這個內(nèi)存單元中。h(ki)也稱為哈希地址(又稱散列地址)。把如此構造的線性表存儲結構稱為哈希表。但是存在這樣的問題，對于兩個關鍵字ki和kj(i≠j)，有ki≠kj(i≠j)，但h(ki)=h(kj)。我們把這種現(xiàn)象叫做哈希沖突。通常把這種具有不同關鍵字而具有相同哈希地址的對象稱做“同義詞〞，由同義詞引起的沖突稱作同義詞沖突。在哈希表存儲結構的存儲中，同義詞沖突是很難防止的，除非關鍵字的變化區(qū)間小于等于哈希地址的變化區(qū)間，而這種情況當關鍵字取值不連續(xù)時是非常浪費存儲空間的。通常的實際情況是關鍵字的取值區(qū)間遠大于哈希地址的變化區(qū)間。歸納起來：(1)哈希函數(shù)是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可；(2)由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突〞現(xiàn)象，即：key1key2，而f(key1)=f(key2)。(3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。10.4