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

第三節(jié)樹表的查找（二）二、B樹1、B樹的概念（1）B樹的定義一棵m（m≥3）階的B樹，或?yàn)榭諛?，或?yàn)闈M足下列性質(zhì)的m叉樹：①每個(gè)結(jié)點(diǎn)至少包含下列信息域：（n，p0，k1，p1，k2，…，kn，pn）其中，n為關(guān)鍵字的個(gè)數(shù)；ki（1≤i≤n）為關(guān)鍵字，且ki

<ki+1（1≤i≤n-1）；pi（0≤i≤n）為指向子樹根結(jié)點(diǎn)的指針，且pi所指向子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于ki+1，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ù)為樹的高度h。⑤每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)滿足：

-1≤n≤m-1。因?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)）至少有棵子樹，至多有m棵子樹。（2）實(shí)例下圖是一棵4階的B樹（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)高一層?！纠吭嚠嫵鰧㈥P(guān)鍵字序列：24，45，53，90，3，50，30，6l，12，70，100依次插入一棵初始為空的4階B樹中的過程?！菊骖}選解】（例題?簡(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ù)目不小于，則只需要該結(jié)點(diǎn)中關(guān)鍵字和相應(yīng)的指針刪除?！纠慨嫵鰟h除圖（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)的指針即可?！敬鸢浮縿h除關(guān)鍵字3后的B樹如圖（b）所示（2）若需刪除關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于－1，即關(guān)鍵字?jǐn)?shù)目已是最小值，直接刪除該關(guān)鍵字會(huì)破壞B樹的性質(zhì)。刪除這樣關(guān)鍵字分兩種情況處理：①若所刪結(jié)點(diǎn)的左(或右)鄰兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于，則將其兄弟結(jié)點(diǎn)中的最大(或最小)的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中相應(yīng)的關(guān)鍵字移至刪除關(guān)鍵字所在結(jié)點(diǎn)中?！纠慨嫵鰟h除上面（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)中?！敬鸢浮縿h除關(guān)鍵字12后的B樹如圖（c）所示②若需刪除關(guān)鍵字所在結(jié)點(diǎn)及其相鄰的左、右兄弟(或只有一個(gè)兄弟)結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目均等于－1，則按上述情況①的移動(dòng)操作就不能實(shí)現(xiàn)。此時(shí)，就需要將被刪結(jié)點(diǎn)與其左兄弟或右兄弟結(jié)點(diǎn)進(jìn)行"合并"?！纠慨嫵鰟h除上面（c）圖中的關(guān)鍵字50后的B樹。隱藏答案【解析】刪除50，需要將63和70合并，90單獨(dú)作為雙親結(jié)點(diǎn)?！敬鸢浮縿h除（c）圖中的關(guān)鍵字50后的B樹如圖（d）所示。上述情況②如果因"合并"操作引起對(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樹的高度降低一層?！敬鸢浮縿h除（d）圖中的關(guān)鍵字24后的B樹如圖（e）所示。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[0]作為中止標(biāo)志，存放給定的查找值K）為止，此時(shí)，若K=Ki且i>0，則表明查找成功，返回具有該關(guān)鍵字的結(jié)點(diǎn)的存儲(chǔ)位置及K在key[1...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ù)賦給ip->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；}elsep=p->ptr[i]；}returnNULL；}（3）實(shí)例分析【例】分析下圖所示B樹，查找18的過程先和根結(jié)點(diǎn)a比較：把K=18賦給k0。K=18小于k1的值48，再同a結(jié)點(diǎn)中k0比較，k0=K，因?yàn)閕=0，所以接著取出a結(jié)點(diǎn)的p0指向的結(jié)點(diǎn)b，用K與b結(jié)點(diǎn)中的k2=32進(jìn)行比較，k=18<k2=32，而K=18>k1=16，所以再取出b結(jié)點(diǎn)的p1所指向的結(jié)點(diǎn)e，因?yàn)閗=k1，因此查找成功，返回e結(jié)點(diǎn)的存儲(chǔ)地址以及k1的位置pos=l。當(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)的指針，且葉子結(jié)點(diǎn)本身依照關(guān)鍵字的大小從小到大順序鏈接。（3）所有非終端