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

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

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

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