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

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

二、B樹

1、B樹的概念

(1)B樹的定義

一棵m(m23)階的B樹，或為空樹，或為滿足下列性質的m叉

樹：

①每個結點至少包含下列信息域：

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

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

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

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

點的關鍵字均小于ki+l,Pn所指子樹中所有結點關鍵字均大于kn。

②樹中每個結點至多有m棵子樹。

③若樹為非空，則根結點至少有1個關鍵字，至多有m-1個關鍵

字。因此，若根結點不是葉子，則它至少有兩棵子樹。

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

點或查找失敗的結點，實際上這些結點不存在，指向它們的指針均為

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

⑤每個非根結點中所包含的關鍵字個數(shù)滿足：y2;iwnwm-l。

因為每個內部結點的度數(shù)正好是關鍵字總數(shù)加1,所以，除根結點之

外的所有非終端結點(非葉子結點的最下層的結點稱為終端結點)至

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

(2)實例

下圖是一棵4階的B樹

root'X

(3)B樹的結點類型定義

*definem10//m為B樹的階，結點中關鍵字最多可有m-1個

typedefstructnode

{intkeynum;〃結點中關鍵字個數(shù)，即結點

的大小

KeyTypekey[m];〃關鍵字向量，key[0]不用

struct*parent;〃指向雙親結點

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

}BTNode;

typedefBTNode*BTree;

2、B樹上的插入

在B樹中插入一個結點的過程：先在最低層的某個非終端結點中添

加一個關鍵字。若該結點中關鍵字的個數(shù)不超過m-1,則插入完成，

否則要產生結點"分裂"分裂"結點時把結點分成兩個，將中間的一個

關鍵字拿出來插入到該結點的雙親結點上，如果雙親結點中已有m-1

個關鍵字，則插入后將引起雙親結點的分裂，這一過程可能波及B樹

的根結點，引起根結點的分裂，從而使B樹長高一層。

【例】試畫出將關鍵字序列：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

【真題選解】

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

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

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

隱藏答案

3、B樹上的刪除

（1）若需刪除關鍵字所在結點中的關鍵字數(shù)目不小于「加2一,則只

需要該結點中關鍵字和相應的指針刪除。

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

隱藏答案

【解析】在3階B樹中，要刪除的關鍵字所在的結點有2個關鍵

字，直接刪除該關鍵字和相應的指針即可。

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

（2）若需刪除關鍵字所在結點中的關鍵字數(shù)目等于一加2一一1,即

關鍵字數(shù)目已是最小值，直接刪除該關鍵字會破壞B樹的性質。刪除

這樣關鍵字分兩種情況處理：

①若所刪結點的左（或右）鄰兄弟結點中的關鍵字數(shù)目不小于

「加2-,則將其兄弟結點中的最大（或最?。┑年P鍵字上移至雙親結點

中，而將雙親結點中相應的關鍵字移至刪除關鍵字所在結點中。

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

隱藏答案

【解析】直接刪除12及其指針，關鍵字24所在結點就變成1叉

樹，不滿足B樹的性質，可以將關鍵字12結點的兄弟結點中的最小

值30移雙親結點中，而將雙親結點中的關鍵字24移至刪除關鍵字

12所在結點中。

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

45

306390

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

（c）刪除12后的B樹

②若需刪除關鍵字所在結點及其相鄰的左、右兄弟（或只有一個兄

弟）結點中關鍵字數(shù)目均等于「加2二1,則按上述情況①的移動操作就

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

并"。

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

隱藏答案

【解析】刪除50,需要將63和70合并，90單獨作為雙親結點。

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

（d）刪除50后的B樹

上述情況②如果因"合并”操作引起對父結點中關鍵字的刪除，又可

能要合并結點，這一過程可能波及根，引起對根結點中關鍵字的刪

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

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

隱藏答案

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

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

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

(e)刪除24后的B樹

4、B樹上的查找

(1)蟄找算法思想

在B樹中查找一個關鍵字等于給定值K的具體過程：若B樹為非

空，則首先取出樹根結點，將給定值K依次與關鍵字向量中從高下標

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

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

此時，若K=K且i>0,則表明查找成功,返回具有該關鍵字的結點的

存儲位置及K在key[L.keynum]中的位置;否則，其值為K的關鍵

字只可能落在當前結點的pi所指向的子樹上，接著只要在該子樹上繼

續(xù)進行查找即可。這樣，每取出一個結點比較后就下移一層，直到查

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

(2)算法描述

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

{〃從棚艮指針為T的B樹上查找關鍵字為K的對應結點的存

儲地址及K在其中的

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

inti;

BTNode*p=T;

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

層查找

{i=p->keynum;〃把結點中關鍵字個數(shù)賦給i

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

key[0...keynum]

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

于K的關鍵字

i--；

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

{*pos=i;returnp;

)

else

p=p->ptr[i];

)

returnNULL;

)

(3)實例分析

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

先和根結點比較：把賦給小于的值再

aK=18k0oK=18kl48,

同a結點中kO比較，kO=K,因為i=0,所以接著取出a結點的pO

指向的結點b,用K與b結點中的k2=32進行匕麻,

k=18<k2=32,而K=18>kl=16,所以再取出b結點的pl所指向的

結點e,因為k=kl,因此查找成功，返回e結點的存儲地址以及kl

的彳蠟

pos=lo

當前講授

三、B+樹

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

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

(1)有k個孩子的結點必含有k個關鍵字。

(2)所有的葉結點中包含了關鍵字的信息及指向相應結點的指

針，目