數(shù)據(jù)結(jié)構(gòu)第9章查找

第9章查找9.1查找的基本概念本章小結(jié)9.2線性表的查找9.3樹表的查找9.4哈希表查找19.1查找的基本概念

被查找的對象是由一組記錄組成的表或文件,而每個(gè)記錄則由若干個(gè)數(shù)據(jù)項(xiàng)組成,并假設(shè)每個(gè)記錄都有一個(gè)能惟一標(biāo)識該記錄的關(guān)鍵字。在這種條件下,查找的定義是：給定一個(gè)值k,在含有n個(gè)記錄的表中找出關(guān)鍵字等于k的記錄。若找到,則查找成功,返回該記錄的信息或該記錄在表中的位置；否則查找失敗,返回相關(guān)的指示信息。

2

采用何種查找方法?

(1)使用哪種數(shù)據(jù)結(jié)構(gòu)來表示“表”,即表中記錄是按何種方式組織的。

(2)表中關(guān)鍵字的次序。是對無序集合查找還是對有序集合查找?

若在查找的同時(shí)對表做修改運(yùn)算(如插入和刪除),則相應(yīng)的表稱之為動(dòng)態(tài)查找表,否則稱之為靜態(tài)查找表。

3

由于查找運(yùn)算的主要運(yùn)算是關(guān)鍵字的比較,所以通常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(也稱為平均查找長度)作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。平均查找長度ASL(AverageSearchLength)定義為：

其中,n是查找表中記錄的個(gè)數(shù)。pi是查找第i個(gè)記錄的概率,一般地,均認(rèn)為每個(gè)記錄的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i個(gè)記錄所需進(jìn)行的比較次數(shù)。

49.2線性表的查找

在表的組織方式中,線性表是最簡單的一種。三種在線性表上進(jìn)行查找的方法：

(1)順序查找

(2)二分查找

(3)分塊查找。因?yàn)椴豢紤]在查找的同時(shí)對表做修改,故上述三種查找操作都是在靜態(tài)查找表上實(shí)現(xiàn)的。5

查找與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān),線性表有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)。本節(jié)只介紹以順序表作為存儲結(jié)構(gòu)時(shí)實(shí)現(xiàn)的順序查找算法。定義被查找的順序表類型定義如下：

#defineMAXL<表中最多記錄個(gè)數(shù)>typedefstruct{ KeyTypekey; /*KeyType為關(guān)鍵字的數(shù)據(jù)類型*/ InfoTypedata; /*其他數(shù)據(jù)*/}NodeType;

typedefNodeTypeSeqList[MAXL];/*順序表類型*/69.2.1順序查找

順序查找是一種最簡單的查找方法。它的基本思路是：從表的一端開始,順序掃描線性表,依次將掃描到的關(guān)鍵字和給定值k相比較,若當(dāng)前掃描到的關(guān)鍵字與k相等,則查找成功；若掃描結(jié)束后,仍未找到關(guān)鍵字等于k的記錄,則查找失敗。7

例如,在關(guān)鍵字序列為{3,9,1,5,8,10,16,7,2,4}的線性表查找關(guān)鍵字為k=16的元素。 順序查找過程如下：8

開始:391581016724

第1次比較:

3

91581016724

i=0

第2次比較:3

9

1581016724

i=1

第3次比較:39

1

581016724

i=2

第4次比較:391

5

81016724

i=3

第5次比較:3915

8

1016724

i=4

第6次比較:39158

1016724

i=5

第7次比較:391581016724

i=6

查找成功,返回序號69

順序查找的算法如下(在順序表R[0..n-1]中查找關(guān)鍵字為k的記錄,成功時(shí)返回找到的記錄位置,失敗時(shí)返回-1)：

intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(i<n&&R[i].key!=k)i++;/*從表頭往后找*/if(i>=n)return-1;elsereturni;}10

從順序查找過程可以看到(不考慮越界比較i<n),ci取決于所查記錄在表中的位置。如查找表中第1個(gè)記錄R[0]時(shí),僅需比較一次；而查找表中最后一個(gè)記錄R[n-1]時(shí),需比較n次,即ci=i。因此,成功時(shí)的順序查找的平均查找長度為：

查找成功時(shí)的平均比較次數(shù)約為表長的一半。119.2.2二分查找

二分查找也稱為折半查找要求線性表中的結(jié)點(diǎn)必須己按關(guān)鍵字值的遞增或遞減順序排列。它首先用要查找的關(guān)鍵字k與中間位置的結(jié)點(diǎn)的關(guān)鍵字相比較,這個(gè)中間結(jié)點(diǎn)把線性表分成了兩個(gè)子表,若比較結(jié)果相等則查找完成;若不相等,再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較大小確定下一步查找哪個(gè)子表,這樣遞歸進(jìn)行下去,直到找到滿足條件的結(jié)點(diǎn)或者該線性表中沒有這樣的結(jié)點(diǎn)。12

例如,在關(guān)鍵字有序序列{2,4,7,9,10,14,18,26,32,40}中采用二分查找法查找關(guān)鍵字為7的元素。 二分查找過程如下：13

第1次比較:

2

4791014182632

40

low=0mid=(0+9)/2=4

high=9

第2次比較:2

47

9

101418263240

low=0

high=3

mid=(0+3)/2=1

第3次比較:24

7

9

101418263240

low=2

high=3

mid=(2+3)/2=22479101418263240R[2].key=7

查找成功,返回序號214

其算法如下(在有序表R[0..n-1]中進(jìn)行二分查找,成功時(shí)返回記錄的位置,失敗時(shí)返回-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;}15

補(bǔ)充：遞歸算法：(在有序表R[low..high]中進(jìn)行二分查找,成功時(shí)返回記錄的位置,失敗時(shí)返回-1)：

intBinSearch(SeqListR,intlow,inthigh,KeyTypek)

{intmid;if(low<=high){mid=(low+high)/2; if(R[mid].key==k)/*查找成功返回*/ returnmid; if(R[mid].key>k)/*繼續(xù)在R[low..mid-1]中查找*/ returnBinSearch(R,low,mid-1,k); else returnBinSearch(R,mid+1,high,k);/*繼續(xù)在R[mid+1..high]中查找*/}return-1;}16

二分查找過程可用二叉樹來描述,我們把當(dāng)前查找區(qū)間的中間位置上的記錄作為根,左子表和右子表中的記錄分別作為根的左子樹和右子樹,由此得到的二叉樹,稱為描述二分查找的判定樹或比較樹。17R[0..10]的二分查線的判定樹(n=11)

18

例9.1

給定11個(gè)數(shù)據(jù)元素的有序表{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,試問：

(1)若查找給定值為20的元素,將依次與表中哪些元素比較？

(2)若查找給定值為26的元素,將依次與哪些元素比較？

(3)假設(shè)查找表中每個(gè)元素的概率相同,求查找成功時(shí)的平均查找長度和查找不成功時(shí)的平均查找長度。19二分查找判定樹

(2)若查找給定值為26的元素,依次與25,30,28元素比較,共比較3次。

(3)在查找成功時(shí),會(huì)找到圖中某個(gè)圓形結(jié)點(diǎn),則成功時(shí)的平均查找長度：(1)若查找給定值為20的元素,依次與表中25,10,15,20元素比較,共比較4次。

在查找不成功時(shí),會(huì)找到圖中某個(gè)方形結(jié)點(diǎn),則不成功時(shí)的平均查找長度：20219.2.3索引存儲結(jié)構(gòu)和分塊查找

分塊查找又稱索引順序查找,它是一種性能介于順序查找和二分查找之間的查找方法。它要求按如下的索引方式來存儲線性表：將表R[0..n-1]均分為b塊,前b-1塊中記錄個(gè)數(shù)為s=n/b,最后一塊即第b塊的記錄數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序,但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字,即要求表是“分塊有序”的；抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè)索引表IDX[0..b-1],即IDX[i](0≤i≤b-1)中存放著第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的,所以索引表是一個(gè)遞增有序表。22在建立順序表的同時(shí)，建立一個(gè)索引。012345678910111213……1708211914313322254052617846……2104057810……例如：索引順序表=索引+順序表順序表(塊內(nèi)無序，塊間有序)索引索引順序表的查找過程：1）由索引確定待查記錄所在分塊（有序表）；2）在順序表的某個(gè)分塊內(nèi)進(jìn)行順序查找。23索引表的數(shù)據(jù)類型定義如下：#defineMAXI<索引表的最大長度>typedefstruct{KeyTypekey; /*KeyType為關(guān)鍵字的類型*/intlink; /*指向?qū)?yīng)塊的起始下標(biāo)*/}IdxType;typedefIdxTypeIDX[MAXI]; /*索引表類型*/24

例如,設(shè)有一個(gè)線性表,其中包含25個(gè)記錄,其關(guān)鍵字序列為{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}。假設(shè)將25個(gè)記錄分為5塊,每塊中有5個(gè)記錄,該線性表的索引存儲結(jié)構(gòu)如下圖所示。

25

采用二分查找索引表的分塊查找算法如下(索引表I的長度為m)：intIdxSearch(IDXI,intm,SeqListR,intn,KeyTypek){intlow=0,high=m-1,mid,i;intb=n/m; /*b為每塊的記錄個(gè)數(shù)*/while(low<=high) /*在索引中二分查找*/{mid=(low+high)/2; if(I[mid].key>=k)high=mid-1; elselow=mid+1;}26if(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;}27

若以二分查找來確定塊,則分塊查找成功時(shí)的平均查找長度為：

若以順序查找確定塊,則分塊查找成功時(shí)的平均查找長度為：

289.3樹表的查找當(dāng)表的插入或刪除操作頻繁時(shí),為維護(hù)表的有序性,需要移動(dòng)表中很多記錄。這種由移動(dòng)記錄引起的額外時(shí)間開銷,就會(huì)抵消二分查找的優(yōu)點(diǎn)。也就是說,二分查找只適用于靜態(tài)查找表。若要對動(dòng)態(tài)查找表進(jìn)行高效率的查找,可采用下面介紹的幾種特殊的二叉樹或樹作為表的組織形式,在這里將它們統(tǒng)稱為樹表。下面將分別討論在這些樹表上進(jìn)行查找和修改操作的方法。299.3.1二叉排序樹

二叉排序樹(簡稱BST)又稱二叉查找(搜索)樹,其定義為：二叉排序樹或者是空樹,或者是滿足如下性質(zhì)的二叉樹：

(1)若它的左子樹非空,則左子樹上所有記錄的值均小于根記錄的值；

(2)若它的右子樹非空,則右子樹上所有記錄的值均大于根記錄的值；

(3)左、右子樹本身又各是一棵二叉排序樹。30503080209010854035252388例如:是二叉排序樹。66不中序遍歷二叉排序樹可得有序序列：10,20,23,25,30,35,40,50,80,85,88,9031

在討論二叉排序樹上的運(yùn)算之前,定義其結(jié)點(diǎn)的類型如下：

typedefstructnode /*記錄類型*/{ KeyTypekey; /*關(guān)鍵字項(xiàng)*/ InfoTypedata; /*其他數(shù)據(jù)域*/ structnode*lchild,*rchild; /*左右孩子指針*/}BSTNode;321.二叉排序樹的插入和生成

在二叉排序樹中插入一個(gè)新記錄,要保證插入后仍滿足BST性質(zhì)。其插入過程是：若二叉排序樹T為空,則創(chuàng)建一個(gè)key域?yàn)閗的結(jié)點(diǎn),將它作為根結(jié)點(diǎn)；否則將k和根結(jié)點(diǎn)的關(guān)鍵字比較,若二者相等,則說明樹中已有此關(guān)鍵字k,無須插入,直接返回0；若k<T->key,則將k插入根結(jié)點(diǎn)的左子樹中,否則將它插入右子樹中。對應(yīng)的遞歸算法InsertBST()如下：33intInsertBST(BSTNode*&p,KeyTypek) /*在以*p為根結(jié)點(diǎn)的BST中插入一個(gè)關(guān)鍵字為k的結(jié)點(diǎn)。插入成功返回1,否則返回0*/{if(p==NULL) /*原樹為空,新插入的記錄為根結(jié)點(diǎn)*/{p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;return1;}elseif(k==p->key)/*存在相同關(guān)鍵字的結(jié)點(diǎn),返回0*/return0;elseif(k<p->key)returnInsertBST(p->lchild,k);/*插入到左子樹中*/elsereturnInsertBST(p->rchild,k);/*插入到右子樹中*/}34

二叉排序樹的生成,是從一個(gè)空樹開始,每插入一個(gè)關(guān)鍵字,就調(diào)用一次插入算法將它插入到當(dāng)前已生成的二叉排序樹中。從關(guān)鍵字?jǐn)?shù)組A[0..n-1]生成二叉排序樹的算法CreatBST()如下：

BSTNode*CreatBST(KeyTypeA[],intn)/*返回樹根指針*/{BSTNode*bt=NULL;/*初始時(shí)bt為空樹*/inti=0;while(i<n){InsertBST(bt,A[i]);/*將A[i]插入二叉排序樹T中*/ i++;}returnbt; /*返回建立的二叉排序樹的根指針*/}35

2.二叉排序樹上的查找

因?yàn)槎媾判驑淇煽醋鍪且粋€(gè)有序表,所以在二叉排序樹上進(jìn)行查找,和二分查找類似,也是一個(gè)逐步縮小查找范圍的過程。遞歸查找算法SearchBST()如下(在二叉排序樹bt上查找關(guān)鍵字為k的記錄,成功時(shí)返回該結(jié)點(diǎn)指針,否則返回NULL)：

BSTNode*SearchBST(BSTNode*bt,KeyTypek)

{if(bt==NULL||bt->key==k) /*遞歸終結(jié)條件*/ returnbt;if(k<bt->key) returnSearchBST(bt->lchild,k);/*在左子樹中遞歸查找*/else returnSearchBST(bt->rchild,k);/*在右子樹中遞歸查找*/}3650308020908540358832例如:查找關(guān)鍵字==50,505035,503040355090,50809095,在已建好的二叉排序樹上進(jìn)行查找37

例9.3

已知一組關(guān)鍵字為{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素順序依次插入到一棵初始為空的二叉排序樹中,畫出該二叉排序樹,并求在等概率的情況下查找成功的平均查找長度。解：生成的二叉排序樹如右圖所示。38

例9.4

設(shè)計(jì)一個(gè)算法，對于給定的二叉排序樹中的結(jié)點(diǎn)*p，找出其左子樹中的最大結(jié)點(diǎn)和右子樹的最小結(jié)點(diǎn)。解：最大結(jié)點(diǎn)為根結(jié)點(diǎn)的最右下結(jié)點(diǎn)，最小結(jié)點(diǎn)是根結(jié)點(diǎn)的最左下結(jié)點(diǎn)。KeyTypemaxnode(BSTNode*p){while(p->rchild!=NULL)p=p->rchild;returnp->data;}39KeyTypeminnode(BSTNode*p){while(p->lchild!=NULL)p=p->lchild;returnp->data;}voidmaxminnode(BSTNode*p){if(p!=NULL){if(p->lchild!=NULL)cout<<“左子樹的最大結(jié)點(diǎn)為：”<<maxnode(p->lchild);if(p->rchild!=NULL)cout<<“右子樹的最小結(jié)點(diǎn)為：”<<minnode(p->rchild);}}403.二叉排序樹的刪除

刪除操作必須首先進(jìn)行查找,假設(shè)在查找過程結(jié)束時(shí),已經(jīng)保存了待刪除結(jié)點(diǎn)及其雙親結(jié)點(diǎn)的地址。指針變量p指向待刪除的結(jié)點(diǎn),指針變量q指向待刪除結(jié)點(diǎn)p的雙親結(jié)點(diǎn)。刪除過程如下：

(1)若待刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn),直接刪去該結(jié)點(diǎn)。如圖(a)所示,直接刪除結(jié)點(diǎn)9。這是最簡單的刪除結(jié)點(diǎn)的情況。

41

(2)若待刪除的結(jié)點(diǎn)只有左子樹而無右子樹。根據(jù)二叉排序樹的特點(diǎn),可以直接將其左子樹的根結(jié)點(diǎn)放在被刪結(jié)點(diǎn)的位置。如圖(b)所示,*p作為*q的右子樹根結(jié)點(diǎn),要?jiǎng)h除*p結(jié)點(diǎn),只需將*p的左子樹(其根結(jié)點(diǎn)為3)作為*q結(jié)點(diǎn)的右子樹。42

(3)若待刪除的結(jié)點(diǎn)只有右子樹而無左子樹。與(2)情況類似,可以直接將其右子樹的根結(jié)點(diǎn)放在被刪結(jié)點(diǎn)的位置。如圖(c)所示,*p作為*q的左子樹根結(jié)點(diǎn),要?jiǎng)h除*p結(jié)點(diǎn),只需將*p的右子樹(其根結(jié)點(diǎn)為8)作為*q結(jié)點(diǎn)的右子樹。43

(4)若待刪除的結(jié)點(diǎn)同時(shí)有左子樹和右子樹。根據(jù)二叉排序樹的特點(diǎn),可以從其左子樹中選擇關(guān)鍵字最大的結(jié)點(diǎn)或從其右子樹中選擇關(guān)鍵字最小的結(jié)點(diǎn)放在被刪去結(jié)點(diǎn)的位置上。假如選取左子樹上關(guān)鍵字最大的結(jié)點(diǎn),那么該結(jié)點(diǎn)一定是左子樹的最右下結(jié)點(diǎn)。如圖(d)所示,若要?jiǎng)h除*p(其關(guān)鍵字為5)結(jié)點(diǎn),找到其左子樹最右下結(jié)點(diǎn)4,它的雙親結(jié)點(diǎn)為2,用它代替*p結(jié)點(diǎn),并將其原來的左子樹(其根結(jié)點(diǎn)為3)作為原來的雙親結(jié)點(diǎn)2的右子樹。44(算法略)刪除二叉排序樹結(jié)點(diǎn)的算法DeleteBST()如下(指針變量p指向待刪除的結(jié)點(diǎn),指針變量q指向待刪除結(jié)點(diǎn)*p的雙親結(jié)點(diǎn))：

voidDelete1(BSTNode*p,BSTNode*&r)

/*當(dāng)被刪*p結(jié)點(diǎn)有左右子樹時(shí)的刪除過程，開始時(shí)，r是p的左子樹*/{ BSTNode*q; if(r->rchild!=NULL) Delete1(p,r->rchild); /*遞歸找最右下結(jié)點(diǎn)*/ else /*找到了最右下結(jié)點(diǎn)*r*/ {p->key=r->key;/*將*r的關(guān)鍵字值賦給*p*/ q=r;r=r->lchild; /*將左子樹的根結(jié)點(diǎn)放在被刪結(jié)點(diǎn)的位置上*/ free(q);/*釋放原*r的空間*/ }}45voidDelete(BSTNode*&p)/*從二叉排序樹中刪除*p結(jié)點(diǎn)*/{BSTNode*q;if(p->rchild==NULL)/**p結(jié)點(diǎn)沒有右子樹的情況*/{q=p;p=p->lchild; /*其右子樹的根結(jié)點(diǎn)放在被刪結(jié)點(diǎn)的位置上*/free(q);}elseif(p->lchild==NULL)/**p結(jié)點(diǎn)沒有左子樹*/{q=p;p=p->rchild; /*將*p結(jié)點(diǎn)的右子樹作為雙親結(jié)點(diǎn)的相應(yīng)子樹/free(q);}elseDelete1(p,p->lchild); /**p結(jié)點(diǎn)既有左子樹又有右子樹的情況*/}46intDeleteBST(BSTNode*&bt,KeyTypek) /*在bt中刪除關(guān)鍵字為k的結(jié)點(diǎn)*/{if(bt==NULL)return0; /*空樹刪除失敗*/else{if(k<bt->key)returnDeleteBST(bt->lchild,k); /*遞歸在左子樹中刪除為k的結(jié)點(diǎn)*/ elseif(k>bt->key)returnDeleteBST(bt->rchild,k); /*遞歸在右子樹中刪除為k的結(jié)點(diǎn)*/ else {Delete(bt);/*調(diào)用Delete(bt)函數(shù)刪除*bt結(jié)點(diǎn)*/ return1; }}}479.3.2平衡二叉樹(AVL)

若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差1,則稱此二叉樹為平衡二叉樹。在算法中,通過平衡因子(balancdfactor,用bf表示)來具體實(shí)現(xiàn)上述平衡二叉樹的定義。平衡因子的定義是：平衡二叉樹中每個(gè)結(jié)點(diǎn)有一個(gè)平衡因子域,每個(gè)結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)左子樹的高度減去右子樹的高度。從平衡因子的角度可以說,若一棵二叉樹中所有結(jié)點(diǎn)的平衡因子的絕對值小于或等于1,即平衡因子取值為1、0或-1,則該二叉樹稱為平衡二叉樹。48平衡二叉樹和不平衡二叉樹

49定義AVL樹的結(jié)點(diǎn)的類型如下：typedefstructnode /*記錄類型*/{ KeyTypekey; /*關(guān)鍵字項(xiàng)*/ intbf; /*增加的平衡因子*/ InfoTypedata; /*其他數(shù)據(jù)域*/ structnode*lchild,*rchild; /*左右孩子指針*/}BSTNode;501.平衡二叉樹插入新結(jié)點(diǎn)的調(diào)整方法

假定向平衡二叉樹中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡二叉樹的平衡性,首先要找出插入新結(jié)點(diǎn)后失去平衡的最小子樹根結(jié)點(diǎn)的指針,然后再調(diào)整這個(gè)子樹中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系,使之成為新的平衡子樹。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后,原有其他所有不平衡子樹無需調(diào)整,整個(gè)二叉排序樹就又成為一棵平衡二叉樹。失去平衡的最小子樹是指以離插入結(jié)點(diǎn)最近,且平衡因子絕對值大于1的結(jié)點(diǎn)作為根的子樹。假設(shè)用A表示失去平衡的最小子樹的根結(jié)點(diǎn),則調(diào)整該子樹的操作可歸納為下列四種情況：51

(1)LL型調(diào)整52

(2)RR型調(diào)整53

(3)LR型調(diào)整54

(4)RL型調(diào)整55

例9.5輸入關(guān)鍵字序列{16,3,7,11,9,26,18,14,15},給出構(gòu)造一棵AVL樹的步驟。56572.平衡二叉樹刪除結(jié)點(diǎn)的調(diào)整方法要?jiǎng)h除結(jié)點(diǎn)x的方法：(1)采用二叉排序樹的刪除方法刪除結(jié)點(diǎn)x沿根到刪除結(jié)點(diǎn)的路徑之逆逐層向上查找，修改x的各祖先結(jié)點(diǎn)的平衡因子。查找途中，若發(fā)現(xiàn)x的某個(gè)祖先結(jié)點(diǎn)*p失衡，要進(jìn)行調(diào)整。若x在*p的左子樹，則對*p的右子樹調(diào)整（RL或RR）;若x在*p的右子樹，則對*p的左子樹調(diào)整（LL或LR）.調(diào)整后，若引起其他祖先結(jié)點(diǎn)失衡，繼續(xù)調(diào)整，直到根結(jié)點(diǎn)為止。58例9.6對AVL樹，刪除結(jié)點(diǎn)11,9,15的過程59例9.6對AVL樹，刪除結(jié)點(diǎn)11,9,15的過程603.平衡二叉樹的查找

在平衡二叉樹上進(jìn)行查找的過程和在二叉排序樹上進(jìn)行查找的過程完全相同，因此，在平衡二叉樹上進(jìn)行查找關(guān)鍵字的比較次數(shù)不會(huì)超過平衡二叉樹的深度。在最壞的情況下，普通二叉排序樹的查找長度為O(n)。那么，平衡二叉樹的情況又是怎樣的呢？下面分析平衡二叉樹的高度h和結(jié)點(diǎn)個(gè)數(shù)n之間的關(guān)系。61

首先，構(gòu)造一系列的平衡二叉樹T1，T2，T3，…，其中，Th（h=1，2，3，…）是高度為h且結(jié)點(diǎn)數(shù)盡可能少的平衡二叉樹，如圖9.16中所示的T1，T2，T3和T4。為了構(gòu)造Th，先分別構(gòu)造Th-1和Th-2，使Th以Th-1和Th-2作為其根結(jié)點(diǎn)的左、右子樹。對于每一個(gè)Th，只要從中刪去一個(gè)結(jié)點(diǎn)，就會(huì)失去平衡或高度不再是h（顯然，這樣構(gòu)造的平衡二叉樹在結(jié)點(diǎn)個(gè)數(shù)相同的平衡二叉樹中具有最大高度）。圖9.16結(jié)點(diǎn)個(gè)數(shù)n最少的平衡二叉樹62

然后，通過計(jì)算上述平衡二叉樹中的結(jié)點(diǎn)個(gè)數(shù)，來建立高度與結(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系。設(shè)N(h)為Th的結(jié)點(diǎn)數(shù)，從圖9.16中可以看出有下列關(guān)系成立：

N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1當(dāng)h>1時(shí)，此關(guān)系類似于定義Fibonacci數(shù)的關(guān)系：

F(1)=1，F(xiàn)(2)=1，F(xiàn)(h)=F(h-1)+F(h-2)通過檢查兩個(gè)序列的前幾項(xiàng)就可發(fā)現(xiàn)兩者之間的對應(yīng)關(guān)系：

N(h)=F(h+2)-1由于Fibonacci數(shù)滿足漸近公式：F(h)≈其中，故由此可得近似公式：N(h)≈即：h≈log2(N(h)+1)所以，含有n個(gè)結(jié)點(diǎn)的平衡二叉樹的平均查找長度為O(log2n)。639.3.3B-樹

B-樹又稱為多路平衡查找樹,是一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。

B-樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)最大個(gè)數(shù)稱為B-樹的階,通常用m表示,從查找效率考慮,要求m≥3。一棵m階B-樹或者是一棵空樹,或者是滿足下列要求的m叉樹：

(1)樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)(即至多有m-1個(gè)關(guān)鍵字)；一棵5階B-樹649.3.3B-樹

B-樹又稱為多路平衡查找樹,是一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。

B-樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)最大個(gè)數(shù)稱為B-樹的階,通常用m表示,從查找效率考慮,要求m≥3。一棵m階B-樹或者是一棵空樹,或者是滿足下列要求的m叉樹：

(2)除根結(jié)點(diǎn)外,其他結(jié)點(diǎn)至少有m/2個(gè)孩子結(jié)點(diǎn)(即至少有m/2-1=(m-1)/2個(gè)關(guān)鍵字)；一棵5階B-樹659.3.3B-樹

B-樹又稱為多路平衡查找樹,是一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。

B-樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)最大個(gè)數(shù)稱為B-樹的階,通常用m表示,從查找效率考慮,要求m≥3。一棵m階B-樹或者是一棵空樹,或者是滿足下列要求的m叉樹：

(3)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn),則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn)；一棵5階B-樹66(4)每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：np0k1p1k2p2…knpn

其中,n為該結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù),除根結(jié)點(diǎn)外,其他所有結(jié)點(diǎn)的n大于等于m/2-1,且小于等于m-1；ki(1≤i≤n)為該結(jié)點(diǎn)的關(guān)鍵字且滿足ki＜ki+1；pi(0≤i≤n)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)指針且滿足pi(0≤i≤n-1)結(jié)點(diǎn)上的關(guān)鍵字大于等于ki且小于ki+1,pn結(jié)點(diǎn)上的關(guān)鍵字大于kn。

67一棵5階B-樹(5)所有葉子結(jié)點(diǎn)都在同一層上,即B-樹是所有結(jié)點(diǎn)的平衡因子均等于0的多路查找樹。68在B-樹的存儲結(jié)構(gòu)中,各結(jié)點(diǎn)的類型定義如下：#defineMAXM10 /*定義B-樹的最大的階數(shù)*/typedefintKeyType; /*KeyType為關(guān)鍵字類型*/typedefstructnode /*B-樹結(jié)點(diǎn)類型定義*/{intkeynum; /*結(jié)點(diǎn)當(dāng)前擁有的關(guān)鍵字的個(gè)數(shù)*/KeyTypekey[MAXM];/*[1..keynum]存放關(guān)鍵字,[0]不用*/structnode*parent; /*雙親結(jié)點(diǎn)指針*/structnode*ptr[MAXM];/*孩子結(jié)點(diǎn)指針數(shù)組[0..keynum]*/}BTNode;69B-樹的查找

在B-樹中查找給定關(guān)鍵字的方法類似于二叉排序樹上的查找,不同的是在每個(gè)記錄上確定向下查找的路徑不一定是二路(即二叉)的,而是n+1路的。因?yàn)橛涗泝?nèi)的關(guān)鍵字序列是有序的數(shù)量key[1..n],故既可以用順序查找,也可以用折半查找。在一棵B-樹上順序查找關(guān)鍵字為k的方法為：70將k與根結(jié)點(diǎn)中的key[i]進(jìn)行比較：

(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ù)查找。np0k1p1k2p2…knpn71查找K=71722.B-樹的插入將關(guān)鍵字k插入到B-樹的過程分兩步完成：

(1)利用前述的B-樹的查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn)(注意B-樹的插入結(jié)點(diǎn)一定是葉子結(jié)點(diǎn))。

(2)判斷該結(jié)點(diǎn)是否還有空位置,即判斷該結(jié)點(diǎn)是否滿足n＜m-1,若該結(jié)點(diǎn)滿足n＜m-1,說明該結(jié)點(diǎn)還有空位置,直接把關(guān)鍵字k插入到該結(jié)點(diǎn)的合適位置上(即滿足插入后結(jié)點(diǎn)上的關(guān)鍵字仍保持有序)；73

若該結(jié)點(diǎn)有n=m-1,說明該結(jié)點(diǎn)已沒有空位置,需要把結(jié)點(diǎn)分裂成兩個(gè)。分裂的做法是,取一新結(jié)點(diǎn),把原結(jié)點(diǎn)上的關(guān)鍵字和k按升序排序后,從中間位置(即m/2=(m+1)/2之處)把關(guān)鍵字(不包括中間位置的關(guān)鍵字)分成兩部分,左部分所含關(guān)鍵字放在舊結(jié)點(diǎn)中,右部分所含關(guān)鍵字放在新結(jié)點(diǎn)中,中間位置的關(guān)鍵字連同新結(jié)點(diǎn)的存儲位置插入到父親結(jié)點(diǎn)中。如果父結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過Max,則要再分裂,再往上插,直至這個(gè)過程傳到根結(jié)點(diǎn)為止。74例如關(guān)鍵字序列為：{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。創(chuàng)建一棵5階B-樹。建立B-的過程如下圖所示。75{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}763.B-樹的刪除

B-樹的刪除過程與插入過程類似,只是稍為復(fù)雜一些。要使刪除后的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)≥m/2-1,將涉及到結(jié)點(diǎn)的“合并”問題。在B-樹上刪除關(guān)鍵字k的過程分兩步完成：

(1)利用前述的B-樹的查找算法找出該關(guān)鍵字所在的結(jié)點(diǎn)。

(2)在結(jié)點(diǎn)上刪除關(guān)鍵字k分兩種情況：一種是在葉子結(jié)點(diǎn)上刪除關(guān)鍵字；另一種是在非葉子結(jié)點(diǎn)上刪除關(guān)鍵字。77

(3)在非葉子結(jié)點(diǎn)上刪除關(guān)鍵字的過程：假設(shè)要?jiǎng)h除關(guān)鍵字key[i](1≤i≤n),在刪去該關(guān)鍵字后,以該結(jié)點(diǎn)ptr[i]所指子樹中的最小關(guān)鍵字key[min]來代替被刪關(guān)鍵字key[i]所在的位置(注意ptr[i]所指子樹中的最小關(guān)鍵字key[min]一定是在葉子結(jié)點(diǎn)上),然后再以指針ptr[i]所指結(jié)點(diǎn)為根結(jié)點(diǎn)查找并刪除key[min](即再以ptr[i]所指結(jié)點(diǎn)為B-樹的根結(jié)點(diǎn),以key[min]為要?jiǎng)h除的關(guān)鍵字,然后再次調(diào)用B-樹上的刪除算法),這樣也就把在非葉子結(jié)點(diǎn)上刪除關(guān)鍵字k的問題轉(zhuǎn)化成了在葉子結(jié)點(diǎn)上刪除關(guān)鍵字key[min]的問題。78(4)在B-樹的葉子結(jié)點(diǎn)上刪除關(guān)鍵字共有以下三種情況：

①假如被刪結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于Min,說明刪去該關(guān)鍵字后該結(jié)點(diǎn)仍滿足B-樹的定義,則可直接刪去該關(guān)鍵字。79②假如被刪結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于Min,說明刪去關(guān)鍵字后該結(jié)點(diǎn)將不滿足B-樹的定義,此時(shí)若該結(jié)點(diǎn)的左(或右)兄弟結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于Min,則把該結(jié)點(diǎn)的左(或右)兄弟結(jié)點(diǎn)中最大(或最小)的關(guān)鍵字上移到雙親結(jié)點(diǎn)中,同時(shí)把雙親結(jié)點(diǎn)中大于(或小于)上移關(guān)鍵字的關(guān)鍵字下移到要?jiǎng)h除關(guān)鍵字的結(jié)點(diǎn)中,這樣刪去關(guān)鍵字k后該結(jié)點(diǎn)以及它的左(或右)兄弟結(jié)點(diǎn)都仍舊滿足B-樹的定義。80

③假如被刪結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于Min,并且該結(jié)點(diǎn)的左和右兄弟結(jié)點(diǎn)(如果存在的話)中關(guān)鍵字個(gè)數(shù)均等于Min,這時(shí),需把要?jiǎng)h除關(guān)鍵字的結(jié)點(diǎn)與其左(或右)兄弟結(jié)點(diǎn)以及雙親結(jié)點(diǎn)中分割二者的關(guān)鍵字合并成一個(gè)結(jié)點(diǎn)。如果因此使雙親結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)小于Min,則對此雙親結(jié)點(diǎn)做同樣處理,以致于可能直到對根結(jié)點(diǎn)做這樣的處理而使整個(gè)樹減少一層。81

例如,對于上例生成的B-樹,給出刪除8,16,15,4等四個(gè)關(guān)鍵字的過程。829.3.4B+樹

在索引文件組織中,經(jīng)常使用B-樹的一些變形,其中B+樹是一種應(yīng)用廣泛的變形。一棵m階B+樹滿足下列條件：

(1)每個(gè)分支結(jié)點(diǎn)至多有m棵子樹。

(2)除根結(jié)點(diǎn)外,其他每個(gè)分支結(jié)點(diǎn)至少有(m+1)/2棵子樹。

(3)根結(jié)點(diǎn)至少有兩棵子樹,至多有m棵子樹。

(4)有n棵子樹的結(jié)點(diǎn)有n個(gè)關(guān)鍵字。83

(5)所有葉子結(jié)點(diǎn)包含全部(數(shù)據(jù)文件中記錄)關(guān)鍵字及指向相應(yīng)記錄的指針(或存放數(shù)據(jù)文件分塊后每塊的最大關(guān)鍵字及指向該塊的指針),而且葉子結(jié)點(diǎn)按關(guān)鍵字大小順序鏈接(可以把每個(gè)葉子結(jié)點(diǎn)看成是一個(gè)基本索引塊,它的指針不再指向另一級索引塊,而是直接指向數(shù)據(jù)文件中的記錄)。

(6)所有分支結(jié)點(diǎn)(可看成是索引的索引)中僅包含它的各個(gè)子結(jié)點(diǎn)(即下級索引的索引塊)中最大關(guān)鍵字及指向子結(jié)點(diǎn)的指針。84一棵3階的B+樹

85m階的B+樹和m階的B-樹,定義中的前三點(diǎn)是相同的,主要的差異是：

(1)在B+樹中,具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有n棵子樹,即每個(gè)關(guān)鍵字對應(yīng)一棵子樹,而在B-樹中,具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有(n+1)棵子樹。

(2)在B+樹中,每個(gè)結(jié)點(diǎn)(除根結(jié)點(diǎn)外)中的關(guān)鍵字個(gè)數(shù)n的取值范圍是m/2≤n≤m,根結(jié)點(diǎn)n的取值范圍是1≤n≤m；而在B-樹中,它們的取值范圍分別是m/2-1≤n≤m-1和1≤n≤m-1。

(3)B+樹中的所有葉子結(jié)點(diǎn)包含了全部關(guān)鍵字,即其他非葉子結(jié)點(diǎn)中的關(guān)鍵字包含在葉子結(jié)點(diǎn)中,而在B-樹中,葉子結(jié)點(diǎn)包含的關(guān)鍵字與其他結(jié)點(diǎn)包含的關(guān)鍵字是不重復(fù)的。86

(4)B+樹中所有非葉子結(jié)點(diǎn)僅起到索引的作用,即結(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針,不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。而在B-樹中,每個(gè)關(guān)鍵字對應(yīng)一個(gè)記錄的存儲地址。

(5)通常在B+樹上有兩個(gè)頭指針,一個(gè)指向根結(jié)點(diǎn),另一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn),所有葉子結(jié)點(diǎn)鏈接成一個(gè)不定長的線性鏈表。879.4哈希表查找9.4.1哈希表的基本概念

哈希表(HashTable)又稱散列表,是除順序表存儲結(jié)構(gòu)、鏈接表存儲結(jié)構(gòu)和索引表存儲結(jié)構(gòu)之外的又一種存儲線性表的存儲結(jié)構(gòu)。哈希表存儲的基本思路是：設(shè)要存儲的對象個(gè)數(shù)為n,設(shè)置一個(gè)長度為m(m≥n)的連續(xù)內(nèi)存單元,以線性表中每個(gè)對象的關(guān)鍵字ki(0≤i≤n-1)為自變量,通過一個(gè)稱為哈希函數(shù)的函數(shù)h(ki),把ki映射為內(nèi)存單元的地址(或稱下標(biāo))h(ki),并把該對象存儲在這個(gè)內(nèi)存單元中。h(ki)也稱為哈希地址(又稱散列地址)。把如此構(gòu)造的線性表存儲結(jié)構(gòu)稱為哈希表。

88{Zhao,Qian,

Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對于如下9個(gè)關(guān)鍵字設(shè)

散列函數(shù)f(key)=

(第一個(gè)字母-'A'+1)/2ChenZhaoQianSunLiWuHanYeDei散列函數(shù)；散列地址；散列表89設(shè)f(key)=(第一個(gè)字母-'A'+1)/2{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}138961114122012345678910111213

數(shù)組

ChenDeiHanLiQianSunWuYezhao

找：key=“Qian”f(key)=8

問題:若添加關(guān)鍵字Zhou,怎么辦？沖突：

key1key2而f(key1)=f(key2)具有相同散列地址的兩個(gè)關(guān)鍵字，稱為該散列函數(shù)的同義詞散列表的查找90

但是存在這樣的問題,對于兩個(gè)關(guān)鍵字ki和kj(i≠j),有ki≠kj(i≠j),但h(ki)=h(kj)。我們把這種現(xiàn)象叫做哈希沖突。通常把這種具有不同關(guān)鍵字而具有相同哈希地址的對象稱做“同義詞”,由同義詞引起的沖突稱作同義詞沖突。在哈希表存儲結(jié)構(gòu)的存儲中,同義詞沖突是很難避免的,除非關(guān)鍵字的變化區(qū)間小于等于哈希地址的變化區(qū)間,而這種情況當(dāng)關(guān)鍵字取值不連續(xù)時(shí)是非常浪費(fèi)存儲空間的。通常的實(shí)際情況是關(guān)鍵字的取值區(qū)間遠(yuǎn)大于哈希地址的變化區(qū)間。91歸納起來：

(1)哈希函數(shù)是一個(gè)映象,即：將關(guān)鍵字的集合映射到某個(gè)地址集合上,它的設(shè)置很靈活,只要這個(gè)地址集合的大小不超出允許范圍即可；

(2)由于哈希函數(shù)是一個(gè)壓縮映象,因此,在一般情況下,很容易產(chǎn)生“沖突”現(xiàn)象,即：key1key2,而f(key1)=f(key2)。

(3)很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下,只能選擇恰當(dāng)?shù)墓：瘮?shù),使沖突盡可能少地產(chǎn)生。929.4.2哈希函數(shù)構(gòu)造方法

構(gòu)造哈希函數(shù)的目標(biāo)是使得到的哈希地址盡可能均勻地分布在n個(gè)連續(xù)內(nèi)存單元地址上,同時(shí)使計(jì)算過程盡可能簡單以達(dá)到盡可能高的時(shí)間效率。

1.直接定址法

直接定址法是以關(guān)鍵字k本身或關(guān)鍵字加上某個(gè)數(shù)值常量c作為哈希地址的方法。直接定址法的哈希函數(shù)h(k)為：

h(k)=k+c(c≥0)

這種哈希函數(shù)計(jì)算簡單,并且不可能有沖突發(fā)生。當(dāng)關(guān)鍵字的分布基本連續(xù)時(shí),可用直接定址法的哈希函數(shù)；否則,若關(guān)鍵字分布不連續(xù)將造成內(nèi)存單元的大量浪費(fèi)。93

2.除留余數(shù)法

除留余數(shù)法是用關(guān)鍵字k除以某個(gè)不大于哈希表長度m的數(shù)p所得的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù)h(k)為：

h(k)=kmodp(mod為求余運(yùn)算,p≤m)

p最好取小于m的質(zhì)數(shù)(素?cái)?shù))。94