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

查找是為了得到某個(gè)信息而進(jìn)行的工作，也稱(chēng)檢索基本概念與術(shù)語(yǔ)靜態(tài)查找表動(dòng)態(tài)查找表哈希表查找基本概念關(guān)鍵碼關(guān)鍵碼是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它

可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。

主關(guān)鍵碼：能唯一確定一個(gè)數(shù)據(jù)元素的關(guān)鍵碼。次關(guān)鍵碼：不能唯一確定一個(gè)數(shù)據(jù)元素的關(guān)鍵碼。查找表查找表是一種以集合為邏輯結(jié)構(gòu)、以查找為核心的數(shù)據(jù)結(jié)構(gòu)。查找表的基本操作：建表、查找、讀表元、插入與刪除靜態(tài)查找表：指一經(jīng)建立就基本保持不變的查找表，

主要操作是檢索。動(dòng)態(tài)查找表：經(jīng)常需要改動(dòng)的查找表，常進(jìn)行插入刪除操作。平均查找長(zhǎng)度查找是給定一個(gè)值key，在查找表中找出關(guān)鍵碼

等于key的元素，如果找到，則查找成功；

否則查找失敗（主關(guān)鍵字）。查找效率的標(biāo)準(zhǔn)是指查找過(guò)程中和關(guān)鍵碼的平均比較次數(shù)，即平均查找長(zhǎng)度ASL，定義為：5-1線(xiàn)性表查找表結(jié)構(gòu)將數(shù)據(jù)元素組織為一個(gè)線(xiàn)性表，可以是基于數(shù)組的

順序存儲(chǔ)或以線(xiàn)性鏈表存儲(chǔ)TypedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;首先，關(guān)鍵碼類(lèi)型和數(shù)據(jù)元素類(lèi)型約定如下描述：typedefstruct{ElemType*data;intlength;}SeqTable;靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)描述如下：靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其結(jié)點(diǎn)類(lèi)型描述如下：typedefstructnode{ElemTypedata;structnode*next;}NodeType;順序查找基本思想是從查找表的一端開(kāi)始順序掃描，將查找表中

元素的關(guān)鍵碼同給定的值比較，如果相等，則查找成功；

當(dāng)掃描結(jié)束時(shí)，還未找到關(guān)鍵碼等于給定值的元素，

則查找失敗。順序查找算法結(jié)束時(shí)，返回查找成功或失敗的標(biāo)志，

若查找成功，指出找到元素的位置，否則，給出失敗信息。順序查找既適合于順序存儲(chǔ)的靜態(tài)查找表，

又適合于鏈?zhǔn)酱鎯?chǔ)的靜態(tài)查找。typedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;typedefstruct{ElemType*elem;intlength;}SeqTable;順序查找算法intS_Search(SeqTable*t,KeyTypekx){inti;t->elem[0]=kx;for(i=t->length;t->elem[i].key!=kx;i--);returni;}

intseqSearch(SeqTable*t,KeyTypekx,int*p){inti；

for(i=0；i<t->length；i++)if(t->elem[i].key==kx){*p=i；return(1)；}*p=i；

return(0)；}若找到的是第一個(gè)元素data[1]，則比較次數(shù)c1=n；若找到的是第i個(gè)元素data[i]，則比較次數(shù)ci=n-i+1；在不考慮檢索失敗的情況下，順序檢索的平均檢索長(zhǎng)度為

ASL=1*pn+2*pn-1+…+n*p1=(1+2+…+n)/n(pi=1/n)=(n+1)/2T（n)=O(n)優(yōu)點(diǎn)是算法簡(jiǎn)單且適應(yīng)面廣，無(wú)論查找表中元素是否有序均可使用。

缺點(diǎn)是平均檢索長(zhǎng)度較大，特別是當(dāng)n很大時(shí)，檢索效率較低。有序表的查找二分查找基本思想是設(shè)查找表中的元素從小到大有序，首先將

給定值key與表中間位置上元素的關(guān)鍵碼比較，如果相

等，則檢索成功；否則，若key小，則在查找表前半部

分中繼續(xù)進(jìn)行二分法查找，若key大，則在查找表后半

部分中繼續(xù)進(jìn)行二分法查找。這樣，經(jīng)過(guò)一次比較就縮

小一半的查找區(qū)間，如此進(jìn)行下去，直到檢索成功或檢

索失敗。效率較高的查找方法71418212329313538424649520123456789101112lowmidhighhighmidhighmidlowmidstatusBinSearch(SeqTablet,KeyTypekx){intlow,high,mid;intflag;low=0;high=t->length-1;while(low<=high){mid=(low+high)/2;if(kx<t->elem[mid])high=mid-1;elseif(kx>t->elem[mid])low=mid+1;else{flag=mid;break;}}returnflag;}若表中元素個(gè)數(shù)n為：有則最大檢索長(zhǎng)度為j;若則最大檢索長(zhǎng)度為j+1，所以設(shè)檢索每個(gè)元素的概率相同，則平均檢索長(zhǎng)度為：T(n)=O(log2n)插值查找類(lèi)似于查英文字典的方法，在查找一個(gè)C開(kāi)頭的

英文單詞時(shí)，從字典中間的一頁(yè)開(kāi)始，這就是

插值查找的基本思想。查找表順序存儲(chǔ)，數(shù)據(jù)元素的關(guān)鍵字在查找表中均勻分布。mid=low+kx-t.data[low].keyt.data[high].key-t.data[low].key(high-low)時(shí)間效率為T(mén)(n)=O(log2n)斐波納契查找（黃金分割法）斐波納契數(shù)列定義：設(shè)n個(gè)數(shù)據(jù)元素的有序表，且n正好是某個(gè)斐波納契數(shù)。

可用此查找方法基本思想：對(duì)于表長(zhǎng)為F(k)-1的有序表，以相對(duì)low

偏移量F(k-1)-1取中點(diǎn)，即mid=low+F(k-1)-1,對(duì)表進(jìn)

行分割，則左子表表長(zhǎng)為F(k-1)-1，右子表表長(zhǎng)為

F(k)-1-F(k-1)-1＝F(k-2)-1。

一直分割到查找成功或查找失敗。分塊查找分塊檢查找（索引順序查找），

是順序查找的一個(gè)改進(jìn)方法。索引表的整個(gè)表分成三個(gè)子表，對(duì)每個(gè)子表建立一個(gè)索引項(xiàng)，

其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)(其值為該子表內(nèi)的最大關(guān)鍵字)

和指針項(xiàng)(指示該子表的第一個(gè)記錄在表中的位置)。

索引表按關(guān)鍵字有序，表或者有序或者分塊有序。

分塊有序指的是后一個(gè)子表中所有記錄的關(guān)鍵字均

大于前一個(gè)子表中的最大關(guān)鍵字。設(shè)n個(gè)數(shù)據(jù)元素查找表分為m個(gè)子表，

分塊檢索的平均檢索長(zhǎng)度為5-2哈希表查找哈希表查找法即散列法又稱(chēng)為雜湊法或關(guān)鍵碼—地址轉(zhuǎn)換法。

用散列法表示的查找表稱(chēng)為（哈希表）散列表。

散列函數(shù)使每個(gè)關(guān)鍵碼都和結(jié)構(gòu)中存儲(chǔ)位置對(duì)應(yīng),

這樣的一個(gè)對(duì)應(yīng)關(guān)系稱(chēng)為散列(哈希Hash)函數(shù)。關(guān)鍵碼存儲(chǔ)地址h22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod11哈希表與哈希方法哈希表與哈希方法：選取某個(gè)函數(shù)，依該函數(shù)

按關(guān)鍵碼計(jì)算元素的存儲(chǔ)位置，并按此存放；

查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值kx計(jì)算地址，

將kx與地址單元中元素關(guān)鍵碼進(jìn)行比較，

確定查找是否成功。若key1≠key2，有h(key1)=h(key2)，這種現(xiàn)象稱(chēng)為沖突（碰撞）。

key1和key2稱(chēng)為同義詞。

h(key)的值域所對(duì)應(yīng)的地址空間稱(chēng)為基本區(qū)域。

發(fā)生碰撞時(shí)，同義詞可以存放在基本區(qū)域中未被占用

的單元，也可以存放到另外的區(qū)域中負(fù)載因子：

其中α>1時(shí)沖突不可避免。

(1)構(gòu)造好的哈希函數(shù)哈希方法的兩個(gè)問(wèn)題：(2)制定解決沖突的方案所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度。轉(zhuǎn)制換出來(lái)的地址要大致均勻分布，減少空間浪費(fèi)。常用的哈希函數(shù)1.直接定址法取關(guān)鍵碼的某個(gè)線(xiàn)性函數(shù)值為哈希函數(shù)。Hash(key)=a.key+b例：{100,300,500,700,800,900}1003005007008009000123456789Hash(key)=1/100*key2.除余法除余法是取關(guān)鍵碼被某個(gè)不大于散列表長(zhǎng)度m的

數(shù)P除后所得余數(shù)為散列地址。數(shù)p的選取，一般

可選P為小于基本區(qū)域長(zhǎng)度m的最大素?cái)?shù)比較好。22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod113.乘余取整法Hash(key)=取上式的整數(shù)部分作為哈希地址。a一般取值為：4.中平方法先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。例如，關(guān)鍵碼key=4731(4731)2=22382361h(key)=3825.數(shù)字分析法數(shù)字分析法是關(guān)鍵碼位數(shù)比存儲(chǔ)區(qū)的地址碼的位數(shù)多,這時(shí)可以對(duì)關(guān)鍵碼的各位進(jìn)行分析,丟掉分布不均勻的位留下均勻位作為地址。例如:對(duì)下列關(guān)鍵碼集合進(jìn)行關(guān)鍵碼到地址的轉(zhuǎn)換。關(guān)鍵碼是9位的，地址是3位的，需要經(jīng)過(guò)分析丟掉6位。

Keyh(key)0003194263260007183097090006294436430007586157150009196979970003103293296.折疊法

折疊法是將關(guān)鍵碼分割成倍數(shù)相等的幾部分，最后一部分的倍數(shù)可以短點(diǎn)，將這幾部分疊加求和，取后幾位為哈希地址。例：key=25346358705移位疊加法：將各部分的最后一位對(duì)齊相加；間界疊加法：從一端向另一端沿各部分分界來(lái)回折疊，

最后一位對(duì)齊相加。分割：25346358705253463587+051308253

364

587

50+1254Hash(key)=308Hash(key)=254例如，關(guān)鍵碼為key=582422241，要求轉(zhuǎn)換為4位的地址碼。

58|2422|241

移位折疊相加移位相加

855814224124222422110642721h1(key)=1064h2(key)=2721折疊法是將關(guān)鍵碼分割成幾部分，其中一部分的長(zhǎng)度

等于地址碼的長(zhǎng)度，再加上其余部分，舍棄進(jìn)位作為地址。++補(bǔ)充：處理沖突的方法1.開(kāi)放定址法開(kāi)放定址法解決碰撞的方法是在基本區(qū)域內(nèi)形成

一個(gè)探查序列，沿探查序列進(jìn)行檢索，直到找

到該元素或碰到一個(gè)未被占用的地址為止。

插入時(shí)，直到找到一個(gè)空單元；檢索時(shí)，

或檢索到關(guān)健碼為key的元素或檢索到達(dá)一個(gè)空單元。Hi=(Hash(key)+di)MODmi=1,2,…,k(k≤m-1)其中：m為表長(zhǎng)，di為增量序列，可有多種取法；di=1,2,3,…,m-1,di=i稱(chēng)線(xiàn)性探查序列；①線(xiàn)性探查法由線(xiàn)性探查序列,解決碰撞,稱(chēng)為線(xiàn)性探查法。關(guān)鍵碼集：{47,7,29,11,16,92,22,8,3}哈希表長(zhǎng)為11，

Hash(key)=keymod11477012345678910291116922283②二次探測(cè)法di=12,-12,22,-22,…,k2,-k2(k≤m/2)稱(chēng)為二次探查序列；801234567891016{47,7,29,11,16,92,22,8,3}477291192223③雙哈希函數(shù)探測(cè)法di=i*ReHash(key),ReHash(key)是另一個(gè)散列函數(shù)，

稱(chēng)雙散列探查序列；Hi=(Hash(key)+i*ReHash(key))MODm例如:K={18,73,10,05,68,99,27,41,51,32,25},Hash(key)=key%13，ReHash(key)=key%11+11873100123456789101112568992741513225２.拉鏈法設(shè)基本區(qū)域長(zhǎng)度為m，建立m條鏈表，將所有關(guān)鍵字

為同義詞的記錄存儲(chǔ)在同一條線(xiàn)性鏈表中。如果某

個(gè)基本區(qū)域地址中沒(méi)有存放查找表元素，則對(duì)應(yīng)的

鏈表為空鏈表；

發(fā)生沖突的同組同義詞存放在同一條鏈表中。給定元素的關(guān)鍵碼為key，首先計(jì)算出h(key)，

即確定是在第h(key)條鏈表中，

在鏈表中進(jìn)行插入及檢索操作。K={18,73,10,05,68,99,27,41,51,32,25}，h(key)=key%13{5,8,10,5,3,8,1,2,12,6,12}結(jié)點(diǎn)類(lèi)型：typedefstructNode{keytypedey;…

structNode*next;

}NodeType;哈希表：typedefNodeType*OpenHash[m];#definem…intCreateHashT(OpenHashl_t;DataType*eptr){intI;intd,finished;for(i=0;i<m;i++)l_t[i]=NULL;for(;eptr->key!=0;eptr++){d=Hash(eptr->key);finished=MovElemToHashT(eptr,l_t,d);if(!finished)break;}returnfinished;}3.建立一個(gè)公共溢出區(qū)基本表溢出表5-4動(dòng)態(tài)查找表二叉排序樹(shù)查找表采用二叉排序樹(shù)作為存儲(chǔ)結(jié)構(gòu)，既有較高的查找效率，

又具有鏈?zhǔn)酱鎯?chǔ)時(shí)元素插入、刪除操作的靈活性。二叉排序樹(shù)的定義二叉排序樹(shù)(BinarySortTree)或者是一棵空二叉樹(shù)；或者具有下列性質(zhì)的二叉樹(shù)：(1).若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

(2).若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；((3).它的左右子樹(shù)也分別為二叉排序樹(shù)。6355425890706310456783一棵二叉排序樹(shù)二叉排序樹(shù)的查找過(guò)程(1)若查找樹(shù)為空，查找失敗。(2)查找樹(shù)為非空，將給定值kx與查找樹(shù)的根結(jié)點(diǎn)關(guān)鍵碼比較；(3)若相等，查找成功，結(jié)束，否則有以下兩種情況：①當(dāng)小于根結(jié)點(diǎn)關(guān)鍵碼，查找將在左子樹(shù)上進(jìn)行，轉(zhuǎn)(1)；②當(dāng)大于根結(jié)點(diǎn)關(guān)鍵碼，查找將在右子樹(shù)上進(jìn)行，轉(zhuǎn)(1)；typedefstructNode{KeyTypekey;structNode*lchild,*rchild;}BinTNode,*BiTree;intBSTSearch(BinTNode*T,BinTNode*C,BinTNode*F,

KeyTypex)

{intflag;C=T;flag=0;while(C)

if(x>C->key){F=C;C=C->rchild;}

elseif(x<C->key){F=C;C=C->lchild;}

else{flag=1;break;}returnflag;}

二叉排序樹(shù)查找算法假設(shè)二叉排序樹(shù)共有n個(gè)結(jié)點(diǎn)，高度是h()，

算法的執(zhí)行時(shí)間代價(jià)最壞為O(h)。二叉排序樹(shù)的插入操作和構(gòu)造一棵二叉排序樹(shù)在二叉排序樹(shù)中插入新結(jié)點(diǎn)，要保證插入后仍是二叉排序樹(shù)。插入新結(jié)點(diǎn)的方法是：(1).如果二叉排序樹(shù)為空，則新結(jié)點(diǎn)為根結(jié)點(diǎn)。

(2).如果二叉排序樹(shù)為非空，則將新結(jié)點(diǎn)的關(guān)鍵碼與根結(jié)點(diǎn)的關(guān)鍵碼比較，若相等表示該結(jié)點(diǎn)已在二叉排序樹(shù)中；若小于根結(jié)點(diǎn)的關(guān)鍵碼，則將新結(jié)點(diǎn)插入到根結(jié)點(diǎn)的左子樹(shù)中；否則，插入到根結(jié)點(diǎn)的左子樹(shù)中。(3).子樹(shù)中的插入過(guò)程和樹(shù)中的插入過(guò)程相同，如此進(jìn)行下去，直到找到該結(jié)點(diǎn)，或者直到新結(jié)點(diǎn)成為葉子結(jié)點(diǎn)為止。635542589070631045678343二叉排序樹(shù)插入一個(gè)結(jié)點(diǎn)的算法IntInsertNode(BinTNode*T,KeyTypex){BinTNode*p,*q,*s;intflag=0;p=*t;if(!BSTSearch(T,q,p,x)){s=newBinTNode;s->key=kx;s->lchild=s->rchild=NULL;flag=1;if(!p)T=s;else{if(x>p->key)p->rchild=s;elsep->lchild=s;

}

}returnflag;

}

例如：已知關(guān)鍵碼集合K={18,73,10,05,68,99,27,41,51,32,25}，寫(xiě)出二叉排序樹(shù)的構(gòu)造過(guò)程1873100568992741513225StatusCreatBST(BinTNode*T){KeyTypex;T=NULL;cin>>x;while(x!=-1){InsertNode(T,x);cin>>x;}returnsuccess;}二叉排序樹(shù)的刪除操作在二叉排序樹(shù)中刪除一個(gè)指定結(jié)點(diǎn)，刪除結(jié)點(diǎn)后的二叉樹(shù)

還是一棵二叉排序樹(shù)。設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，分以下三種情況：(1)p是葉結(jié)點(diǎn)。(2)p是單分支結(jié)點(diǎn)，即只有左子樹(shù)pl或右子樹(shù)pr,

只需用子樹(shù)根結(jié)點(diǎn)代替p結(jié)點(diǎn)。

(3)p有左右子樹(shù)時(shí),按中序遍歷保持有序進(jìn)行調(diào)整。FPfpPL兩種調(diào)整方法：①直接令p結(jié)點(diǎn)的右孩子p1為f相應(yīng)的子樹(shù)，將p的

原左子樹(shù)pL作為以pr為根的子樹(shù)中序遍歷的第一

個(gè)結(jié)點(diǎn)的左子樹(shù)。②用p結(jié)點(diǎn)的直接后繼pr(或直接前驅(qū))替換p結(jié)點(diǎn)。

再用(2)方法刪去pr。FPfpPLP1P2PJPRS1S2SJSRFPpPLP1P2PJPRS1S2SJSRfPR二叉排序樹(shù)刪除算法intDeleteNode(BinTNode*T,KeyTypex)

{BinTNode*p,*q,*s,*f;intflag=0;p=T;if(BSTSearch(T,q,p,x))

if(q){if(q->lchild==NULL&&q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=NULL;elsep->rchild=NULL;}elseT=NULL;free(q);}elseif(q->lchild==NULL){if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}elseif(q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=q->lchild;elsep->rchild=q->lchild;}

elseT=q->lchild;free(q);}else{child=q->rchild;while(child->lchild)child=child->lchild;child->lchild=q->lchild;if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}returnsuccess;}returnfailure;}在二叉排序樹(shù)上查找關(guān)鍵字實(shí)際上是走了一條從根結(jié)點(diǎn)

到某個(gè)結(jié)點(diǎn)的路徑的過(guò)程，比較的次數(shù)等于路徑長(zhǎng)度加1。

因此，比較的次數(shù)不超過(guò)樹(shù)的深度。但是具有n個(gè)結(jié)點(diǎn)的

二叉樹(shù)可以有不同的形態(tài)，因此，對(duì)于不同形態(tài)的二叉

排序樹(shù)，其平均查找長(zhǎng)度也是不同的。

最壞的情況下蛻變?yōu)閱沃?shù)，此時(shí)的平均查找長(zhǎng)度為（n+1)/2。平衡二叉樹(shù)（AVL樹(shù)）平衡二叉樹(shù)的定義是一棵空樹(shù)或是具有下列性質(zhì)的二叉排序樹(shù)：

它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和

右子樹(shù)高度之差的絕對(duì)值不超過(guò)1.72418530607891426550477241853060789142非平衡二叉樹(shù)平衡二叉樹(shù)3-30000000002-2011-101平衡因子：結(jié)點(diǎn)左右子樹(shù)高度之差的數(shù)字稱(chēng)為結(jié)點(diǎn)的平衡因子在平衡二叉樹(shù)上插入或刪除結(jié)點(diǎn)后，得進(jìn)行平衡調(diào)整左單旋轉(zhuǎn)（RR型）aBhDhEhcxaBhDhEhcx27510-1BA27510-1BA73-2735100BA27051270-1BA1007341099730BA510274101000-10990-1-1-2acDhEhBhxacDhEhBhx右單旋轉(zhuǎn)（LL型）271001BA271001BA052271000BA050512701BA10005180003011251270BA1000518003010先左后右雙向旋轉(zhuǎn)（LR型）先右后左雙向旋轉(zhuǎn)（RL型）B樹(shù)和B＋樹(shù)B樹(shù)和B＋樹(shù)用于外存文件的索引。

一棵m階的B樹(shù)，或?yàn)榭諛?shù)，或是滿(mǎn)足下列特性的m叉樹(shù)：（1）樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；（2）除根之外的所有分支結(jié)點(diǎn)至少有m/2棵子樹(shù)；（3）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)；（4）有j個(gè)子女的非葉結(jié)點(diǎn)中恰好有j-1個(gè)關(guān)鍵碼，且按遞增順序排列，結(jié)點(diǎn)中包含的信息為

(p0,k1,p1,k2,…,kj-1,pj)B樹(shù)的定義其中ki(i=1,..,j-1)為關(guān)鍵碼，且ki<ki+1(i=1,…,j-2);pi(i=0,…,j-1)為指向子樹(shù)根結(jié)點(diǎn)的指針，且pi-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于ki(i=1,…,j-1),pj-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均大于kj-1,j（m/2<=j<=m-1）為關(guān)鍵碼的個(gè)數(shù)。（5）所有葉子結(jié)點(diǎn)都在同一層上，實(shí)際上這些結(jié)點(diǎn)不存在。當(dāng)m=2時(shí)，m階B樹(shù)實(shí)際上就是二叉排序樹(shù)。所以m階B樹(shù)是二叉排序樹(shù)的推廣。其查找過(guò)程和二叉排序樹(shù)類(lèi)似，它是一個(gè)沿指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵碼中進(jìn)行順序查找交叉進(jìn)行的過(guò)程。實(shí)際應(yīng)用中，m和內(nèi)外存交換的單位有關(guān)，一般，m=1024B樹(shù)主要用于文件的索引。結(jié)點(diǎn)類(lèi)型可以如下說(shuō)明：#definem 3typedefstructBTNode{int keyNum; /*關(guān)鍵字個(gè)數(shù)*/structBTNode*parent; /*指向父結(jié)點(diǎn)*/KeyType key[m+1];/*關(guān)鍵字向量*/structBTNode*ptr[m+1];/*子樹(shù)指針向量*/Record *recPtr[m+1]/*指向文件中的記錄號(hào)*/}NodeType;1、B樹(shù)的檢索keykiki+1pi

首先在根結(jié)點(diǎn)的關(guān)鍵碼集合中進(jìn)行檢索，若key==ki

，則檢索成功；否則，key一定在ki

和ki+1

之間（存在某個(gè)i），沿pi繼續(xù)查找，重復(fù)上述過(guò)程，直到檢索成功，或pi為空，檢索失敗。B樹(shù)的運(yùn)算性能分析在B樹(shù)是進(jìn)行查找包含兩種基本操作：（1）在B樹(shù)中找結(jié)點(diǎn)；（2）在結(jié)點(diǎn)中找關(guān)鍵字。由于B樹(shù)通常存儲(chǔ)在磁盤(pán)上，因此前一操作是在磁盤(pán)上進(jìn)行的，而后一操作是在內(nèi)存中進(jìn)行的，即在磁盤(pán)上找到指針p所指結(jié)點(diǎn)后，先將結(jié)點(diǎn)中信息讀入內(nèi)存，然后查詢(xún)。而在磁盤(pán)上進(jìn)行操作比在內(nèi)存中操作慢得多，因此在磁盤(pán)上進(jìn)行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點(diǎn)在B樹(shù)是的層次數(shù)，是決定B樹(shù)查找效率的關(guān)鍵因素?，F(xiàn)在考慮最壞的情況：含n個(gè)關(guān)鍵字的m階B樹(shù)的最大深度 為logm/2(n+1)/2+12.B樹(shù)的插入深度為h的m階B樹(shù)，新結(jié)點(diǎn)一般插入到h層，首先檢索到第h層，確定插入結(jié)點(diǎn)位置。（1）若被插入結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1，則插入。（2）若被插入結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1，則引起結(jié)點(diǎn)“分裂”?？扇缦聦?shí)現(xiàn)“分裂”：假設(shè)*p結(jié)點(diǎn)中含有信息為：

m,p0,(k1,p1),…,(km,pm)將*p分裂為*p和*p’兩個(gè)結(jié)點(diǎn)，分別含有信息為：*p：m/2－1,p0,(k1,p1),…(km/2－1,pm/2－1)*p’：(m-m/2,pm/2,(km/2+1,pm/2+1),…(km,pm)把關(guān)鍵字km/2和指針*p’一起插入到*p的雙親結(jié)點(diǎn)中。3.B樹(shù)的刪除在深度為h的m階B樹(shù)中刪除一個(gè)關(guān)鍵碼，首先檢索到該關(guān)鍵碼所在的結(jié)點(diǎn),然后根據(jù)不同情況進(jìn)行刪除。（1)若結(jié)點(diǎn)在第h層，且關(guān)鍵碼數(shù)目大于m/2-1，則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵碼ki。（2）若結(jié)點(diǎn)在第h層，且關(guān)鍵碼數(shù)目等于m/2-1，該結(jié)點(diǎn)左兄弟（或右兄弟）結(jié)點(diǎn)中的關(guān)鍵碼數(shù)目大于m/2－1，則需調(diào)整被刪除關(guān)鍵碼的結(jié)點(diǎn)，兄弟結(jié)點(diǎn)，以及父結(jié)點(diǎn)中的信息。方法：設(shè)父結(jié)點(diǎn)中的信息為：（p0,k1,p1,k2,p2,…,kxpx),由pi指向被刪除關(guān)鍵碼的結(jié)點(diǎn)，其的信息為：（p0,k

1,p

1,k2,p

2,…,k