[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第17次課-查找c-資料下載頁
2025-01-19 11:23本頁面
【正文】 與信息學(xué)院 姜敏 第 41頁 B樹的插入（要求保持 B樹性質(zhì)不變） B樹的生成也是從空樹起，逐個插入關(guān)鍵字而得。但由于 B樹結(jié)點(diǎn)中得關(guān)鍵字個數(shù)必須 ??m/2?1，因此，每次插入一個關(guān)鍵字不是在樹中添加一個葉子接點(diǎn)，而是首先在最低層的某個非終端結(jié)點(diǎn)中添加一個關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個數(shù) 不超過 m1， 則插入完成，否則要產(chǎn)生結(jié)點(diǎn)的 分裂 。 例： 在下面是一棵 3階的 B樹，從中插入元素 30， 26， 85。 3 12 bt 45 53 90 24 37 50 100 61 70 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 42頁 3 12 bt 45 53 90 24 30 37 50 100 61 70 插入元素 30 3 12 bt 45 53 90 24 26 30 37 50 100 61 70 插入元素 26 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 43頁 3 12 bt 45 53 90 24 30 37 50 100 61 70 插入元素 26 26 3 12 bt 45 53 90 24 30 37 50 100 61 70 85 插入元素 85 26 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 44頁 插入元素 85 bt 45 70 3 12 90 53 24 30 37 26 50 100 85 61 3 12 bt 45 53 70 90 24 37 50 100 85 61 問：此時插入關(guān)鍵字 7，如何改變樹結(jié)構(gòu)？動手練習(xí)一下！ 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 45頁 B樹的刪除 若在 B樹中刪除一個關(guān)鍵字，則首先應(yīng)找到該關(guān)鍵字所在結(jié)點(diǎn)，并叢中刪除之。 若該結(jié)點(diǎn)為 最下層的非終端結(jié)點(diǎn) ，且其中的關(guān)鍵字?jǐn)?shù)目不小于 ?m/2?，則刪除完成，否則進(jìn)行“合并”結(jié)點(diǎn)的操作。 3 12 bt 45 53 90 24 30 37 50 100 61 70 26 直接刪除元素 61 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 46頁 假若所刪除關(guān)鍵字為非終端結(jié)點(diǎn)中的 Ki， 則可以指針 Ai所指子樹中的最小關(guān)鍵字 Y替代 Ki，然后在相應(yīng)的結(jié)點(diǎn)中刪除 Y。 刪除元素 24 3 12 bt 45 53 90 24 30 37 50 100 61 70 26 3 12 bt 45 53 90 26 30 37 50 100 61 70 26 刪除終端結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 47頁 因此，下面我們可以只需討論 刪除最下層非終端結(jié)點(diǎn)中的關(guān)鍵字的情形 。有下面三種可能： 被刪除關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目 不小于 ?m/2?，則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵字 Ki和相應(yīng)指針 Ai，樹的其它部分不變。 被刪除關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目 等于 ?m/2?1，而與該結(jié)點(diǎn)相鄰的 右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于 ?m/2?1， 則只需將其右兄弟結(jié)點(diǎn)中的最?。ɑ蜃笮值芙Y(jié)點(diǎn)中的最大）的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪除關(guān)鍵字所在結(jié)點(diǎn)中。 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 48頁 3 12 bt 45 53 90 24 30 37 50 100 61 70 26 刪除終端結(jié)點(diǎn) 50 3 12 bt 45 61 90 24 30 37 53 100 70 26 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 49頁 被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于?m/2?1。若該結(jié)點(diǎn)有右兄弟，且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針 Ai所指，則在刪去關(guān)鍵字之后，它所在結(jié)點(diǎn)中剩余的關(guān)鍵字和指針，加上雙親結(jié)點(diǎn)中的關(guān)鍵字 Ki一起，合并到 Ai所指兄弟結(jié)點(diǎn)中（若沒有右兄弟，則合并到左兄弟結(jié)點(diǎn)中）。 12 bt 45 53 90 25 30 37 50 100 61 70 26 刪除終端結(jié)點(diǎn) 26 12 bt 45 53 90 25 30 37 50 100 61 70 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 50頁 ? B+樹的定義 B+樹是文件系統(tǒng)所需而出的一種 B樹的變型樹。一棵 m階的 B+樹和m階的 B樹的區(qū)別在于： 有 n棵子樹的結(jié)點(diǎn)匯總含有 n個關(guān)鍵字。 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小而大順序鏈接。 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹（根結(jié)點(diǎn)）中的最大（或最小）關(guān)鍵字。 在 B+樹上進(jìn)行隨機(jī)查找、插入和刪除的過程與 B樹基本類似，在此不做詳細(xì)的介紹。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1