1 簡介

可以用階數來描述B樹, 一棵M階B樹代表著該B樹最多有M個孩子節點. 如果M為2, 那么該B樹就是一棵二叉搜索樹. 一棵M階B樹具有以下性質:

1. 每個節點最多有M - 1個關鍵字.?跟普通的樹不同, B樹的關鍵字有多個.

2. 根節點最少可以只有一個關鍵字.

3. 非根節點至少有k個關鍵字, 這里的k是指ceil(M / 2) - 1.(這里面的ceil是指大于等于參數的最小整數, 從下面插入操作分析可知, 葉子節點都是由父節點分裂而來, 而分裂的條件就是分裂前節點總數已經達到了M)

4. 每個節點中的關鍵字都按照從小到大的順序排列, 每個關鍵字在左子樹中的所有關鍵字都小于它本身的關鍵字, 右子樹的都大于它本身關鍵字.

5. 所有葉子節點都位于同一層, 或者說根節點到每個葉子節點的長度都相同.

2 插入操作

一棵M階樹的插入操作可以總結為以下步驟:

1. 根據要插入的key的值, 找到對應的葉子節點(一定要注意是葉子節點)

2. 如果被插入后的節點的key總數達到了M, 就需要對該節點, 按照key序列的中間左右分開進行分裂, 中間的key插入其父節點.

3. 對父節點進行第二步檢查.

下面以一棵5階B樹的插入操作舉例:

1. 首先插入39, 22, 97, 41:

2.? 插入39, 節點總key數量達到了5, 進行分裂:

3.? 插入13, 21:

4. 插入40, 節點分裂, 22進入父節點:

5. 插入30, 27, 33, 其中33插入后, 該節點滿, 導致其分裂, 33進入父節點:

6. 插入36, 35, 34, 其中34插入后, 該節點滿, 導致節點分裂, 36進入父節點:

7. 插入24, 29:

8. 插入26, 導致該節點滿, 分裂, 27 進入父節點, 然后父節點也滿了, 再分裂, 創建新節點:

3 刪除操作

1. 首先找到要刪除的點, 如果點不在樹中, 那么肯定刪除失敗了.

2. 如果要刪除的節點位于葉子節點, 那么拿掉這個節點, 如果位于非葉子節點上, 那么就要找到其后繼節點, 因為后繼節點肯定位于葉子節點上(因為肯定位于最左, 如果還位于非葉上面, 因其左子節點肯定存在比其大的節點, 不可能出現這種情況), 把要刪除的節點替換成后繼節點的值, 然后刪除后繼節點.

3. 因為最終刪除的點位于葉子上, 所以要觀察此時該葉節點是否滿足B樹的性質3:

非根節點至少有k個關鍵字, 這里的k是指ceil(M / 2) - 1

如果滿足, 那么結束刪除操作, 如果不滿足, 那么進行4.

4. 先觀察兄弟節點的情況:

如果兄弟節點的key數量大于k, 那么把父親節點的key下移至該節點, 并把兄弟節點的一個節點上移至父節點

否則, 將父節點中的key下移與當前節點及其兄弟節點中的key合并, 形成一個新的節點. 原父節點中的key的兩個孩子指針就變成了一個孩子指針, 指向這個新節點, 然后當前節點的指針指向父節點, 重復第3步.

舉例說明:

1. 原始狀態5階B樹, 每個非根節點的最少關鍵字數量為ceil(5 / 2) - 1 = 2:

2. 刪除21, 位于葉節點, 且刪除完成后該節點關鍵字數量為2, 結束:

3. 刪除27, 27位于非葉子節點上

3.1 首先把其值修改為后繼節點28:

3.2?刪除28, 28位于葉子節點上, 刪去:

3.3 此時該節點key數量小于2, 其左邊的兄弟節點有三個key, 可以把父節點一個key移下來, 把兄弟節點一個key移到父節點, 具體操作就是把28下移, 26上移, 完成:

4.?刪除32

4.1 首先刪除32:

4.2 該節點key數量為1, 小于2, 而兄弟節點也沒有大于2的了, 所以讓父節點中對應的key30下移與該節點和兄弟節點合并:

總結

以上是生活随笔為你收集整理的多路平衡查找树 --- B(B-)树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。