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

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

<ki+1（1≤i≤n-1）；pi（0≤i≤n）為指向子樹根結(jié)點的指針，且pi所指向子樹中所有結(jié)點的關(guān)鍵字均小于ki+1，pn所指子樹中所有結(jié)點關(guān)鍵字均大于kn。②樹中每個結(jié)點至多有m棵子樹。③若樹為非空，則根結(jié)點至少有1個關(guān)鍵字，至多有m-1個關(guān)鍵字。因此，若根結(jié)點不是葉子，則它至少有兩棵子樹。④所有的葉結(jié)點都在同一層上，并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向它們的指針均為空），葉子的層數(shù)為樹的高度h。⑤每個非根結(jié)點中所包含的關(guān)鍵字個數(shù)滿足：

-1≤n≤m-1。因為每個內(nèi)部結(jié)點的度數(shù)正好是關(guān)鍵字總數(shù)加1，所以，除根結(jié)點之外的所有非終端結(jié)點（非葉子結(jié)點的最下層的結(jié)點稱為終端結(jié)點）至少有棵子樹，至多有m棵子樹。（2）實例下圖是一棵4階的B樹（3）B樹的結(jié)點類型定義#definem10//m為B樹的階，結(jié)點中關(guān)鍵字最多可有m-1個typedefstructnode{intkeynum；//結(jié)點中關(guān)鍵字個數(shù)，即結(jié)點的大小KeyTypekey[m]；//關(guān)鍵字向量，key[0]不用struct*parent；//指向雙親結(jié)點structnode*ptr[m]；//子樹指針向量}BTNode；typedefBTNode*BTree；2、B樹上的插入在B樹中插入一個結(jié)點的過程：先在最低層的某個非終端結(jié)點中添加一個關(guān)鍵字。若該結(jié)點中關(guān)鍵字的個數(shù)不超過m-1，則插入完成，否則要產(chǎn)生結(jié)點"分裂"。"分裂"結(jié)點時把結(jié)點分成兩個，將中間的一個關(guān)鍵字拿出來插入到該結(jié)點的雙親結(jié)點上，如果雙親結(jié)點中已有m-1個關(guān)鍵字，則插入后將引起雙親結(jié)點的分裂，這一過程可能波及B樹的根結(jié)點，引起根結(jié)點的分裂，從而使B樹長高一層?！纠吭嚠嫵鰧㈥P(guān)鍵字序列：24，45，53，90，3，50，30，6l，12，70，100依次插入一棵初始為空的4階B樹中的過程?！菊骖}選解】（例題?簡答題）已知3階B樹如圖所示，（1）畫出將關(guān)鍵字6插入之后的B樹；（2）畫出在（1）所得樹中插入關(guān)鍵字2之后的B樹。隱藏答案3、B樹上的刪除（1）若需刪除關(guān)鍵字所在結(jié)點中的關(guān)鍵字?jǐn)?shù)目不小于，則只需要該結(jié)點中關(guān)鍵字和相應(yīng)的指針刪除?！纠慨嫵鰟h除圖（a）中所示3階B樹上的關(guān)鍵字3后的B樹。隱藏答案【解析】在3階B樹中，要刪除的關(guān)鍵字所在的結(jié)點有2個關(guān)鍵字，直接刪除該關(guān)鍵字和相應(yīng)的指針即可?！敬鸢浮縿h除關(guān)鍵字3后的B樹如圖（b）所示（2）若需刪除關(guān)鍵字所在結(jié)點中的關(guān)鍵字?jǐn)?shù)目等于－1，即關(guān)鍵字?jǐn)?shù)目已是最小值，直接刪除該關(guān)鍵字會破壞B樹的性質(zhì)。刪除這樣關(guān)鍵字分兩種情況處理：①若所刪結(jié)點的左(或右)鄰兄弟結(jié)點中的關(guān)鍵字?jǐn)?shù)目不小于，則將其兄弟結(jié)點中的最大(或最小)的關(guān)鍵字上移至雙親結(jié)點中，而將雙親結(jié)點中相應(yīng)的關(guān)鍵字移至刪除關(guān)鍵字所在結(jié)點中?！纠慨嫵鰟h除上面（b）圖中的關(guān)鍵字12后的B樹。隱藏答案【解析】直接刪除12及其指針，關(guān)鍵字24所在結(jié)點就變成1叉樹，不滿足B樹的性質(zhì)，可以將關(guān)鍵字12結(jié)點的兄弟結(jié)點中的最小值30移雙親結(jié)點中，而將雙親結(jié)點中的關(guān)鍵字24移至刪除關(guān)鍵字12所在結(jié)點中?！敬鸢浮縿h除關(guān)鍵字12后的B樹如圖（c）所示②若需刪除關(guān)鍵字所在結(jié)點及其相鄰的左、右兄弟(或只有一個兄弟)結(jié)點中關(guān)鍵字?jǐn)?shù)目均等于－1，則按上述情況①的移動操作就不能實現(xiàn)。此時，就需要將被刪結(jié)點與其左兄弟或右兄弟結(jié)點進行"合并"?！纠慨嫵鰟h除上面（c）圖中的關(guān)鍵字50后的B樹。隱藏答案【解析】刪除50，需要將63和70合并，90單獨作為雙親結(jié)點。【答案】刪除（c）圖中的關(guān)鍵字50后的B樹如圖（d）所示。上述情況②如果因"合并"操作引起對父結(jié)點中關(guān)鍵字的刪除，又可能要合并結(jié)點，這一過程可能波及根，引起對根結(jié)點中關(guān)鍵字的刪除，從而可能使B樹的高度降低一層?！纠慨嫵鰟h除上面（d）圖中的關(guān)鍵字24后的B樹。隱藏答案【解析】刪除24后，30需要37進行合并，這樣需要45和90合并才能滿足B樹的性質(zhì)，使B樹的高度降低一層。【答案】刪除（d）圖中的關(guān)鍵字24后的B樹如圖（e）所示。4、B樹上的查找（1）查找算法思想在B樹中查找一個關(guān)鍵字等于給定值K的具體過程：若B樹為非空，則首先取出樹根結(jié)點，將給定值K依次與關(guān)鍵字向量中從高下標(biāo)端（key[keynum]）開始的每個關(guān)鍵字進行比較，直到K≥Ki（0≤i≤n=keynum，用key[0]作為中止標(biāo)志，存放給定的查找值K）為止，此時，若K=Ki且i>0，則表明查找成功，返回具有該關(guān)鍵字的結(jié)點的存儲位置及K在key[1...keynum]中的位置；否則，其值為K的關(guān)鍵字只可能落在當(dāng)前結(jié)點的pi所指向的子樹上，接著只要在該子樹上繼續(xù)進行查找即可。這樣，每取出一個結(jié)點比較后就下移一層，直到查找成功，或被查找的子樹為空(即查找失敗)為止。（2）算法描述BTNode*SearchBTree(BTreeT，KeyTypeK，int*pos)｛//從樹根指針為T的B樹上查找關(guān)鍵字為K的對應(yīng)結(jié)點的存儲地址及K在其中的//位置*pos，查找失敗返回NULL，*pos無定義inti；BTNode*p=T；while(p!=NuLL)//從根結(jié)點開始起依次向下一層查找{i=p->keynum；//把結(jié)點中關(guān)鍵字個數(shù)賦給ip->key[0]=K；//設(shè)置哨兵，順序查找key[0…keynum]while(K<p->key[i])//從后向前查找第1個小于等于K的關(guān)鍵字i--；if(K==key[i]&&i>0){*pos=i；returnp；}elsep=p->ptr[i]；}returnNULL；}（3）實例分析【例】分析下圖所示B樹，查找18的過程先和根結(jié)點a比較：把K=18賦給k0。K=18小于k1的值48，再同a結(jié)點中k0比較，k0=K，因為i=0，所以接著取出a結(jié)點的p0指向的結(jié)點b，用K與b結(jié)點中的k2=32進行比較，k=18<k2=32，而K=18>k1=16，所以再取出b結(jié)點的p1所指向的結(jié)點e，因為k=k1，因此查找成功，返回e結(jié)點的存儲地址以及k1的位置pos=l。當(dāng)前講授三、B+樹B+樹是一種常用于文件組織的B樹的變形樹。一棵m階的B+樹和m階的B樹的差異在于：（1）有k個孩子的結(jié)點必含有k個關(guān)鍵字。（2）所有的葉結(jié)點中包含了關(guān)鍵字的信息及指向相應(yīng)結(jié)點的指針，且葉子結(jié)點本身依照關(guān)鍵字的大小從小到大順序鏈接。（3）所有非終端