《數據結構》中B—樹的刪除算法的實現(xiàn)

江克勤　吳海峰　程玉勝

摘要：B-樹是一種平衡的多路查找樹，在文件系統(tǒng)中有著很好的應用。該文分析了在B-樹中刪除一個關鍵詞的幾種情形，給出了B-樹刪除算法的具體實現(xiàn)，有助于對《數據結構》課程中B-樹操作的更好理解。

關鍵詞：查找樹；子樹；葉子結點；刪除算法；合并結點

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）16-3778-04

Abstract：B-trees are balanced search trees designed to work well on file systems. In this paper， the detailed implementation of a deleting algorithm is discussed for a few situations of deleting the key in B-trees， which contributes to a better understanding of B-trees in a data structure course.

Key words：Search tree； Subtree； Leaf node； Deleting algorithm； Merge node

1 概述

B-樹是《數據結構》課程中動態(tài)查找表的重要內容[1]，其中在B-樹上刪除一個關鍵詞是教學過程中的一個難點。大多數的《數據結構》教材中只給出了刪除關鍵詞的情況分析，并輔以簡單的示例，都沒有給出對應的B-樹刪除算法。對于一些稍復雜的關鍵詞刪除問題，我們往往不能得到準確刪除后的B-樹。該文在給出B-樹的定義后，對在B-樹中刪除一個關鍵詞的幾種情形進行分析，并給出B-樹刪除算法的具體程序實現(xiàn)，有助于大家更好地理解《數據結構》課程中B-樹的刪除過程。

2 B-樹的定義及其查找過程

2.1 B-樹的定義

B-樹是由R. Bayer和E.M. McCreight于1972年提出的一種平衡的多路查找樹[2]，它比較適合在磁盤等直接存取設備上組織動態(tài)的查找表，它是一種組織和維護外存文件系統(tǒng)非常有效的數據結構。

B-樹中所有結點的最大子樹個數稱為該B-樹的階，通常用m表示，從查找效率考慮，一般要求m≥3。一棵m階B-樹或者是一棵空樹，或者是滿足下列特性的m叉樹[3]：

1）樹中每個結點至多有m棵子樹（即至多有m-1個關鍵詞）；

2）若根結點不是葉子結點，則其至少有兩棵子樹；

3）除根結點之外的其它結點至少有[m2]棵子樹（至少有[m2-1]個關鍵詞）；

4）每個結點的結構為：（n， A0， K1， A1， K2， A2， … ， Kn， An）其中，n為該結點中關鍵詞的個數，除根結點外，其它所有結點的n滿足[m2-1≤n≤m-1]；Ki（1≤i≤n）為該結點的關鍵詞且滿足Ki

5）所有的葉子結點都出現(xiàn)在同一層上，即B-樹是所有結點的平衡因子均等于0的多路查找樹。

下面圖1所示為一棵3階的B-樹。

2.2 B-樹的存儲及查找

假設B-樹的結點類型定義如下：

#define m 3 // B-樹的階，暫設為3

typedef int KeyType； // KeyType為關鍵詞的類型

typedef struct BTNode {

int keynum； // 結點中關鍵詞個數，即結點的大小

struct BTNode *parent； // 指向雙親結點

KeyType key[m+1]； // key[1..keynum]存放關鍵詞，key[0]未用

struct BTNode *ptr[m+1]； // 子樹指針數組ptr[0..keynum]

}BTNode，*BTree； // B-樹結點和B-樹的類型

typedef struct {

BTNode *pt； // 指向找到的結點

int i； // 1..m，在結點中的關鍵詞序號

int tag； // 查找成功時為1，否則為0

}Result； // B-樹的查找結果類型

由B-樹的定義可知，在B-樹上進行查找的過程和二叉排序樹的查找類似，它是一個順著指針查找結點和在結點的關鍵詞中進行查找不斷交叉進行的過程。若在一棵B-樹上查找指定的關鍵詞x，則先將x與根1）結點中的key[i]進行比較：

2）若x=key[i]，查找成功；

3）若x

4）若key[i]

5）若k>key[n]，則沿著指針ptr[n]所指的子樹繼續(xù)查找。

對應的查找算法可參見文獻[3]，文獻[1，4]中有關于查找的一些例子。

3 B-樹的刪除算法及其實現(xiàn)

本節(jié)結合示例和算法詳細討論在B-樹上刪除關鍵詞x的過程。

首先在B-樹上查找待刪關鍵詞x所在的結點，如果查找失敗，那么表明x不在該B-樹中，無關鍵詞可刪除；如果查找成功，關鍵詞x在B-樹的結點p中，但p不是葉子結點，那么可用某葉子結點中的一個關鍵詞替代結點p中的x，假設x為p中的第i個關鍵詞（即x=p→key[i]），則替換x可以選用子樹p→ptr[i]中關鍵詞最小的，或選用子樹p→ptr[i-1]中關鍵詞最大的，這兩個關鍵詞都位于B-樹的葉子結點中，這樣刪除非葉子結點中的關鍵詞可以轉化為刪除葉子結點中的替代關鍵詞。該文采用子樹p→ptr[i]中最小關鍵詞作為替代關鍵詞，例如，要刪除圖1中的關鍵詞30，它位于根結點，選用其右子樹中最左下的葉子結點f中的關鍵詞45替換30，再刪除葉子結點f中的替代關鍵詞。

通過修改文獻[3]中的查找算法SearchBTree，在查找成功時返回替代關鍵詞的位置信息。

if （found） // 查找成功，返回刪除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p為非葉子結點，則由其后繼葉子結點q作為替代結點

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需討論刪除葉子結點p中的關鍵詞的情形，分四種情況[5]：

1）p是根結點，如果刪除之后，根結點還剩至少一個關鍵詞，那么把根結點寫盤，刪除任務完成；如果刪除之后，根結點中無關鍵詞，那么該B-樹成為空樹。

2）刪除之后p至少有[m2-1]個關鍵詞，則把結點p寫盤，刪除任務完成。

3）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點至少有[m2]個關鍵詞。先檢查p的左兄弟，若其關鍵詞數目至少為[m2]，則我們調用函數MoveRight（ ），將左兄弟中的最大關鍵詞上移至雙親結點，并將雙親結點中大于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點；若p無左兄弟，則檢查其右兄弟，調用函數MoveLeft（ ），將右兄弟中的最小關鍵詞上移至雙親結點，并將雙親結點中小于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點。例如，從圖1中刪除關鍵詞30，結果如圖2所示。

4）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點恰有[m2-1]個關鍵詞。若p有左兄弟，且其左兄弟結點地址由雙親結點中指針q→ptr[i-1]所指，則調用函數Merge（ ）把p中剩余的關鍵詞和指針，加上雙親結點中的關鍵詞q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟結點中（若沒有左兄弟，則合并至右兄弟結點中）。例如，從圖2中刪除50，結果如圖3所示。如果該合并操作使得雙親結點中的關鍵詞數目小于[m2-1]，則依次類推作相應處理。例如，從圖3中刪除關鍵詞25，結果如圖4所示。

4 結論

在B-樹上刪除一個關鍵詞是《數據結構》課程教學中的一個難點，該文分析了刪除的幾種情形，給出了B-樹刪除算法的具體程序實現(xiàn)，可以幫助大家更準確地解決B-樹中一些復雜的關鍵詞刪除問題。本程序在VC++6.0中調試通過，其中創(chuàng)建一棵m階B-樹是通過修改的查找算法SearchBTree和文獻[1]中的插入算法InsertBTree實現(xiàn)的，用括號表示法顯示B-樹的輸出，圖5是該完整程序的運行結果。

參考文獻：

[1] 嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京： 清華大學出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹為民，李蓉蓉，等. 數據結構教程[M].3版.北京： 清華大學出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲濤譯. 數據結構基礎（C語言版）[M]. 2nd ed. 北京： 清華大學出版社， 2009.endprint

通過修改文獻[3]中的查找算法SearchBTree，在查找成功時返回替代關鍵詞的位置信息。

if （found） // 查找成功，返回刪除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p為非葉子結點，則由其后繼葉子結點q作為替代結點

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需討論刪除葉子結點p中的關鍵詞的情形，分四種情況[5]：

1）p是根結點，如果刪除之后，根結點還剩至少一個關鍵詞，那么把根結點寫盤，刪除任務完成；如果刪除之后，根結點中無關鍵詞，那么該B-樹成為空樹。

2）刪除之后p至少有[m2-1]個關鍵詞，則把結點p寫盤，刪除任務完成。

3）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點至少有[m2]個關鍵詞。先檢查p的左兄弟，若其關鍵詞數目至少為[m2]，則我們調用函數MoveRight（ ），將左兄弟中的最大關鍵詞上移至雙親結點，并將雙親結點中大于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點；若p無左兄弟，則檢查其右兄弟，調用函數MoveLeft（ ），將右兄弟中的最小關鍵詞上移至雙親結點，并將雙親結點中小于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點。例如，從圖1中刪除關鍵詞30，結果如圖2所示。

4）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點恰有[m2-1]個關鍵詞。若p有左兄弟，且其左兄弟結點地址由雙親結點中指針q→ptr[i-1]所指，則調用函數Merge（ ）把p中剩余的關鍵詞和指針，加上雙親結點中的關鍵詞q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟結點中（若沒有左兄弟，則合并至右兄弟結點中）。例如，從圖2中刪除50，結果如圖3所示。如果該合并操作使得雙親結點中的關鍵詞數目小于[m2-1]，則依次類推作相應處理。例如，從圖3中刪除關鍵詞25，結果如圖4所示。

4 結論

在B-樹上刪除一個關鍵詞是《數據結構》課程教學中的一個難點，該文分析了刪除的幾種情形，給出了B-樹刪除算法的具體程序實現(xiàn)，可以幫助大家更準確地解決B-樹中一些復雜的關鍵詞刪除問題。本程序在VC++6.0中調試通過，其中創(chuàng)建一棵m階B-樹是通過修改的查找算法SearchBTree和文獻[1]中的插入算法InsertBTree實現(xiàn)的，用括號表示法顯示B-樹的輸出，圖5是該完整程序的運行結果。

參考文獻：

[1] 嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京： 清華大學出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹為民，李蓉蓉，等. 數據結構教程[M].3版.北京： 清華大學出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲濤譯. 數據結構基礎（C語言版）[M]. 2nd ed. 北京： 清華大學出版社， 2009.endprint

通過修改文獻[3]中的查找算法SearchBTree，在查找成功時返回替代關鍵詞的位置信息。

if （found） // 查找成功，返回刪除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p為非葉子結點，則由其后繼葉子結點q作為替代結點

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需討論刪除葉子結點p中的關鍵詞的情形，分四種情況[5]：

1）p是根結點，如果刪除之后，根結點還剩至少一個關鍵詞，那么把根結點寫盤，刪除任務完成；如果刪除之后，根結點中無關鍵詞，那么該B-樹成為空樹。

2）刪除之后p至少有[m2-1]個關鍵詞，則把結點p寫盤，刪除任務完成。

3）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點至少有[m2]個關鍵詞。先檢查p的左兄弟，若其關鍵詞數目至少為[m2]，則我們調用函數MoveRight（ ），將左兄弟中的最大關鍵詞上移至雙親結點，并將雙親結點中大于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點；若p無左兄弟，則檢查其右兄弟，調用函數MoveLeft（ ），將右兄弟中的最小關鍵詞上移至雙親結點，并將雙親結點中小于且緊靠該上移關鍵詞的關鍵詞下移至被刪關鍵詞所在結點。例如，從圖1中刪除關鍵詞30，結果如圖2所示。

4）刪除之后p有[m2-2]個關鍵詞，且離p最近的兄弟結點恰有[m2-1]個關鍵詞。若p有左兄弟，且其左兄弟結點地址由雙親結點中指針q→ptr[i-1]所指，則調用函數Merge（ ）把p中剩余的關鍵詞和指針，加上雙親結點中的關鍵詞q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟結點中（若沒有左兄弟，則合并至右兄弟結點中）。例如，從圖2中刪除50，結果如圖3所示。如果該合并操作使得雙親結點中的關鍵詞數目小于[m2-1]，則依次類推作相應處理。例如，從圖3中刪除關鍵詞25，結果如圖4所示。

4 結論

在B-樹上刪除一個關鍵詞是《數據結構》課程教學中的一個難點，該文分析了刪除的幾種情形，給出了B-樹刪除算法的具體程序實現(xiàn)，可以幫助大家更準確地解決B-樹中一些復雜的關鍵詞刪除問題。本程序在VC++6.0中調試通過，其中創(chuàng)建一棵m階B-樹是通過修改的查找算法SearchBTree和文獻[1]中的插入算法InsertBTree實現(xiàn)的，用括號表示法顯示B-樹的輸出，圖5是該完整程序的運行結果。

參考文獻：

[1] 嚴蔚敏，吳偉民. 數據結構（C語言版）[M]. 北京： 清華大學出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹為民，李蓉蓉，等. 數據結構教程[M].3版.北京： 清華大學出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲濤譯. 數據結構基礎（C語言版）[M]. 2nd ed. 北京： 清華大學出版社， 2009.endprint