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

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

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

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

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

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

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

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

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

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

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

對兩個關(guān)鍵字的比較約定為如下帶參數(shù)的宏定義：/*對數(shù)值型關(guān)鍵字*/#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))/*對字符串型關(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ù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合，各個數(shù)據(jù)元素有唯一標(biāo)識的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬于一個集合?；静僮鱌：┇}ADTStatic_SearchTable詳見p216。線性表是查找表最簡單的一種組織方式，本節(jié)介紹幾種主要的關(guān)于順序存儲結(jié)構(gòu)的查找方法。9.2.1順序查找(SequentialSearch)1查找思想

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

#defineMAX_SIZE100typedefstructSSTable{RecTypeelem[MAX_SIZE];/*順序表*/intlength;/*實際元素個數(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個元素：1……….查找第i個元素：n-i+1查找第1個元素：n查找失敗：n+12算法分析不失一般性，設(shè)查找每個記錄成功的概率相等，即Pi=1/n；查找第i個元素成功的比較次數(shù)Ci=n-i+1；◆

查找成功時的平均查找長度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ù)為n+1，若成功與不成功的概率相等，對每個記錄的查找概率為Pi=1/(2n)，則平均查找長度ASL：9.2.2

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

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

用Low、High和Mid表示待查找區(qū)間的下界、上界和中間位置指針，初值為Low=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算法實現(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算法分析①查找時每經(jīng)過一次比較，查找范圍就縮小一半，該過程可用一棵二叉樹表示：◆

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

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

分塊查找

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

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

先確定待查記錄所在塊，再在塊內(nèi)查找(順序查找)3算法實現(xiàn)typedefstructIndexType{keyTypemaxkey;/*塊中最大的關(guān)鍵字*/intstartpos;/*塊的起始位置指針*/}Index;intBlock_search(RecTypeST[],Indexind[],KeyTypekey,intn,intb)/*表長為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è)表長為n個記錄，均分為b塊，每塊記錄數(shù)為s，則b=?n/s?。設(shè)記錄的查找概率相等，每塊的查找概率為1/b，塊中記錄的查找概率為1/s，則平均查找長度ASL：ASL=Lb+Lw=∑j+j=1b∑i=i=1ss―12b+12s+1+9.2.4Fibonacci查找

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

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

大于：待查記錄在區(qū)間的前半段(區(qū)間長度為F(j-1)-1)，修改上界指針：High=Mid-1，轉(zhuǎn)⑴；③小于：待查記錄在區(qū)間的后半段(區(qū)間長度為F(j-2)-1)，修改下界指針：Low=Mid+1，轉(zhuǎn)⑴；直到越界(Low>High)，查找失敗。2算法實現(xiàn)在算法實現(xiàn)時，為了避免頻繁計算Fibonacci數(shù)，可用兩個變量f1和f2保存當(dāng)前相鄰的兩個Fibonacci數(shù)，這樣在以后的計算中可以依次遞推計算出。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)點是分割時只需進行加、減運算。9.3

動態(tài)查找

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

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

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

BST仍然可以用二叉鏈表來存儲，如圖9-4所示。圖9-4二叉排序樹1624271241518結(jié)點類型定義如下：

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

9.3.2BST樹的查找1查找思想

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

給定的K值小于BST的根結(jié)點的關(guān)鍵字：繼續(xù)在該結(jié)點的左子樹上進行查找；②給定的K值大于BST的根結(jié)點的關(guān)鍵字：繼續(xù)在該結(jié)點的右子樹上進行查找。2算法實現(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);}

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

插入思想

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

若相等：不需要插入；②若x.key<T->key：結(jié)點x插入到T的左子樹中；③若x.key>T->key：結(jié)點x插入到T的右子樹中。2算法實現(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é)點*/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é)點*/

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é)論知，對于一個無序序列可以通過構(gòu)造一棵BST樹而變成一個有序序列。由算法知，每次插入的新結(jié)點都是BST樹的葉子結(jié)點，即在插入時不必移動其它結(jié)點，僅需修改某個結(jié)點的指針。利用BST樹的插入操作，可以從空樹開始逐個插入每個結(jié)點，從而建立一棵BST樹，算法如下：#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樹的刪除

1刪除操作過程分析

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

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

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

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

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

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

p=p->Rchild;/*搜索右子樹*/}if(p==NULL)return;/*沒有要刪除的結(jié)點*/s=p;/*找到了要刪除的結(jié)點為p*/

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

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

用結(jié)點s的內(nèi)容替換結(jié)點p內(nèi)容}/*將第3種情況轉(zhuǎn)換為第2種情況*/if(s->Lchild!=NULL)//若s有左子樹，右子樹為空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平衡二叉樹(AVL)

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

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

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

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時，Nh=Fh+2-1，…而這樣，含有n個結(jié)點的平衡二叉排序樹的最大深度為h≈√5㏒φ((n+1))-2φh√5Fh≈21+√5其中φ=φh√5則Nh≈-1則在平衡二叉排序樹上進行查找的平均查找長度和㏒2n是一個數(shù)量級的，平均時間復(fù)雜度為O(㏒2n)。9.4.2平衡化旋轉(zhuǎn)

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

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

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

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

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

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

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

b的左子樹沒有變化，右子樹是以a為根的子樹，則平衡因子是：HbL-HbL=0

即b也是平衡的，以b為根的子樹的深度是HbL+1，與插入前a的子樹的深度相同，則該子樹的上層各結(jié)點的平衡因子沒有變化，即整棵樹旋轉(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é)點a的左孩子的右子樹上進行插入，插入使結(jié)點a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。設(shè)b是a的左孩子，c為b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點。⑵插入后結(jié)點c的平衡因子的變化分析

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

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

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

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

①

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

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

。

②

旋轉(zhuǎn)前

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

。

③

旋轉(zhuǎn)前

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

。綜上所述，即整棵樹旋轉(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é)點a的右孩子的左子樹上進行插入，插入使結(jié)點a失去平衡，與LR型正好對稱。對于結(jié)點a，插入前的平衡因子是-1，插入后a的平衡因子是-2。設(shè)b是a的右孩子，c為b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同樣，c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點。⑵插入后結(jié)點c的平衡因子的變化分析

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

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

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

旋轉(zhuǎn)前

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

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

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

。

②

旋轉(zhuǎn)前

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

。

③

旋轉(zhuǎn)前

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

。綜上所述，即整棵樹旋轉(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é)點a的右孩子的右子樹上進行插入，插入使結(jié)點a失去平衡。要進行一次逆時針旋轉(zhuǎn)，和LL型平衡化旋轉(zhuǎn)正好對稱。⑵平衡化旋轉(zhuǎn)方法

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

b原來的左子樹作為a的右子樹。圖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;}

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

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

算法實現(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é)點*/f=q=NULL;/*f指向a的父結(jié)點,q指向p父結(jié)點*/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;/*在右子樹中搜索*/}/*找插入位置*/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;}}//插入到左子樹,平衡因子加1,插入到左子樹,減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é)點指針*/if(f==NULL)T=p;/*p為根結(jié)點*/elseif(f->Lchild==a)f->Lchild=p;elsef->Lchild=p;}例：設(shè)要構(gòu)造的平衡二叉樹中各結(jié)點的值分別是(3,14,25,81,44)，平衡二叉樹的構(gòu)造過程如圖9-11所示。3314(a)插入不超過兩個結(jié)點(b)插入新結(jié)點失衡,RR平衡旋轉(zhuǎn)31425314253142581(c)插入新結(jié)點未失衡(d)插入結(jié)點失衡,RL平衡旋轉(zhuǎn)314258144314448125圖9-11平衡二叉樹的構(gòu)造過程9.5

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

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

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

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

263

275

386

……

1046關(guān)鍵字…

386

263

1046

…

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

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

提供對變長數(shù)據(jù)記錄的便捷訪問；◆

插入或刪除數(shù)據(jù)記錄時不需要移動記錄，但需要對索引表進行維護。缺點：◆

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

對索引表的維護代價較高，涉及到大量索引項的移動，不適合于插入和刪除操作。9.5.2樹形索引表

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

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

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

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

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

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

若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é)點且未找到相等的關(guān)鍵字，則查找失敗。⑵算法實現(xiàn)intBT_search(BTNode*T,KeyTypeK,BTNode*p)//

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

//及結(jié)點指針p;否則返回0及最后一個結(jié)點指針{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_樹上的查找有兩中基本操作：◆

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

在結(jié)點中查找關(guān)鍵字：在磁盤上找到指針ptr所指向的結(jié)點后，將結(jié)點信息讀入內(nèi)存后再查找。因此，磁盤上的查找次數(shù)(待查找的記錄關(guān)鍵字在B_樹上的層次數(shù))是決定B_樹查找效率的首要因素。根據(jù)m階B_樹的定義，第一層上至少有1個結(jié)點，第二層上至少有2個結(jié)點；除根結(jié)點外，所有非終端結(jié)點至少有m/2棵子樹，…，第h層上至少有m/2h-2個結(jié)點。在這些結(jié)點中：根結(jié)點至少包含1個關(guān)鍵字，其它結(jié)點至少包含m/2-1個關(guān)鍵字，設(shè)s=m/2，則總的關(guā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個關(guān)鍵字的B_樹上進行查找時，從根結(jié)點到待查找記錄關(guān)鍵字的結(jié)點的路徑上所涉及的結(jié)點數(shù)不超過1+㏒m/2((n+1)/2)。3B_樹的插入

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

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

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

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

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

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

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

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

/*結(jié)點p中包含m個關(guān)鍵字，從中分裂出一個新的結(jié)點*/{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é)點q中*/q->keynum=m-mid;p->keynum=mid-1;return(q);}voidinsert_BTree(BTNode*T,KeyTypeK)

/*在B_樹T中插入關(guān)鍵字K，*/{BTNode*q,*s1=NULL,*s2=NULL;intn;if(!BT_search(T,K,p))/*樹中不存在關(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é)點p

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

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

}

if(p==NULL)//

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

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

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

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

}}4B_樹的刪除

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