大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第八章：查找-第三節(jié)-樹表的查找（二）

第三節(jié)樹表的直找(二)

二、B樹

1、B樹的概念

(1)B樹的定義

一棵m(m23)階的B樹，或?yàn)榭諛?，或?yàn)闈M足下列性質(zhì)的m叉

樹：

①每個(gè)結(jié)點(diǎn)至少包含下列信息域：

(n,po,kl,pi,k2,,kn,Pn)

其中，n為關(guān)鍵字的個(gè)數(shù)；

ki(l<i<n)為關(guān)鍵字,fiki<ki+i(l<i<n-l);

pi(0<i<n)為指向子樹根結(jié)點(diǎn)的指針，且pi所指向子樹中所有結(jié)

點(diǎn)的關(guān)鍵字均小于ki+l,Pn所指子樹中所有結(jié)點(diǎn)關(guān)鍵字均大于kn。

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

③若樹為非空，則根結(jié)點(diǎn)至少有1個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵

字。因此，若根結(jié)點(diǎn)不是葉子，則它至少有兩棵子樹。

④所有的葉結(jié)點(diǎn)都在同一層上，并且不帶信息(可以看作是外部結(jié)

點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向它們的指針均為

空)，葉子的層數(shù)為樹的高度ho

⑤每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)滿足：y2;iwnwm-l。

因?yàn)槊總€(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)正好是關(guān)鍵字總數(shù)加1,所以，除根結(jié)點(diǎn)之

外的所有非終端結(jié)點(diǎn)(非葉子結(jié)點(diǎn)的最下層的結(jié)點(diǎn)稱為終端結(jié)點(diǎn))至

少有「加2］棵子樹，至多有m棵子樹。

(2)實(shí)例

下圖是一棵4階的B樹

root'X

(3)B樹的結(jié)點(diǎn)類型定義

*definem10//m為B樹的階，結(jié)點(diǎn)中關(guān)鍵字最多可有m-1個(gè)

typedefstructnode

{intkeynum;〃結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，即結(jié)點(diǎn)

的大小

KeyTypekey[m];〃關(guān)鍵字向量，key[0]不用

struct*parent;〃指向雙親結(jié)點(diǎn)

structnode*ptr[m];〃子樹指針向量

}BTNode;

typedefBTNode*BTree;

2、B樹上的插入

在B樹中插入一個(gè)結(jié)點(diǎn)的過程：先在最低層的某個(gè)非終端結(jié)點(diǎn)中添

加一個(gè)關(guān)鍵字。若該結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不超過m-1,則插入完成，

否則要產(chǎn)生結(jié)點(diǎn)"分裂"分裂"結(jié)點(diǎn)時(shí)把結(jié)點(diǎn)分成兩個(gè)，將中間的一個(gè)

關(guān)鍵字拿出來插入到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)上，如果雙親結(jié)點(diǎn)中已有m-1

個(gè)關(guān)鍵字，則插入后將引起雙親結(jié)點(diǎn)的分裂，這一過程可能波及B樹

的根結(jié)點(diǎn)，引起根結(jié)點(diǎn)的分裂，從而使B樹長(zhǎng)高一層。

【例】試畫出將關(guān)鍵字序列：24,45,53,90,3,50,30,

61,12,70,100依次插入一棵初始為空的4階B樹中的過程。

24^45、53(a)插入90(b)插入3

(c)插入50(d)插入30(e)插入61

(f)插入12(g)插入70(h)插入100

【真題選解】

(例題?簡(jiǎn)答題)已知3階B樹如圖所示，

(1)畫出將關(guān)鍵字6插入之后的B樹；

(2)畫出在(1)所得樹中插入關(guān)鍵字2之后的B樹。

隱藏答案

3、B樹上的刪除

（1）若需刪除關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于「加2一,則只

需要該結(jié)點(diǎn)中關(guān)鍵字和相應(yīng)的指針刪除。

【例】畫出刪除圖（a）中所示3階B樹上的關(guān)鍵字3后的B樹。

隱藏答案

【解析】在3階B樹中，要?jiǎng)h除的關(guān)鍵字所在的結(jié)點(diǎn)有2個(gè)關(guān)鍵

字，直接刪除該關(guān)鍵字和相應(yīng)的指針即可。

【答案】刪除關(guān)鍵字3后的B樹如圖（b）所示

（2）若需刪除關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于一加2一一1,即

關(guān)鍵字?jǐn)?shù)目已是最小值，直接刪除該關(guān)鍵字會(huì)破壞B樹的性質(zhì)。刪除

這樣關(guān)鍵字分兩種情況處理：

①若所刪結(jié)點(diǎn)的左（或右）鄰兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于

「加2-,則將其兄弟結(jié)點(diǎn)中的最大（或最?。┑年P(guān)鍵字上移至雙親結(jié)點(diǎn)

中，而將雙親結(jié)點(diǎn)中相應(yīng)的關(guān)鍵字移至刪除關(guān)鍵字所在結(jié)點(diǎn)中。

【例】畫出刪除上面（b）圖中的關(guān)鍵字12后的B樹。

隱藏答案

【解析】直接刪除12及其指針，關(guān)鍵字24所在結(jié)點(diǎn)就變成1叉

樹，不滿足B樹的性質(zhì)，可以將關(guān)鍵字12結(jié)點(diǎn)的兄弟結(jié)點(diǎn)中的最小

值30移雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中的關(guān)鍵字24移至刪除關(guān)鍵字

12所在結(jié)點(diǎn)中。

【答案】刪除關(guān)鍵字12后的B樹如圖（c）所示

45

306390

7-24~|1回|70||100~

（c）刪除12后的B樹

②若需刪除關(guān)鍵字所在結(jié)點(diǎn)及其相鄰的左、右兄弟（或只有一個(gè)兄

弟）結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目均等于「加2二1,則按上述情況①的移動(dòng)操作就

不能實(shí)現(xiàn)。此時(shí)，就需要將被刪結(jié)點(diǎn)與其左兄弟或右兄弟結(jié)點(diǎn)進(jìn)行"合

并"。

【例】畫出刪除上面（C）圖中的關(guān)鍵字50后的B樹。

隱藏答案

【解析】刪除50,需要將63和70合并，90單獨(dú)作為雙親結(jié)點(diǎn)。

【答案】刪除（c）圖中的關(guān)鍵字50后的B樹如圖（d）所示。

（d）刪除50后的B樹

上述情況②如果因"合并”操作引起對(duì)父結(jié)點(diǎn)中關(guān)鍵字的刪除，又可

能要合并結(jié)點(diǎn)，這一過程可能波及根，引起對(duì)根結(jié)點(diǎn)中關(guān)鍵字的刪

除，從而可能使B樹的高度降低一層。

【例】畫出刪除上面(d)圖中的關(guān)鍵字24后的B樹。

隱藏答案

【解析】刪除24后，30需要37進(jìn)行合并，這樣需要45和90合

并才能滿足B樹的性質(zhì)，使B樹的高度降低一層。

【答案】刪除(d)圖中的關(guān)鍵字24后的B樹如圖(e)所示。

(e)刪除24后的B樹

4、B樹上的查找

(1)蟄找算法思想

在B樹中查找一個(gè)關(guān)鍵字等于給定值K的具體過程：若B樹為非

空，則首先取出樹根結(jié)點(diǎn)，將給定值K依次與關(guān)鍵字向量中從高下標(biāo)

端(key[keynum])開始的每個(gè)關(guān)鍵字進(jìn)行匕瞰，直到K>Ki(0<i<

n=keynum,用key⑼作為中止標(biāo)志，存放給定的查找值K)為止,

此時(shí)，若K=K且i>0,則表明查找成功,返回具有該關(guān)鍵字的結(jié)點(diǎn)的

存儲(chǔ)位置及K在key[L.keynum]中的位置;否則，其值為K的關(guān)鍵

字只可能落在當(dāng)前結(jié)點(diǎn)的pi所指向的子樹上，接著只要在該子樹上繼

續(xù)進(jìn)行查找即可。這樣，每取出一個(gè)結(jié)點(diǎn)比較后就下移一層，直到查

找成功，或被查找的子樹為空(即查找失敗)為止。

(2)算法描述

BTNode*SearchBTree(BTreeT,KeyTypeK,int*pos)

{〃從棚艮指針為T的B樹上查找關(guān)鍵字為K的對(duì)應(yīng)結(jié)點(diǎn)的存

儲(chǔ)地址及K在其中的

〃位置*pos,查找失敗返回NULL,*pos無定義

inti;

BTNode*p=T;

while(p!=NuLL)〃從根結(jié)點(diǎn)開始起依次向下一

層查找

{i=p->keynum;〃把結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)賦給i

p->key[0]=K;〃設(shè)置哨兵，順序查找

key[0...keynum]

while(K<p->key[i])〃從后向前查找第1個(gè)小于等

于K的關(guān)鍵字

i--；

if(K==key[i]&&i>0)

{*pos=i;returnp;

)

else

p=p->ptr[i];

)

returnNULL;

)

(3)實(shí)例分析

【例】分析下圖所示B樹,查找18的過程

先和根結(jié)點(diǎn)比較：把賦給小于的值再

aK=18k0oK=18kl48,

同a結(jié)點(diǎn)中kO比較，kO=K,因?yàn)閕=0,所以接著取出a結(jié)點(diǎn)的pO

指向的結(jié)點(diǎn)b,用K與b結(jié)點(diǎn)中的k2=32進(jìn)行匕麻,

k=18<k2=32,而K=18>kl=16,所以再取出b結(jié)點(diǎn)的pl所指向的

結(jié)點(diǎn)e,因?yàn)閗=kl,因此查找成功，返回e結(jié)點(diǎn)的存儲(chǔ)地址以及kl

的彳蠟

pos=lo

當(dāng)前講授

三、B+樹

B+樹是一種常用于文件組織的B樹的變形樹。一棵m階的B+樹

和m階的B樹的差異在于：

(1)有k個(gè)孩子的結(jié)點(diǎn)必含有k個(gè)關(guān)鍵字。

(2)所有的葉結(jié)點(diǎn)中包含了關(guān)鍵字的信息及指向相應(yīng)結(jié)點(diǎn)的指

針，目