數(shù)據(jù)結(jié)構(gòu)金良兵lbjin@浙江師范大學(xué)第9章查找

數(shù)據(jù)的組織和查找是大多數(shù)應(yīng)用程序的核心，而查找是所有數(shù)據(jù)處理中最基本、最常用的操作。特別當(dāng)查找的對(duì)象是一個(gè)龐大數(shù)量的數(shù)據(jù)集合中的元素時(shí)，查找的方法和效率就顯得格外重要。本章主要討論順序表、有序表、樹(shù)表和哈希表查找的各種實(shí)現(xiàn)方法，以及相應(yīng)查找方法在等概率情況下的平均查找長(zhǎng)度。9.1

查找的概念查找表(SearchTable)：相同類型的數(shù)據(jù)元素(對(duì)象)組成的集合，每個(gè)元素通常由若干數(shù)據(jù)項(xiàng)構(gòu)成。關(guān)鍵字(Key，碼)：數(shù)據(jù)元素中某個(gè)(或幾個(gè))數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。若關(guān)鍵字能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則關(guān)鍵字稱為主關(guān)鍵字；將能標(biāo)識(shí)若干個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為次關(guān)鍵字。查找/檢索(Searching)：根據(jù)給定的K值，在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。◆

查找表中存在滿足條件的記錄：查找成功；結(jié)果：所查到的記錄信息或記錄在查找表中的位置?！?/p>

查找表中不存在滿足條件的記錄：查找失敗。查找有兩種基本形式：靜態(tài)查找和動(dòng)態(tài)查找。

靜態(tài)查找(StaticSearch)：在查找時(shí)只對(duì)數(shù)據(jù)元素進(jìn)行查詢或檢索，查找表稱為靜態(tài)查找表。

動(dòng)態(tài)查找(DynamicSearch)：在實(shí)施查找的同時(shí)，插入查找表中不存在的記錄，或從查找表中刪除已存在的某個(gè)記錄，查找表稱為動(dòng)態(tài)查找表。

查找的對(duì)象是查找表，采用何種查找方法，首先取決于查找表的組織。查找表是記錄的集合，而集合中的元素之間是一種完全松散的關(guān)系，因此，查找表是一種非常靈活的數(shù)據(jù)結(jié)構(gòu)，可以用多種方式來(lái)存儲(chǔ)。根據(jù)存儲(chǔ)結(jié)構(gòu)的不同，查找方法可分為三大類：①順序表和鏈表的查找：將給定的K值與查找表中記錄的關(guān)鍵字逐個(gè)進(jìn)行比較，找到要查找的記錄；②散列表的查找：根據(jù)給定的K值直接訪問(wèn)查找表，從而找到要查找的記錄；③索引查找表的查找：先根據(jù)索引確定待查找記錄所在的塊，再?gòu)膲K中找到要查找的記錄。查找方法評(píng)價(jià)指標(biāo)

查找過(guò)程中主要操作是關(guān)鍵字的比較，查找過(guò)程中關(guān)鍵字的平均比較次數(shù)(平均查找長(zhǎng)度ASL：AverageSearchLength)作為衡量一個(gè)查找算法效率高低的標(biāo)準(zhǔn)ASL定義為：ASL=∑PiCin為查找表中記錄個(gè)數(shù)i=1n∑Pi=1i=1n其中：Pi

：查找第i個(gè)記錄的概率，不失一般性，認(rèn)為查找每個(gè)記錄的概率相等，即P1=P2=…=Pn=1/n；Ci：查找第i個(gè)記錄需要進(jìn)行比較的次數(shù)。一般地，認(rèn)為記錄的關(guān)鍵字是一些可以進(jìn)行比較運(yùn)算的類型，如整型、字符型、實(shí)型等，本章以后各節(jié)中討論所涉及的關(guān)鍵字、數(shù)據(jù)元素等的類型描述如下：典型的關(guān)鍵字類型說(shuō)明是：typedeffloatKeyType;/*實(shí)型*/typedefintKeyType;/*整型*/typedefcharKeyType;/*字符串型*/數(shù)據(jù)元素類型的定義：typedefstructRecType{KeyTypekey;/*關(guān)鍵字碼*/……/*其他域*/}RecType;

對(duì)兩個(gè)關(guān)鍵字的比較約定為如下帶參數(shù)的宏定義：/*對(duì)數(shù)值型關(guān)鍵字*/#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))/*對(duì)字符串型關(guān)鍵字*/#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)9.2

靜態(tài)查找

靜態(tài)查找表的抽象數(shù)據(jù)類型定義如下：ADTStatic_SearchTable{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合，各個(gè)數(shù)據(jù)元素有唯一標(biāo)識(shí)的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬于一個(gè)集合?；静僮鱌：┇}ADTStatic_SearchTable詳見(jiàn)p216。線性表是查找表最簡(jiǎn)單的一種組織方式，本節(jié)介紹幾種主要的關(guān)于順序存儲(chǔ)結(jié)構(gòu)的查找方法。9.2.1順序查找(SequentialSearch)1查找思想

從表的一端開(kāi)始逐個(gè)將記錄的關(guān)鍵字和給定K值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字和給定K值相等，查找成功；否則，若掃描完整個(gè)表，仍然沒(méi)找到相應(yīng)的記錄，則查找失敗。順序表的類型定義如下：

#defineMAX_SIZE100typedefstructSSTable{RecTypeelem[MAX_SIZE];/*順序表*/intlength;/*實(shí)際元素個(gè)數(shù)*/}SSTable;intSeq_Search(SSTableST,KeyTypekey){intp;ST.elem[0].key=key;//設(shè)置監(jiān)視哨兵,失敗返回0for(p=ST.length;!EQ(ST.elem[p].key,key);p--)return(p);}比較次數(shù)：查找第n個(gè)元素：1……….查找第i個(gè)元素：n-i+1查找第1個(gè)元素：n查找失?。簄+12算法分析不失一般性，設(shè)查找每個(gè)記錄成功的概率相等，即Pi=1/n；查找第i個(gè)元素成功的比較次數(shù)Ci=n-i+1；◆

查找成功時(shí)的平均查找長(zhǎng)度ASL：ASL=∑PiCi=i=1n∑(n-i+1)=i=1nn―12n+164513192137566475808892監(jiān)視哨查找6401234567891011ppppp比較次數(shù)=5圖9-1順序查找示例ASL=∑PiCi=i=1n2n+1∑(n-i+1)+i=1n2n1=3(n+1)/4◆

包含查找不成功時(shí)：查找失敗的比較次數(shù)為n+1，若成功與不成功的概率相等，對(duì)每個(gè)記錄的查找概率為Pi=1/(2n)，則平均查找長(zhǎng)度ASL：9.2.2

折半查找(BinarySearch)折半查找又稱為二分查找，是一種效率較高的查找方法。

前提條件：查找表中的所有記錄是按關(guān)鍵字有序(升序或降序)。查找過(guò)程中，先確定待查找記錄在表中的范圍，然后逐步縮小范圍(每次將待查記錄所在區(qū)間縮小一半)，直到找到或找不到記錄為止。1查找思想

用Low、High和Mid表示待查找區(qū)間的下界、上界和中間位置指針，初值為L(zhǎng)ow=1，High=n。⑴取中間位置Mid：Mid=(Low+High)/2；⑵比較中間位置記錄的關(guān)鍵字與給定的K值：①相等：查找成功；②大于：待查記錄在區(qū)間的前半段，修改上界指針：High=Mid-1，轉(zhuǎn)⑴；③小于：待查記錄在區(qū)間的后半段，修改下界指針：Low=Mid+1，轉(zhuǎn)⑴；直到越界(Low>High)，查找失敗。2算法實(shí)現(xiàn)intBin_Search(SSTableST,KeyTypekey){intLow=1，High=ST.length,Mid;while(Low<High){Mid=(Low+High)/2;if(EQ(ST.elem[Mid].key,key))

return(Mid);elseif(LT(ST.elem[Mid].key,key))

Low=Mid+1;

elseHigh=Mid-1;}return(0);/*查找失敗*/}查找21

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow(a)查找成功示例3算法示例如圖9-2(a)，(b)所示。查找71

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow(b)查找不成功示例圖9-2折半查找示例4算法分析①查找時(shí)每經(jīng)過(guò)一次比較，查找范圍就縮小一半，該過(guò)程可用一棵二叉樹(shù)表示：◆

根結(jié)點(diǎn)就是第一次進(jìn)行比較的中間位置的記錄；◆排在中間位置前面的作為左子樹(shù)的結(jié)點(diǎn)；◆排在中間位置后面的作為右子樹(shù)的結(jié)點(diǎn)；對(duì)各子樹(shù)來(lái)說(shuō)都是相同的。這樣所得到的二叉樹(shù)稱為判定樹(shù)(DecisionTree)。②將二叉判定樹(shù)的第㏒2n+1層上的結(jié)點(diǎn)補(bǔ)齊就成為一棵滿二叉樹(shù)，深度不變，h=㏒2(n+1)

。③由滿二叉樹(shù)性質(zhì)知，第i層上的結(jié)點(diǎn)數(shù)為2i-1(i≤h)，設(shè)表中每個(gè)記錄的查找概率相等，即Pi=1/n，查找成功時(shí)的平均查找長(zhǎng)度ASL：ASL=∑PiCi=i=1n∑j2j-1=j=1hn―1nn+1㏒2(n+1)-1當(dāng)n很大(n>50)時(shí)，ASL≈㏒2(n+1)-1。9.2.3

分塊查找

分塊查找(BlockingSearch)又稱索引順序查找，是前面兩種查找方法的綜合。1查找表的組織①

將查找表分成幾塊。塊間有序，即第i+1塊的所有記錄關(guān)鍵字均大于(或小于)第i塊記錄關(guān)鍵字；塊內(nèi)無(wú)序。②在查找表的基礎(chǔ)上附加一個(gè)索引表，索引表是按關(guān)鍵字有序的，索引表中記錄的構(gòu)成是：最大關(guān)鍵字起始指針2查找思想

先確定待查記錄所在塊，再在塊內(nèi)查找(順序查找)3算法實(shí)現(xiàn)typedefstructIndexType{keyTypemaxkey;/*塊中最大的關(guān)鍵字*/intstartpos;/*塊的起始位置指針*/}Index;intBlock_search(RecTypeST[],Indexind[],KeyTypekey,intn,intb)/*表長(zhǎng)為n，塊數(shù)為b*//*在分塊索引表中查找關(guān)鍵字為key的記錄*/{inti=0,j,k;while((i<b)&<(ind[i].maxkey,key))i++;if(i>b){printf("\nNotfound");return(0);}j=ind[i].startpos;while((j<n)&&LQ(ST[j].key,ind[i].maxkey)){if(EQ(ST[j].key,key))break;j++;}/*在塊內(nèi)查找*/if(j>n||!EQ(ST[j].key,key)){j=0;printf("\nNotfound");}return(j);}4算法示例索引表1234567891011121314151617182212138920334244382448605874578653查38224886

1713圖9-3分塊查找示例5

算法分析設(shè)表長(zhǎng)為n個(gè)記錄，均分為b塊，每塊記錄數(shù)為s，則b=?n/s?。設(shè)記錄的查找概率相等，每塊的查找概率為1/b，塊中記錄的查找概率為1/s，則平均查找長(zhǎng)度ASL：ASL=Lb+Lw=∑j+j=1b∑i=i=1ss―12b+12s+1+9.2.4Fibonacci查找

Fibonacci查找方法是根據(jù)Fibonacci數(shù)列的特點(diǎn)對(duì)查找表進(jìn)行分割。Fibonacci數(shù)列的定義是：

F(0)=0，F(xiàn)(1)=1，F(xiàn)(j)=F(j-1)+F(j-2)。1查找思想設(shè)查找表中的記錄數(shù)比某個(gè)Fibonacci數(shù)小1，即設(shè)n=F(j)-1。用Low、High和Mid表示待查找區(qū)間的下界、上界和分割位置，初值為L(zhǎng)ow=1，High=n。⑴取分割位置Mid：Mid=F(j-1)；⑵比較分割位置記錄的關(guān)鍵字與給定的K值：①相等：查找成功；②

大于：待查記錄在區(qū)間的前半段(區(qū)間長(zhǎng)度為F(j-1)-1)，修改上界指針：High=Mid-1，轉(zhuǎn)⑴；③小于：待查記錄在區(qū)間的后半段(區(qū)間長(zhǎng)度為F(j-2)-1)，修改下界指針：Low=Mid+1，轉(zhuǎn)⑴；直到越界(Low>High)，查找失敗。2算法實(shí)現(xiàn)在算法實(shí)現(xiàn)時(shí)，為了避免頻繁計(jì)算Fibonacci數(shù)，可用兩個(gè)變量f1和f2保存當(dāng)前相鄰的兩個(gè)Fibonacci數(shù)，這樣在以后的計(jì)算中可以依次遞推計(jì)算出。intfib(intn){inti,f,f0=0,f1=1;if(n==0)return(0);if(n==1)return(1);for(i=2;i<=n;i++){f=f0+f1;f0=f1;f1=f;}return(f);}intFib_search(RecTypeST[],KeyTypekey,intn)/*在有序表ST中用Fibonacci方法查找關(guān)鍵字為key的記錄*/{intLow=1,High,Mid,f1,f2;High=n;f1=fib(n-1);f2=fib(n-2);while(Low<=High){Mid=Low+f1-1;if(EQ(ST.[Mid].key,key))return(Mid);elseif(LT(key,ST.[Mid].key)){High=Mid-1;f2=f1-f2;f1=f1-f2;}else{Low=Mid+1;f1=f1-f2;f2=f2-f1;}}return(0);}

由算法知，F(xiàn)ibonacci查找在最壞情況下性能比折半查找差，但折半查找要求記錄按關(guān)鍵字有序；Fibonacci查找的優(yōu)點(diǎn)是分割時(shí)只需進(jìn)行加、減運(yùn)算。9.3

動(dòng)態(tài)查找

當(dāng)查找表以線性表的形式組織時(shí)，若對(duì)查找表進(jìn)行插入、刪除或排序操作，就必須移動(dòng)大量的記錄，當(dāng)記錄數(shù)很多時(shí)，這種移動(dòng)的代價(jià)很大。利用樹(shù)的形式組織查找表，可以對(duì)查找表進(jìn)行動(dòng)態(tài)

高效的查找。查找方法比較順序查找折半查找分塊查找ASL最大最小兩者之間表結(jié)構(gòu)有序表、無(wú)序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表9.3.1二叉排序樹(shù)(BST)的定義二叉排序樹(shù)(BinarySortTree或BinarySearchTree)的定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿足下列性質(zhì)的二叉樹(shù)。(1)：若左子樹(shù)不為空，則左子樹(shù)上所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根結(jié)點(diǎn)的值；(2)：若右子樹(shù)不為空，則右子樹(shù)上所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根結(jié)點(diǎn)的值；(3)：左、右子樹(shù)都分別是二叉排序樹(shù)。

結(jié)論：若按中序遍歷一棵二叉排序樹(shù)，所得到的結(jié)點(diǎn)序列是一個(gè)遞增序列。

BST仍然可以用二叉鏈表來(lái)存儲(chǔ)，如圖9-4所示。圖9-4二叉排序樹(shù)1624271241518結(jié)點(diǎn)類型定義如下：

typedefstructNode{KeyTypekey;/*關(guān)鍵字域*/…/*其它數(shù)據(jù)域*/structNode*Lchild,*Rchild;}BSTNode;

9.3.2BST樹(shù)的查找1查找思想

首先將給定的K值與二叉排序樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：若相等：則查找成功；①

給定的K值小于BST的根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的左子樹(shù)上進(jìn)行查找；②給定的K值大于BST的根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的右子樹(shù)上進(jìn)行查找。2算法實(shí)現(xiàn)⑴遞歸算法BSTNode*BST_Serach(BSTNode*T,KeyTypekey){if(T==NULL)return(NULL);else{if(EQ(T->key,key))return(T);elseif(LT(key,T->key))return(BST_Serach(T->Lchild,key));elsereturn(BST_Serach(T->Rchild,key));}}

⑵非遞歸算法BSTNode*BST_Serach(BSTNode*T,KeyTypekey){BSTNodep=T;while(p!=NULL&&!EQ(p->key,key)){if(LT(key,p->key))p=p->Lchild;elsep=p->Rchild;}if(EQ(p->key,key))return(p);elsereturn(NULL);}

在隨機(jī)情況下，二叉排序樹(shù)的平均查找長(zhǎng)度ASL和㏒(n)(樹(shù)的深度)是等數(shù)量級(jí)的。9.3.3BST樹(shù)的插入在BST樹(shù)中插入一個(gè)新結(jié)點(diǎn)，要保證插入后仍滿足BST的性質(zhì)。1

插入思想

在BST樹(shù)中插入一個(gè)新結(jié)點(diǎn)x時(shí)，若BST樹(shù)為空，則令新結(jié)點(diǎn)x為插入后BST樹(shù)的根結(jié)點(diǎn)；否則，將結(jié)點(diǎn)x的關(guān)鍵字與根結(jié)點(diǎn)T的關(guān)鍵字進(jìn)行比較：①

若相等：不需要插入；②若x.key<T->key：結(jié)點(diǎn)x插入到T的左子樹(shù)中；③若x.key>T->key：結(jié)點(diǎn)x插入到T的右子樹(shù)中。2算法實(shí)現(xiàn)⑴遞歸算法voidInsert_BST(BSTNode*T,KeyTypekey){BSTNode*x;x=(BSTNode*)malloc(sizeof(BSTNode));X->key=key;x->Lchild=x->Rchild=NULL;if(T==NULL)T=x;else{if(EQ(T->key,x->key))return;/*已有結(jié)點(diǎn)*/elseif(LT(x->key,T->key))

Insert_BST(T->Lchild,key);

elseInsert_BST(T->Rchild,key);}}⑵非遞歸算法voidInsert_BST(BSTNode*T,KeyTypekey){BSTNode*x,*p,*q;x=(BSTNode*)malloc(sizeof(BSTNode));X->key=key;

x->Lchild=x->Rchild=NULL;if(T==NULL)T=x;else{p=T;while(p!=NULL){if(EQ(p->key,x->key))return;q=p;/*q作為p的父結(jié)點(diǎn)*/

if(LT(x->key,p->key))p=p->Lchild;elsep=p->Rchild;}if(LT(x->key,q->key))q->Lchild=x;elseq->Rchild=x;}}

由結(jié)論知，對(duì)于一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵BST樹(shù)而變成一個(gè)有序序列。由算法知，每次插入的新結(jié)點(diǎn)都是BST樹(shù)的葉子結(jié)點(diǎn)，即在插入時(shí)不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針。利用BST樹(shù)的插入操作，可以從空樹(shù)開(kāi)始逐個(gè)插入每個(gè)結(jié)點(diǎn)，從而建立一棵BST樹(shù)，算法如下：#defineENDKEY65535BSTNode*create_BST(){KeyTypekey;BSTNode*T=NULL;scanf(“%d”,&key);while(key!=ENDKEY){Insert_BST(T,key);

scanf(“%d”,&key);}return(T);}9.3.4BST樹(shù)的刪除

1刪除操作過(guò)程分析

從BST樹(shù)上刪除一個(gè)結(jié)點(diǎn)，仍然要保證刪除后滿足BST的性質(zhì)。設(shè)被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f，刪除情況如下：①若p是葉子結(jié)點(diǎn)：直接刪除p，如圖9-5(b)所示。

②若p只有一棵子樹(shù)(左子樹(shù)或右子樹(shù))：直接用p的左子樹(shù)(或右子樹(shù))取代p的位置而成為f的一棵子樹(shù)。即原來(lái)p是f的左子樹(shù)，則p的子樹(shù)成為f的左子樹(shù)；原來(lái)p是f的右子樹(shù)，則p的子樹(shù)成為f的右子樹(shù)，如圖9-5(c)、(d)所示。③若p既有左子樹(shù)又有右子樹(shù)

：處理方法有以下兩種，可以任選其中一種?！?/p>

用p的直接前驅(qū)結(jié)點(diǎn)代替p。即從p的左子樹(shù)中選擇值最大的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。s是p的左子樹(shù)中的最右邊的結(jié)點(diǎn)且沒(méi)有右子樹(shù)，對(duì)s的刪除同②，如圖9-5(e)所示。◆

用p的直接后繼結(jié)點(diǎn)代替p。即從p的右子樹(shù)中選擇值最小的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。s是p的右子樹(shù)中的最左邊的結(jié)點(diǎn)且沒(méi)有左子樹(shù)，對(duì)s的刪除同②，如圖9-5(f)所示。圖9-5BST樹(shù)的結(jié)點(diǎn)刪除情況(e)刪除結(jié)點(diǎn)12986151314(d)刪除結(jié)點(diǎn)159861314128610151913149(a)BST樹(shù)1286101513149(b)刪除結(jié)點(diǎn)1912869151314(c)刪除結(jié)點(diǎn)102算法實(shí)現(xiàn)voidDelete_BST(BSTNode*T,KeyTypekey)

/*在以T為根結(jié)點(diǎn)的BST樹(shù)中刪除關(guān)鍵字為key的結(jié)點(diǎn)*/{BSTNode*p=T,*f=NULL,*q,*s;while(p!=NULL&&!EQ(p->key,key)){f=p;if(LT(key,p->key))p=p->Lchild;/*搜索左子樹(shù)*/else

p=p->Rchild;/*搜索右子樹(shù)*/}if(p==NULL)return;/*沒(méi)有要?jiǎng)h除的結(jié)點(diǎn)*/s=p;/*找到了要?jiǎng)h除的結(jié)點(diǎn)為p*/

if(p->Lchild!=NULL&&p->Rchild!=NULL){f=p;s=p->Lchild;/*從左子樹(shù)開(kāi)始找*/while(s->Rchild!=NULL)

{f=s;s=s->Rchild;}//左、右子樹(shù)都不空，找左子樹(shù)中最右邊的結(jié)點(diǎn)p->key=s->key;p->otherinfo=s->otherinfo;//

用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容}/*將第3種情況轉(zhuǎn)換為第2種情況*/if(s->Lchild!=NULL)//若s有左子樹(shù)，右子樹(shù)為空q=s->Lchild;elseq=s->Rchild;if(f==NULL)T=q;elseif(f->Lchild==s)f->Lchild=q;elsef->Rchild=q;free(s);}9.4平衡二叉樹(shù)(AVL)

BST是一種查找效率比較高的組織形式，但其平均查找長(zhǎng)度受樹(shù)的形態(tài)影響較大，形態(tài)比較均勻時(shí)查找效率很好，形態(tài)明顯偏向某一方向時(shí)其效率就大大降低。因此，希望有更好的二叉排序樹(shù)，其形態(tài)總是均衡的，查找時(shí)能得到最好的效率，這就是平衡二叉排序樹(shù)。平衡二叉排序樹(shù)(BalancedBinaryTree或Height-BalancedTree)是在1962年由Adelson-Velskii和Landis提出的，又稱AVL樹(shù)。9.4.1平衡二叉樹(shù)的定義平衡二叉樹(shù)或者是空樹(shù)，或者是滿足下列性質(zhì)的二叉樹(shù)。⑴：左子樹(shù)和右子樹(shù)深度之差的絕對(duì)值不大于1；⑵：左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。

平衡因子(BalanceFactor)：二叉樹(shù)上結(jié)點(diǎn)的左子樹(shù)的深度減去其右子樹(shù)深度稱為該結(jié)點(diǎn)的平衡因子。因此，平衡二叉樹(shù)上每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0和1，否則，只要有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，該二叉樹(shù)就不是平衡二叉樹(shù)。如果一棵二叉樹(shù)既是二叉排序樹(shù)又是平衡二叉樹(shù)，稱為平衡二叉排序樹(shù)(BalancedBinarySortTree)。在平衡二叉排序樹(shù)上執(zhí)行查找的過(guò)程與二叉排序樹(shù)上的查找過(guò)程完全一樣，則在AVL樹(shù)上執(zhí)行查找時(shí)，和給定的K值比較的次數(shù)不超過(guò)樹(shù)的深度。

設(shè)深度為h的平衡二叉排序樹(shù)所具有的最少結(jié)點(diǎn)數(shù)為Nh，則由平衡二叉排序樹(shù)的性質(zhì)知：圖9-6平衡二叉樹(shù)16241241518結(jié)點(diǎn)類型定義如下：

typedefstructBNode{KeyTypekey;/*關(guān)鍵字域*/intBfactor;/*平衡因子域*/…/*其它數(shù)據(jù)域*/structBNode*Lchild,*Rchild;}BSTNode;

N0=0，N1=1，N2=2，…

，Nh=Nh-1+Nh-2

該關(guān)系和Fibonacci數(shù)列相似。根據(jù)歸納法可證明，當(dāng)h≥0時(shí)，Nh=Fh+2-1，…而這樣，含有n個(gè)結(jié)點(diǎn)的平衡二叉排序樹(shù)的最大深度為h≈√5㏒φ((n+1))-2φh√5Fh≈21+√5其中φ=φh√5則Nh≈-1則在平衡二叉排序樹(shù)上進(jìn)行查找的平均查找長(zhǎng)度和㏒2n是一個(gè)數(shù)量級(jí)的，平均時(shí)間復(fù)雜度為O(㏒2n)。9.4.2平衡化旋轉(zhuǎn)

一般的二叉排序樹(shù)是不平衡的，若能通過(guò)某種方法使其既保持有序性，又具有平衡性，就找到了構(gòu)造平衡二叉排序樹(shù)的方法，該方法稱為平衡化旋轉(zhuǎn)。在對(duì)AVL樹(shù)進(jìn)行插入或刪除一個(gè)結(jié)點(diǎn)后，通常會(huì)影響到從根結(jié)點(diǎn)到插入(或刪除)結(jié)點(diǎn)的路徑上的某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的子樹(shù)可能發(fā)生變化。以插入結(jié)點(diǎn)為例，影響有以下幾種可能性◆

以某些結(jié)點(diǎn)為根的子樹(shù)的深度發(fā)生了變化；◆

某些結(jié)點(diǎn)的平衡因子發(fā)生了變化；◆

某些結(jié)點(diǎn)失去平衡。1LL型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的左孩子的左子樹(shù)上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。a插入前的平衡因子是1，插入后的平衡因子是2。設(shè)b是a的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1(否則b就是失衡結(jié)點(diǎn))。⑵平衡化旋轉(zhuǎn)方法通過(guò)順時(shí)針旋轉(zhuǎn)操作實(shí)現(xiàn)，如圖9-7所示。

沿著插入結(jié)點(diǎn)上行到根結(jié)點(diǎn)就能找到某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的平衡因子和子樹(shù)深度都會(huì)發(fā)生變化，這樣的結(jié)點(diǎn)稱為失衡結(jié)點(diǎn)。用b取代a的位置，a成為b的右子樹(shù)的根結(jié)點(diǎn)，b原來(lái)的右子樹(shù)作為a的左子樹(shù)。⑶插入后各結(jié)點(diǎn)的平衡因子分析①旋轉(zhuǎn)前的平衡因子設(shè)插入后b的左子樹(shù)的深度為HbL，則其右子樹(shù)的深度為HbL-1；a的左子樹(shù)的深度為HbL+1。abbRaRbLxabbRaRbLx圖9-7LL型平衡化旋轉(zhuǎn)示意圖a的平衡因子為2，則a的右子樹(shù)的深度為：HaR=HbL+1-2=HbL-1。②旋轉(zhuǎn)后的平衡因子

a的右子樹(shù)沒(méi)有變，而左子樹(shù)是b的右子樹(shù)，則平衡因子是：HaL-HaR=(HbL-1)-(HbL-1)=0

即a是平衡的，以a為根的子樹(shù)的深度是HbL。

b的左子樹(shù)沒(méi)有變化，右子樹(shù)是以a為根的子樹(shù)，則平衡因子是：HbL-HbL=0

即b也是平衡的，以b為根的子樹(shù)的深度是HbL+1，與插入前a的子樹(shù)的深度相同，則該子樹(shù)的上層各結(jié)點(diǎn)的平衡因子沒(méi)有變化，即整棵樹(shù)旋轉(zhuǎn)后是平衡的。⑷旋轉(zhuǎn)算法voidLL_rotate(BBSTNode*a){BBSTNode*b;b=a->Lchild;a->Lchild=b->Rchild;b->Rchild=a;a->Bfactor=b->Bfactor=0;a=b;}2LR型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的左孩子的右子樹(shù)上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。設(shè)b是a的左孩子，c為b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點(diǎn)。⑵插入后結(jié)點(diǎn)c的平衡因子的變化分析

①插入后c的平衡因子是1：即在c的左子樹(shù)上插入。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度為HcL-1；b插入后的平衡因子是-1，則b的左子樹(shù)的深度為HcL，以b為根的子樹(shù)的深度是HcL+2。

因插入后a的平衡因子是2，則a的右子樹(shù)的深度是HcL。

②插入后c的平衡因子是0：c本身是插入結(jié)點(diǎn)。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度也是HcL；因b插入后的平衡因子是-1，則b的左子樹(shù)的深度為HcL，以b為根的子樹(shù)的深度是HcL+2；插入后a的平衡因子是2，則a的右子樹(shù)的深度是HcL。③插入后c的平衡因子是-1：即在c的右子樹(shù)上插入。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度為HcL+1，以c為根的子樹(shù)的深度是HcL+2；因b插入后的平衡因子是-1，則b的左子樹(shù)的深度為HcL+1，以b為根的子樹(shù)的深度是HcL+3；則a的右子樹(shù)的深度是HcL+1。⑶平衡化旋轉(zhuǎn)方法

先以b進(jìn)行一次逆時(shí)針旋轉(zhuǎn)(將以b為根的子樹(shù)旋轉(zhuǎn)為以c為根)，再以a進(jìn)行一次順時(shí)針旋轉(zhuǎn)，如圖9-8所示。將整棵子樹(shù)旋轉(zhuǎn)為以c為根，b是c的左子樹(shù)，a是c的右子樹(shù)；c的右子樹(shù)移到a的左子樹(shù)位置，c的左子樹(shù)移到b的右子樹(shù)位置。圖9-8LR型平衡化旋轉(zhuǎn)示意圖abbLaRcLxcRxcacbLaRcLxcRxb⑷旋轉(zhuǎn)后各結(jié)點(diǎn)(a,b,c)平衡因子分析

①

旋轉(zhuǎn)前(插入后)c的平衡因子是1：

a的左子樹(shù)深度為HcL-1，其右子樹(shù)沒(méi)有變化，深度是HcL，則a的平衡因子是-1；b的左子樹(shù)沒(méi)有變化，深度為HcL，右子樹(shù)是c旋轉(zhuǎn)前的左子樹(shù)，深度為HcL，則b的平衡因子是0；c的左、右子樹(shù)分別是以b和a為根的子樹(shù)，則c的平衡因子是0

。

②

旋轉(zhuǎn)前

(插入后)c的平衡因子是0：旋轉(zhuǎn)后a，b，c的平衡因子都是0

。

③

旋轉(zhuǎn)前

(插入后)c的平衡因子是-1：旋轉(zhuǎn)后a，b，c的平衡因子分別是0，-1，0

。綜上所述，即整棵樹(shù)旋轉(zhuǎn)后是平衡的。⑸旋轉(zhuǎn)算法voidLR_rotate(BBSTNode*a){BBSTNode*b,*c;b=a->Lchild;c=b->Rchild;/*初始化*/a->Lchild=c->Rchild;b->Rchild=c->Lchild;c->Lchild=b;c->Rchild=a;if(c->Bfactor==1){a->Bfactor=-1;b->Bfactor=0;}elseif(c->Bfactor==0)a->Bfactor=b->Bfactor=0;else{a->Bfactor=0;b->Bfactor=1;}}3RL型平衡化旋轉(zhuǎn)⑴失衡原因

在結(jié)點(diǎn)a的右孩子的左子樹(shù)上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡，與LR型正好對(duì)稱。對(duì)于結(jié)點(diǎn)a，插入前的平衡因子是-1，插入后a的平衡因子是-2。設(shè)b是a的右孩子，c為b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同樣，c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點(diǎn)。⑵插入后結(jié)點(diǎn)c的平衡因子的變化分析

①插入后c的平衡因子是1：在c的左子樹(shù)上插入。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度為HcL-1。因b插入后的平衡因子是1，則其右子樹(shù)的深度為HcL，以b為根的子樹(shù)的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹(shù)的深度是HcL。

②插入后c的平衡因子是0：c本身是插入結(jié)點(diǎn)。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度也是HcL；因b插入后的平衡因子是1，則b的右子樹(shù)的深度為HcL，以b為根的子樹(shù)的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹(shù)的深度是HcL。③插入后c的平衡因子是-1：在c的右子樹(shù)上插入。設(shè)c的左子樹(shù)的深度為HcL，則右子樹(shù)的深度為HcL+1，以c為根的子樹(shù)的深度是HcL+2；因b插入后的平衡因子是1，則b的右子樹(shù)的深度為HcL+1，以b為根的子樹(shù)的深度是HcL+3；則a的右子樹(shù)的深度是HcL+1。⑶平衡化旋轉(zhuǎn)方法

先以b進(jìn)行一次順時(shí)針旋轉(zhuǎn)，再以a進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，如圖9-9所示。即將整棵子樹(shù)(以a為根)旋轉(zhuǎn)為以c為根，a是c的左子樹(shù)，b是c的右子樹(shù)；c的右子樹(shù)移到b的左子樹(shù)位置，c的左子樹(shù)移到a的右子樹(shù)位置。圖9-9RL型平衡化旋轉(zhuǎn)示意圖abbRaLcLxcRxcbcbRaLcLxcRxa⑷旋轉(zhuǎn)后各結(jié)點(diǎn)(a,b,c)的平衡因子分析①

旋轉(zhuǎn)前

(插入后)c的平衡因子是1：

a的左子樹(shù)沒(méi)有變化，深度是HcL，右子樹(shù)是c旋轉(zhuǎn)前的左子樹(shù)，深度為HcL，則a的平衡因子是0；b的右子樹(shù)沒(méi)有變化，深度為HcL，左子樹(shù)是c旋轉(zhuǎn)前的右子樹(shù)，深度為HcL-1

，則b的平衡因子是-1；c的左、右子樹(shù)分別是以a和b為根的子樹(shù)，則c的平衡因子是0

。

②

旋轉(zhuǎn)前

(插入后)c的平衡因子是0：旋轉(zhuǎn)后a，b，c的平衡因子都是0

。

③

旋轉(zhuǎn)前

(插入后)c的平衡因子是-1：旋轉(zhuǎn)后a，b，c的平衡因子分別是1，0，0

。綜上所述，即整棵樹(shù)旋轉(zhuǎn)后是平衡的。⑸旋轉(zhuǎn)算法VoidLR_rotate(BBSTNode*a){BBSTNode*b,*c;b=a->Rchild;c=b->Lchild;/*初始化*/a->Rchild=c->Lchild;b->Lchild=c->Rchild;c->Lchild=a;c->Rchild=b;if(c->Bfactor==1){a->Bfactor=0;b->Bfactor=-1;}elseif(c->Bfactor==0)a->Bfactor=b->Bfactor=0;else{a->Bfactor=1;b->Bfactor=0;}}4

RR型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的右孩子的右子樹(shù)上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，和LL型平衡化旋轉(zhuǎn)正好對(duì)稱。⑵平衡化旋轉(zhuǎn)方法

設(shè)b是a的右孩子，通過(guò)逆時(shí)針旋轉(zhuǎn)實(shí)現(xiàn)，如圖9-10所示。用b取代a的位置，a作為b的左子樹(shù)的根結(jié)點(diǎn)，

b原來(lái)的左子樹(shù)作為a的右子樹(shù)。圖9-10RR型平衡化旋轉(zhuǎn)示意圖babLaLbRxabbLaLbRx⑶旋轉(zhuǎn)算法BBSTNode*RR_rotate(BBSTNode*a){BBSTNode*b;b=a->Rchild;a->Rchild=b->Lchild;b->Lchild=a;a->Bfactor=b->Bfactor=0;a=b;}

對(duì)于上述四種平衡化旋轉(zhuǎn)，其正確性容易由“遍歷所得中序序列不變”來(lái)證明。并且，無(wú)論是哪種情況，平衡化旋轉(zhuǎn)處理完成后，形成的新子樹(shù)仍然是平衡二叉排序樹(shù)，且其深度和插入前以a為根結(jié)點(diǎn)的平衡二叉排序樹(shù)的深度相同。所以，在平衡二叉排序樹(shù)上因插入結(jié)點(diǎn)而失衡，僅需對(duì)失衡子樹(shù)做平衡化旋轉(zhuǎn)處理。9.4.3平衡二叉排序樹(shù)的插入平衡二叉排序樹(shù)的插入操作實(shí)際上是在二叉排序插入的基礎(chǔ)上完成以下工作：⑴：判別插入結(jié)點(diǎn)后的二叉排序樹(shù)是否產(chǎn)生不平衡?⑵：找出失去平衡的最小子樹(shù)；⑶：判斷旋轉(zhuǎn)類型，然后做相應(yīng)調(diào)整。失衡的最小子樹(shù)的根結(jié)點(diǎn)a在插入前的平衡因子不為0，且是離插入結(jié)點(diǎn)最近的平衡因子不為0的結(jié)點(diǎn)的若a失衡，從a到插入點(diǎn)的路徑上的所有結(jié)點(diǎn)的平衡因子都會(huì)發(fā)生變化，在該路徑上還有一個(gè)結(jié)點(diǎn)的平衡因子不為0且該結(jié)點(diǎn)插入后沒(méi)有失衡，其平衡因子只能是由1到0或由-1到0，以該結(jié)點(diǎn)為根的子樹(shù)深度不變。該結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的平衡因子也不變，更不會(huì)失衡。1

算法思想(插入結(jié)點(diǎn)的步驟)①：按照二叉排序樹(shù)的定義，將結(jié)點(diǎn)s插入；②：在查找結(jié)點(diǎn)s的插入位置的過(guò)程中，記錄離結(jié)點(diǎn)s最近且平衡因子不為0的結(jié)點(diǎn)a，若該結(jié)點(diǎn)不存在，則結(jié)點(diǎn)a指向根結(jié)點(diǎn)；③：修改結(jié)點(diǎn)a到結(jié)點(diǎn)s路徑上所有結(jié)點(diǎn)的；④：判斷是否產(chǎn)生不平衡，若不平衡，則確定旋轉(zhuǎn)類型并做相應(yīng)調(diào)整。2

算法實(shí)現(xiàn)voidInsert_BBST(BBSTNode*T,BBSTNode*S){BBSTNode*f,*a,*b,*p,*q;if(T==NULL){T=S;T->Bfactor=1;return;}a=p=T;/*a指向離s最近且平衡因子不為0的結(jié)點(diǎn)*/f=q=NULL;/*f指向a的父結(jié)點(diǎn),q指向p父結(jié)點(diǎn)*/while(p!=NULL){if(EQ(S->key,p->key))return;if(p->Bfactor!=0){a=p;f=q;}q=p;if(LT(S->key,p->key))p=p->Lchild;elsep=p->Rchild;/*在右子樹(shù)中搜索*/}/*找插入位置*/if(LT(S->key,p->key))q->Lchild=S;/*s為左孩子*/elseq->Rchild=S;/*s插入為q的右孩子*/p=a;while(p!=S){if(LT(S->key,p->key))

{p->Bfactor++;p=p->Lchild;}else{p->Bfactor--;p=p->Rchild;}}//插入到左子樹(shù),平衡因子加1,插入到左子樹(shù),減1if(a->Bfactor>-2&&a->Bfactor<2)return;/*未失去平衡,不做調(diào)整*/if(a->Bfactor==2){b=a->Lchild;if(b->Bfactor==1)p=LL_rotate(a);elsep=LR_rotate(a);}else{b=a->Rchild;if(b->Bfactor==1)p=RL_rotate(a);elsep=RR_rotate(a);}/*修改雙親結(jié)點(diǎn)指針*/if(f==NULL)T=p;/*p為根結(jié)點(diǎn)*/elseif(f->Lchild==a)f->Lchild=p;elsef->Lchild=p;}例：設(shè)要構(gòu)造的平衡二叉樹(shù)中各結(jié)點(diǎn)的值分別是(3,14,25,81,44)，平衡二叉樹(shù)的構(gòu)造過(guò)程如圖9-11所示。3314(a)插入不超過(guò)兩個(gè)結(jié)點(diǎn)(b)插入新結(jié)點(diǎn)失衡,RR平衡旋轉(zhuǎn)31425314253142581(c)插入新結(jié)點(diǎn)未失衡(d)插入結(jié)點(diǎn)失衡,RL平衡旋轉(zhuǎn)314258144314448125圖9-11平衡二叉樹(shù)的構(gòu)造過(guò)程9.5

索引查找索引技術(shù)是組織大型數(shù)據(jù)庫(kù)的重要技術(shù)，索引結(jié)構(gòu)的基本組成是索引表和數(shù)據(jù)表兩部分，如圖9-12所示?！?/p>

數(shù)據(jù)表：存儲(chǔ)實(shí)際的數(shù)據(jù)記錄；◆索引表：存儲(chǔ)記錄的關(guān)鍵字和記錄(存儲(chǔ))地址之間的對(duì)照表，每個(gè)元素稱為一個(gè)索引項(xiàng)。索引表數(shù)據(jù)表圖9-12

索引結(jié)構(gòu)的基本形式

關(guān)鍵字存儲(chǔ)地址

263

275

386

……

1046關(guān)鍵字…

386

263

1046

…

275通過(guò)索引表可實(shí)現(xiàn)對(duì)數(shù)據(jù)表中記錄的快速查找。索引表的組織有線性結(jié)構(gòu)和樹(shù)形結(jié)構(gòu)兩種。9.5.1順序索引表是將索引項(xiàng)按順序結(jié)構(gòu)組織的線性索引表，而表中索引項(xiàng)一般是按關(guān)鍵字排序的，其特點(diǎn)是：優(yōu)點(diǎn)：◆

可以用折半查找方法快速找到關(guān)鍵字，進(jìn)而找到數(shù)據(jù)記錄的物理地址，實(shí)現(xiàn)數(shù)據(jù)記錄的快速查找；◆

提供對(duì)變長(zhǎng)數(shù)據(jù)記錄的便捷訪問(wèn)；◆

插入或刪除數(shù)據(jù)記錄時(shí)不需要移動(dòng)記錄，但需要對(duì)索引表進(jìn)行維護(hù)。缺點(diǎn)：◆

索引表中索引項(xiàng)的數(shù)目與數(shù)據(jù)表中記錄數(shù)相同，當(dāng)索引表很大時(shí)，檢索記錄需多次訪問(wèn)外存；◆

對(duì)索引表的維護(hù)代價(jià)較高，涉及到大量索引項(xiàng)的移動(dòng)，不適合于插入和刪除操作。9.5.2樹(shù)形索引表

平衡二叉排序樹(shù)便于動(dòng)態(tài)查找，因此用平衡二叉排序樹(shù)來(lái)組織索引表是一種可行的選擇。當(dāng)用于大型數(shù)據(jù)庫(kù)時(shí)，所有數(shù)據(jù)及索引都存儲(chǔ)在外存，因此，涉及到內(nèi)、外存之間頻繁的數(shù)據(jù)交換，這種交換速度的快慢成為制約動(dòng)態(tài)查找的瓶頸。若以二叉樹(shù)的結(jié)點(diǎn)作為內(nèi)、外存之間數(shù)據(jù)交換單位，則查找給定關(guān)鍵字時(shí)對(duì)磁盤平均進(jìn)行㏒2n次訪問(wèn)是不能容忍的，因此，必須選擇一種能盡可能降低磁盤I/O次數(shù)的索引組織方式。樹(shù)結(jié)點(diǎn)的大小盡可能地接近頁(yè)的大小。

R.Bayer和E.McCreight在1972年提出了一種多路平衡查找樹(shù)，稱為B_樹(shù)(其變型體是B+樹(shù))。1B_樹(shù)

B_樹(shù)主要用于文件系統(tǒng)中，在B_樹(shù)中，每個(gè)結(jié)點(diǎn)的大小為一個(gè)磁盤頁(yè)，結(jié)點(diǎn)中所包含的關(guān)鍵字及其孩子的數(shù)目取決于頁(yè)的大小。一棵度為m的B_樹(shù)稱為m階B_樹(shù)，其定義是：一棵m階B_樹(shù)，或者是空樹(shù)，或者是滿足以下性質(zhì)的m叉樹(shù)：⑴根結(jié)點(diǎn)或者是葉子，或者至少有兩棵子樹(shù)，至多有m棵子樹(shù)；⑵除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)，至多有m棵子樹(shù)；⑶所有葉子結(jié)點(diǎn)都在樹(shù)的同一層上；

⑷每個(gè)結(jié)點(diǎn)應(yīng)包含如下信息：

(n，A0，K1，A1，K2，A2，…

，Kn，An)其中Ki(1≤i≤n)是關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)；Ai(i=0，1，…

，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki，Ai所指向的子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki；n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且m/2-1≤n≤m-1，n+1為子樹(shù)的棵數(shù)。當(dāng)然，在實(shí)際應(yīng)用中每個(gè)結(jié)點(diǎn)中還應(yīng)包含n個(gè)指向每個(gè)關(guān)鍵字的記錄指針，如圖9-13是一棵包含13個(gè)關(guān)鍵字的4階B_樹(shù)。gfedcba1241151∧20∧2∧28∧31∧2∧10∧20∧1∧56∧1∧50∧1∧37∧3334853ih圖9-13一棵包含13個(gè)關(guān)鍵字的4階B_樹(shù)

根據(jù)m階B_樹(shù)的定義，結(jié)點(diǎn)的類型定義如下：#defineM5/*根據(jù)實(shí)際需要定義B_樹(shù)的階數(shù)*/typedefstructBTNode{intkeynum;/*結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)*/structBTNode*parent;/*指向父結(jié)點(diǎn)的指針*/KeyTypekey[M+1];/*關(guān)鍵字向量,key[0]未用*/structBTNode*ptr[M+1];/*子樹(shù)指針向量*/RecType*recptr[M+1];/*記錄指針向量,recptr[0]未用*/}BTNode;2B_樹(shù)的查找

由B_樹(shù)的定義可知，在其上的查找過(guò)程和二叉排序樹(shù)的查找相似。⑴算法思想①?gòu)臉?shù)的根結(jié)點(diǎn)T開(kāi)始，在T所指向的結(jié)點(diǎn)的關(guān)鍵字向量key[1…keynum]中查找給定值K(用折半查找)：若key[i]=K(1≤i≤keynum)，則查找成功，返回結(jié)點(diǎn)及關(guān)鍵字位置；否則，轉(zhuǎn)⑵；②將K與向量key[1…keynum]中的各個(gè)分量的值進(jìn)行比較，以選定查找的子樹(shù)：◆

若K<key[1]：T=T->ptr[0]；◆

若key[i]<K<key[i+1](i=1,2,…keynum-1)

T=T->ptr[i]；◆

若K>key[keynum]：T=T->ptr[keynum]；轉(zhuǎn)①，直到T是葉子結(jié)點(diǎn)且未找到相等的關(guān)鍵字，則查找失敗。⑵算法實(shí)現(xiàn)intBT_search(BTNode*T,KeyTypeK,BTNode*p)//

在B_樹(shù)中查找關(guān)鍵字K,查找成功返回在結(jié)點(diǎn)中的位置

//及結(jié)點(diǎn)指針p;否則返回0及最后一個(gè)結(jié)點(diǎn)指針{BTNode*q;intn;p=q=T;while(q!=NULL){p=q;q->key[0]=K;//設(shè)置查找哨兵for(n=q->keynum;K<q->key[n];n--)

if(n>0&&EQ(q->key[n],K))returnn;q=q->ptr[n];}return0;}⑶算法分析

在B_樹(shù)上的查找有兩中基本操作：◆

在B_樹(shù)上查找結(jié)點(diǎn)(查找算法中沒(méi)有體現(xiàn))；◆

在結(jié)點(diǎn)中查找關(guān)鍵字：在磁盤上找到指針ptr所指向的結(jié)點(diǎn)后，將結(jié)點(diǎn)信息讀入內(nèi)存后再查找。因此，磁盤上的查找次數(shù)(待查找的記錄關(guān)鍵字在B_樹(shù)上的層次數(shù))是決定B_樹(shù)查找效率的首要因素。根據(jù)m階B_樹(shù)的定義，第一層上至少有1個(gè)結(jié)點(diǎn)，第二層上至少有2個(gè)結(jié)點(diǎn)；除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)，…，第h層上至少有m/2h-2個(gè)結(jié)點(diǎn)。在這些結(jié)點(diǎn)中：根結(jié)點(diǎn)至少包含1個(gè)關(guān)鍵字，其它結(jié)點(diǎn)至少包含m/2-1個(gè)關(guān)鍵字，設(shè)s=m/2，則總的關(guān)鍵字?jǐn)?shù)目n滿足：n≧1+(s-1)∑2si=i=2h=2sh-1-1s-1sh-1-12(s-1)因此有：

h≦1+㏒s((n+1)/2)=1+㏒m/2((n+1)/2)

即在含有n個(gè)關(guān)鍵字的B_樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到待查找記錄關(guān)鍵字的結(jié)點(diǎn)的路徑上所涉及的結(jié)點(diǎn)數(shù)不超過(guò)1+㏒m/2((n+1)/2)。3B_樹(shù)的插入

B_樹(shù)的生成也是從空樹(shù)起，逐個(gè)插入關(guān)鍵字。插入時(shí)不是每插入一個(gè)關(guān)鍵字就添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)葉子結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，然后有可能“分裂”。⑴插入思想①在B_樹(shù)的中查找關(guān)鍵字K，若找到，表明關(guān)鍵字已存在，返回；否則，K的查找操作失敗于某個(gè)葉子結(jié)點(diǎn)，轉(zhuǎn)

②；②將K插入到該葉子結(jié)點(diǎn)中，插入時(shí)，若：◆

葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)<m-1：直接插入；◆

葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)=m-1：將結(jié)點(diǎn)“分裂”

。⑵結(jié)點(diǎn)“分裂”方法設(shè)待“分裂”結(jié)點(diǎn)包含信息為：

(m，A0，K1，A1，K2，A2，…

，Km，Am)，從其中間位置分為兩個(gè)結(jié)點(diǎn)：(m/2-1，A0，K1，A1，…

，Km/2-1，Am/2-1)(m-m/2，Am/2，Km/2+1，Am/2+1，…

，Km，Am)

并將中間關(guān)鍵字Km/2插入到p的父結(jié)點(diǎn)中，以分裂后的兩個(gè)結(jié)點(diǎn)作為中間關(guān)鍵字Km/2的兩個(gè)子結(jié)點(diǎn)。當(dāng)將中間關(guān)鍵字Km/2插入到p的父結(jié)點(diǎn)后，父結(jié)點(diǎn)也可能不滿足m階B_樹(shù)的要求(分枝數(shù)大于m)，則必須對(duì)父結(jié)點(diǎn)進(jìn)行“分裂”，一直進(jìn)行下去，直到?jīng)]有父結(jié)點(diǎn)或分裂后的父結(jié)點(diǎn)滿足m階B_樹(shù)的要求。當(dāng)根結(jié)點(diǎn)分裂時(shí)，因沒(méi)有父結(jié)點(diǎn)，則建立一個(gè)新的根，B_樹(shù)增高一層。例：在一個(gè)3階B_樹(shù)(2-3樹(shù))上插入結(jié)點(diǎn)，其過(guò)程如圖9-14所示。⑶算法實(shí)現(xiàn)

要實(shí)現(xiàn)插入，首先必須考慮結(jié)點(diǎn)的分裂。設(shè)待分裂的結(jié)點(diǎn)是p，分裂時(shí)先開(kāi)辟一個(gè)新結(jié)點(diǎn)，依此將結(jié)點(diǎn)p中后半部分的關(guān)鍵字和指針移到新開(kāi)辟的結(jié)點(diǎn)中。分裂之后，而需要插入到父結(jié)點(diǎn)中的關(guān)鍵字在p的關(guān)鍵字向量的p->keynum+1位置上。fhmb(a)一棵2-3樹(shù)fhmbd(b)插入d后fhmpbd分裂(c)插入p后并進(jìn)行分裂hfmbdphlfmbdp(d)插入l后分裂ghlfmbdp(e)插入g后并進(jìn)行分裂lfhmbdpp分裂圖9-14在B_樹(shù)中進(jìn)行插入的過(guò)程lfhmbdpglbdpghfm(f)繼續(xù)進(jìn)行分裂BTNode*split(BTNode*p)

/*結(jié)點(diǎn)p中包含m個(gè)關(guān)鍵字，從中分裂出一個(gè)新的結(jié)點(diǎn)*/{BTNode*q;intk,mid,j;q=(BTNode*)malloc(sizeof(BTNode));mid=(m+1)/2;q->ptr[0]=p->ptr[mid];for(j=1,k=mid+1;k<=m;k++){q->key[j]=p->key[k];

q->ptr[j++]=p->ptr[k];}/*將p的后半部分移到新結(jié)點(diǎn)q中*/q->keynum=m-mid;p->keynum=mid-1;return(q);}voidinsert_BTree(BTNode*T,KeyTypeK)

/*在B_樹(shù)T中插入關(guān)鍵字K，*/{BTNode*q,*s1=NULL,*s2=NULL;intn;if(!BT_search(T,K,p))/*樹(shù)中不存在關(guān)鍵字K*/{while(p!=NULL){p->key[0]=K;/*設(shè)置哨兵*/

for(n=p->keynum;K<p->key[n];n--){p->key[n+1]=p->key[n];p->ptr[n+1]=p->ptr[n];}/*后移關(guān)鍵字和指針*/

p->key[n]=K;p->ptr[n-1]=s1;

p->ptr[n+1]=s2;//

置關(guān)鍵字K的左右指針

if(++(p->keynum))<mbreak;

else{s2=split(p);s1=p;//分裂結(jié)點(diǎn)p

K=p->key[p->keynum+1];

p=p->parent;/*取出父結(jié)點(diǎn)*/

}

if(p==NULL)//

需要產(chǎn)生新的根結(jié)點(diǎn)

{p=(BTNode*)malloc(sizeof(BTNode));

p->keynum=1;p->key[1]=K;

p->ptr[0]=s1;p->ptr[1]=s2;

}}4B_樹(shù)的刪除

在B_樹(shù)上刪除一個(gè)關(guān)鍵字K，首先找到關(guān)鍵字所在的結(jié)點(diǎn)N，然后在N中進(jìn)行關(guān)鍵字K的刪除操作。若N不是葉子結(jié)點(diǎn)，設(shè)K是N中的第i個(gè)關(guān)鍵字，則將指針Ai-1所指子樹(shù)中的最大關(guān)鍵字(或最小關(guān)鍵字)