woaidongmao

http://blog.csdn.net/v_july_v/article/details/6735293(該博客值得深入翻閱)

 

 從B樹談到R樹之B樹的c實現

作者：weedge，July。編程藝術室出品。

前言

    代碼大全的作者Steve McConnell曾稱，他所見識的任何一本書都不是某一個人能完全獨立即能完成的。吾深以為然。

    本blog內的文章十有八九系我個人參考資料原創所作，同時十有二三系本人與吾的朋友共同創作完成。所以，諸君在瀏覽本博客內任何一篇文章時，務必尊重他人勞動成果。當然，有任何問題，歡迎隨時不吝指正。

    ok，在本blog之前的一篇文章中：從B樹、B+樹、B*樹談到R 樹，各位讀者反應熱烈。這次，咱們來編碼實現B樹的查找，插入，刪除等操作。同時此文也算作是上一篇文章從B樹談到R樹的續。望諸君不吝賜教。謝謝。

第一部分、B樹的查找，插入，刪除等具體操作

    編碼實現B樹之前，咱們先來回顧一下上文中所給出的B樹的查找，插入，刪除等具體的操作都是怎么一回事兒。明白了原理之后，再來編程實現，就相對來說有方向感了。ok，請看下文（援引自從B樹、B+樹、B*樹談到R 樹第3小節）：

B樹的插入、刪除操作

    上文第3小節簡單介紹了利用B樹這種結構如何訪問外存磁盤中的數據的情況，下面咱們通過另外一個實例來對這棵B樹的插入（insert）,刪除（delete）基本操作進行詳細的介紹。

    但在此之前，咱們還得簡單回顧下一棵m階的B 樹 (m叉樹)的特性，如下：

1. 樹中每個結點含有最多含有m個孩子，即m滿足：ceil(m/2)<=m<=m。
2. 除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；
3. 若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；
4. 所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；
5. 每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
          a)   Ki (i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki。
          b)   Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小于Ki，但都大于K(i-1)。 
          c)   除根結點之外的結點的關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1（葉子結點也必須滿足此條關于關鍵字數的性質，根結點除外）。

    ok，下面咱們以一棵5階（m=5，即除根結點和葉子結點之外的內結點最多5個孩子，最少3個孩子）B樹實例進行講。

備注：

• 關鍵字數（2-4個）針對--非根結點（包括葉子結點在內），孩子數（3-5個）--針對根結點和葉子結點之外的內結點。當然，根結點是必須至少有2個孩子的，不然就成直線型搜索樹了。
• 我說的再明白點就是，一棵5階的B樹中任何一個結點的關鍵字數是1-4，孩子樹是2-5。同時，一棵5階的B樹的最大高度應為log_ceil(m/2)N（下劃線表示以ceil(m/2)為底）。

下圖中關鍵字為大寫字母，順序為字母升序。

結點定義如下：

typedef struct{
   int Count;         // 當前節點中關鍵元素數目
   ItemType Key[4];   // 存儲關鍵字元素的數組
   long Branch[5];    // 偽指針數組，(記錄數目)方便判斷合并和分裂的情況
} NodeType;

 

1.1、插入（insert）操作

    插入一個元素時，首先在B樹中是否存在，如果不存在，即在葉子結點處結束，然后在葉子結點中插入該新的元素，注意：

• 如果葉子結點空間足夠，這里需要向右移動該葉子結點中大于新插入關鍵字的元素，
• 如果空間滿了以致沒有足夠的空間去添加新的元素，則將該結點進行“分裂”，將一半數量的關鍵字元素分裂到新的其相鄰右結點中，中間關鍵字元素上移到父結點中（當然，如果父結點空間滿了，也同樣需要“分裂”操作），而且當結點中關鍵元素向右移動了，相關的指針也需要向右移。
• 如果在根結點插入新元素，空間滿了，則進行分裂操作，這樣原來的根結點中的中間關鍵字元素向上移動到新的根結點中，因此導致樹的高度增加一層。

1、咱們通過一個實例來逐步講解下。插入以下字符字母到一棵空的B 樹中（非根結點關鍵字數小了（小于2個）就合并，大了（超過4個）就分裂）：C N G A H E K Q M F W L T Z D P R X Y S，首先，結點空間足夠，4個字母插入相同的結點中，如下圖：

 

2、當咱們試著插入H時，結點發現空間不夠，以致將其分裂成2個結點，移動中間元素G上移到新的根結點中，在實現過程中，咱們把A和C留在當前結點中，而H和N放置新的其右鄰居結點中。如下圖：

 

3、當咱們插入E,K,Q時，不需要任何分裂操作

4、插入M需要一次分裂，注意M恰好是中間關鍵字元素，以致向上移到父節點中

 

5、插入F,W,L,T不需要任何分裂操作

 

6、插入Z時，最右的葉子結點空間滿了，需要進行分裂操作，中間元素T上移到父節點中，注意通過上移中間元素，樹最終還是保持平衡，分裂結果的結點存在2個關鍵字元素。

 

7、插入D時，導致最左邊的葉子結點被分裂，D恰好也是中間元素，上移到父節點中，然后字母P,R,X,Y陸續插入不需要任何分裂操作（別忘了，樹中至多5個孩子）。

 

8、最后，當插入S時，含有N,P,Q,R的結點需要分裂，把中間元素Q上移到父節點中，但是情況來了，父節點中空間已經滿了，所以也要進行分裂，將父節點中的中間元素M上移到新形成的根結點中，注意以前在父節點中的第三個指針在修改后包括D和G節點中。這樣具體插入操作的完成，下面介紹刪除操作，刪除操作相對于插入操作要考慮的情況多點。

 

1.2、刪除(delete)操作

    首先查找B樹中需刪除的元素,如果該元素在B樹中存在，則將該元素在其結點中進行刪除，如果刪除該元素后，首先判斷該元素是否有左右孩子結點，如果有，則上移孩子結點中的某相近元素到父節點中，然后是移動之后的情況；如果沒有，直接刪除后，移動之后的情況。

    刪除元素，移動相應元素之后，

• 如果某結點中元素數目（即關鍵字數）小于ceil(m/2)-1，則需要看其某相鄰兄弟結點是否豐滿（結點中元素個數大于ceil(m/2)-1）（還記得第一節中關于B樹的第5個特性中的c點么?： c)除根結點之外的結點（包括葉子結點）的關鍵字的個數n必須滿足： （ceil(m / 2)-1）<= n <= m-1。m表示最多含有m個孩子，n表示關鍵字數。在本小節中舉的一顆B樹的示例中，關鍵字數n滿足：2<=n<=4），
• 如果豐滿，則向父節點借一個元素來滿足條件；
• 如果其相鄰兄弟都剛脫貧，即借了之后其結點數目小于ceil(m/2)-1，則該結點與其相鄰的某一兄弟結點進行“合并”成一個結點，以此來滿足條件。

    那咱們通過下面實例來詳細了解吧。

    以上述插入操作構造的一棵5階B樹（樹中最多含有m（m=5）個孩子，因此關鍵字數最小為ceil(m / 2)-1=2。還是這句話，關鍵字數小了（小于2個）就合并，大了（超過4個）就分裂）為例，依次刪除H,T,R,E。

1、首先刪除元素H，當然首先查找H，H在一個葉子結點中，且該葉子結點元素數目3大于最小元素數目ceil(m/2)-1=2，則操作很簡單，咱們只需要移動K至原來H的位置，移動L至K的位置（也就是結點中刪除元素后面的元素向前移動）

 

2、下一步，刪除T,因為T沒有在葉子結點中，而是在中間結點中找到，咱們發現他的繼承者W(字母升序的下個元素)，將W上移到T的位置，然后將原包含W的孩子結點中的W進行刪除，這里恰好刪除W后，該孩子結點中元素個數大于2，無需進行合并操作。

 

3、下一步刪除R，R在葉子結點中,但是該結點中元素數目為2，刪除導致只有1個元素，已經小于最小元素數目ceil(5/2)-1=2,而由前面我們已經知道：如果其某個相鄰兄弟結點中比較豐滿（元素個數大于ceil(5/2)-1=2），則可以向父結點借一個元素，然后將最豐滿的相鄰兄弟結點中上移最后或最前一個元素到父節點中（有沒有看到紅黑樹中左旋操作的影子?），在這個實例中，右相鄰兄弟結點中比較豐滿（3個元素大于2），所以先向父節點借一個元素W下移到該葉子結點中，代替原來S的位置，S前移；然后X在相鄰右兄弟結點中上移到父結點中，最后在相鄰右兄弟結點中刪除X，后面元素前移。

 

4、最后一步刪除E， 刪除后會導致很多問題，因為E所在的結點數目剛好達標，剛好滿足最小元素個數（ceil(5/2)-1=2）,而相鄰的兄弟結點也是同樣的情況，刪除一個元素都不能滿足條件，所以需要該節點與某相鄰兄弟結點進行合并操作；首先移動父結點中的元素（該元素在兩個需要合并的兩個結點元素之間）下移到其子結點中，然后將這兩個結點進行合并成一個結點。所以在該實例中，咱們首先將父節點中的元素D下移到已經刪除E而只有F的結點中，然后將含有D和F的結點和含有A,C的相鄰兄弟結點進行合并成一個結點。

 

5、也許你認為這樣刪除操作已經結束了，其實不然，在看看上圖，對于這種特殊情況，你立即會發現父節點只包含一個元素G，沒達標（因為非根節點包括葉子結點的關鍵字數n必須滿足于2=<n<=4，而此處的n=1），這是不能夠接受的。如果這個問題結點的相鄰兄弟比較豐滿，則可以向父結點借一個元素。假設這時右兄弟結點（含有Q,X）有一個以上的元素（Q右邊還有元素），然后咱們將M下移到元素很少的子結點中，將Q上移到M的位置，這時，Q的左子樹將變成M的右子樹，也就是含有N，P結點被依附在M的右指針上。所以在這個實例中，咱們沒有辦法去借一個元素，只能與兄弟結點進行合并成一個結點，而根結點中的唯一元素M下移到子結點，這樣，樹的高度減少一層。

 

為了進一步詳細討論刪除的情況，再舉另外一個實例：

這里是一棵不同的5序B樹，那咱們試著刪除C

 

于是將刪除元素C的右子結點中的D元素上移到C的位置，但是出現上移元素后，只有一個元素的結點的情況。

又因為含有E的結點，其相鄰兄弟結點才剛脫貧（最少元素個數為2），不可能向父節點借元素，所以只能進行合并操作，于是這里將含有A,B的左兄弟結點和含有E的結點進行合并成一個結點。

 

這樣又出現只含有一個元素F結點的情況，這時，其相鄰的兄弟結點是豐滿的（元素個數為3>最小元素個數2），這樣就可以想父結點借元素了，把父結點中的J下移到該結點中，相應的如果結點中J后有元素則前移，然后相鄰兄弟結點中的第一個元素（或者最后一個元素）上移到父節點中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的結點以前依附在M的左邊，現在變為依附在J的右邊。這樣每個結點都滿足B樹結構性質。

 

從以上操作可看出：除根結點之外的結點（包括葉子結點）的關鍵字的個數n滿足：（ceil(m / 2)-1）<= n <= m-1，即2<=n<=4。這也佐證了咱們之前的觀點。刪除操作完。

第二部分、B樹的編碼實現

    既然明白了B樹的插入，和刪除操作的原理，接下來，咱們來一步一步實現它。不過，有一點必須說明的是：這個實現只是實現了偶數序order（階)的情況；還有奇數序order（階)的情況沒有考慮。待日后改進。

• ok，以下是頭文件：

//實現對order序(階)的B-TREE結構基本操作的封裝。 //查找：search，插入：insert，刪除：remove。 //創建：create，銷毀：destory，打印：print。 #ifndef BTREE_H #define BTREE_H #ifdef __cplusplus extern "C" { #endif ////* 定義m序(階)B 樹的最小度數BTree_D=ceil(m)*/ /// 在這里定義每個節點中關鍵字的最大數目為:2 * BTree_D - 1，即序(階)：2 * BTree_D. #define BTree_D 2 #define ORDER (BTree_D * 2) //定義為4階B-tree,2-3-4樹。最簡單為3階B-tree,2-3樹。 //#define ORDER (BTree_T * 2-1) //最簡單為3階B-tree,2-3樹。 typedef int KeyType; typedef struct BTNode{ int keynum; /// 結點中關鍵字的個數，keynum <= BTree_N KeyType key[ORDER-1]; /// 關鍵字向量為key[0..keynum - 1] struct BTNode* child[ORDER]; /// 孩子指針向量為child[0..keynum] bool isLeaf; /// 是否是葉子節點的標志 }BTNode; typedef BTNode* BTree; ///定義BTree ///給定數據集data,創建BTree。 void BTree_create(BTree* tree, const KeyType* data, int length); ///銷毀BTree，釋放內存空間。 void BTree_destroy(BTree* tree); ///在BTree中插入關鍵字key。 void BTree_insert(BTree* tree, KeyType key); ///在BTree中移除關鍵字key。 void BTree_remove(BTree* tree, KeyType key); ///深度遍歷BTree打印各層結點信息。 void BTree_print(const BTree tree, int layer=1); /// 在BTree中查找關鍵字 key， /// 成功時返回找到的節點的地址及 key 在其中的位置 *pos /// 失敗時返回 NULL 及查找失敗時掃描到的節點位置 *pos BTNode* BTree_search(const BTree tree, int key, int* pos); #ifdef __cplusplus } #endif #endif

• 下面是B樹的實現文件：

//實現對order序(階)的B-TREE結構基本操作的封裝。 //查找：search，插入：insert，刪除：remove。 //創建：create，銷毀：destory，打印：print。 #include <stdlib.h> #include <stdio.h> #include <assert.h> #include "btree.h" //#define max(a, b) (((a) > (b)) ? (a) : (b)) #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比較a，b大小 #define DEBUG_BTREE // 模擬向磁盤寫入節點 void disk_write(BTNode* node) { //打印出結點中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個元素。 printf("向磁盤寫入節點"); for(int i=0;i<ORDER-1;i++){ printf("%c",node->key[i]); } printf("\n"); } // 模擬從磁盤讀取節點 void disk_read(BTNode** node) { //打印出結點中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個元素。 printf("向磁盤讀取節點"); for(int i=0;i<ORDER-1;i++){ printf("%c",(*node)->key[i]); } printf("\n"); } // 按層次打印 B 樹 void BTree_print(const BTree tree, int layer) { int i; BTNode* node = tree; if (node) { printf("第 %d 層， %d node : ", layer, node->keynum); //打印出結點中的全部元素，方便調試查看keynum之后的元素是否為0(即是否存在垃圾數據)；而不是keynum個元素。 for (i = 0; i < ORDER-1; ++i) { //for (i = 0; i < node->keynum; ++i) { printf("%c ", node->key[i]); } printf("\n"); ++layer; for (i = 0 ; i <= node->keynum; i++) { if (node->child[i]) { BTree_print(node->child[i], layer); } } } else { printf("樹為空。\n"); } } // 結點node內對關鍵字進行二分查找。 int binarySearch(BTNode* node, int low, int high, KeyType Fkey) { int mid; while (low<=high) { mid = low + (high-low)/2; if (Fkey<node->key[mid]) { high = mid-1; } if (Fkey>node->key[mid]) { low = mid+1; } if (Fkey==node->key[mid]) { return mid;//返回下標。 } } return 0;//未找到返回0. } <span style="color:#660000;"></span>//insert /*************************************************************************************** 將分裂的結點中的一半元素給新建的結點，并且將分裂結點中的中間關鍵字元素上移至父節點中。 parent 是一個非滿的父節點 node 是 tree 孩子表中下標為 index 的孩子節點，且是滿的，需分裂。 *******************************************************************/ void BTree_split_child(BTNode* parent, int index, BTNode* node) { #ifdef DEBUG_BTREE printf("BTree_split_child!\n"); #endif assert(parent && node); int i; // 創建新節點，存儲 node 中后半部分的數據 BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1); if (!newNode) { printf("Error! out of memory!\n"); return; } newNode->isLeaf = node->isLeaf; newNode->keynum = BTree_D - 1; // 拷貝 node 后半部分關鍵字,然后將node后半部分置為0。 for (i = 0; i < newNode->keynum; ++i){ newNode->key[i] = node->key[BTree_D + i]; node->key[BTree_D + i] = 0; } // 如果 node 不是葉子節點，拷貝 node 后半部分的指向孩子節點的指針，然后將node后半部分指向孩子節點的指針置為NULL。 if (!node->isLeaf) { for (i = 0; i < BTree_D; i++) { newNode->child[i] = node->child[BTree_D + i]; node->child[BTree_D + i] = NULL; } } // 將 node 分裂出 newNode 之后，里面的數據減半 node->keynum = BTree_D - 1; // 調整父節點中的指向孩子的指針和關鍵字元素。分裂時父節點增加指向孩子的指針和關鍵元素。 for (i = parent->keynum; i > index; --i) { parent->child[i + 1] = parent->child[i]; } parent->child[index + 1] = newNode; for (i = parent->keynum - 1; i >= index; --i) { parent->key[i + 1] = parent->key[i]; } parent->key[index] = node->key[BTree_D - 1]; ++parent->keynum; node->key[BTree_D - 1] = 0; // 寫入磁盤 disk_write(parent); disk_write(newNode); disk_write(node); } void BTree_insert_nonfull(BTNode* node, KeyType key) { assert(node); int i; // 節點是葉子節點，直接插入 if (node->isLeaf) { i = node->keynum - 1; while (i >= 0 && key < node->key[i]) { node->key[i + 1] = node->key[i]; --i; } node->key[i + 1] = key; ++node->keynum; // 寫入磁盤 disk_write(node); } // 節點是內部節點 else { /* 查找插入的位置*/ i = node->keynum - 1; while (i >= 0 && key < node->key[i]) { --i; } ++i; // 從磁盤讀取孩子節點 disk_read(&node->child[i]); // 如果該孩子節點已滿，分裂調整值 if (node->child[i]->keynum == (ORDER-1)) { BTree_split_child(node, i, node->child[i]); // 如果待插入的關鍵字大于該分裂結點中上移到父節點的關鍵字，在該關鍵字的右孩子結點中進行插入操作。 if (key > node->key[i]) { ++i; } } BTree_insert_nonfull(node->child[i], key); } } void BTree_insert(BTree* tree, KeyType key) { #ifdef DEBUG_BTREE printf("BTree_insert:\n"); #endif BTNode* node; BTNode* root = *tree; // 樹為空 if (NULL == root) { root = (BTNode*)calloc(sizeof(BTNode), 1); if (!root) { printf("Error! out of memory!\n"); return; } root->isLeaf = true; root->keynum = 1; root->key[0] = key; *tree = root; // 寫入磁盤 disk_write(root); return; } // 根節點已滿，插入前需要進行分裂調整 if (root->keynum == (ORDER-1)) { // 產生新節點當作根 node = (BTNode*)calloc(sizeof(BTNode), 1); if (!node) { printf("Error! out of memory!\n"); return; } *tree = node; node->isLeaf = false; node->keynum = 0; node->child[0] = root; BTree_split_child(node, 0, root); BTree_insert_nonfull(node, key); } // 根節點未滿，在當前節點中插入 key else { BTree_insert_nonfull(root, key); } } <p> </p><p>//remove  // 對 tree 中的節點 node 進行合并孩子節點處理. // 注意：孩子節點的 keynum 必須均已達到下限，即均等于 BTree_D - 1 // 將 tree 中索引為 index 的 key 下移至左孩子結點中， // 將 node 中索引為 index + 1 的孩子節點合并到索引為 index 的孩子節點中，右孩子合并到左孩子結點中。 // 并調相關的 key 和指針。</p>void BTree_merge_child(BTree* tree, BTNode* node, int index) { #ifdef DEBUG_BTREE printf("BTree_merge_child!\n"); #endif assert(tree && node && index >= 0 && index < node->keynum); int i; KeyType key = node->key[index]; BTNode* leftChild = node->child[index]; BTNode* rightChild = node->child[index + 1]; assert(leftChild && leftChild->keynum == BTree_D - 1 && rightChild && rightChild->keynum == BTree_D - 1); // 將 node中關鍵字下標為index 的 key 下移至左孩子結點中，該key所對應的右孩子結點指向node的右孩子結點中的第一個孩子。 leftChild->key[leftChild->keynum] = key; leftChild->child[leftChild->keynum + 1] = rightChild->child[0]; ++leftChild->keynum; // 右孩子的元素合并到左孩子結點中。 for (i = 0; i < rightChild->keynum; ++i) { leftChild->key[leftChild->keynum] = rightChild->key[i]; leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1]; ++leftChild->keynum; } // 在 node 中下移的 key后面的元素前移 for (i = index; i < node->keynum - 1; ++i) { node->key[i] = node->key[i + 1]; node->child[i + 1] = node->child[i + 2]; } node->key[node->keynum - 1] = 0; node->child[node->keynum] = NULL; --node->keynum; // 如果根節點沒有 key 了，并將根節點調整為合并后的左孩子節點；然后刪除釋放空間。 if (node->keynum == 0) { if (*tree == node) { *tree = leftChild; } free(node); node = NULL; } free(rightChild); rightChild = NULL; } void BTree_recursive_remove(BTree* tree, KeyType key) { // B-數的保持條件之一： // 非根節點的內部節點的關鍵字數目不能少于 BTree_D - 1 int i, j, index; BTNode *root = *tree; BTNode *node = root; if (!root) { printf("Failed to remove %c, it is not in the tree!\n", key); return; } // 結點中找key。 index = 0; while (index < node->keynum && key > node->key[index]) { ++index; } /*======================含有key的當前結點時的情況==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * key * +---+---+---+---+---+ / \ index of Child: i i+1 / \ +---+---+ +---+---+ * * * * +---+---+---+ +---+---+---+ leftChild rightChild ============================================================*/ /*一、結點中找到了關鍵字key的情況.*/ BTNode *leftChild, *rightChild; KeyType leftKey, rightKey; if (index < node->keynum && node->key[index] == key) { /* 1，所在節點是葉子節點，直接刪除*/ if (node->isLeaf) { for (i = index; i < node->keynum-1; ++i) { node->key[i] = node->key[i + 1]; //node->child[i + 1] = node->child[i + 2];葉子節點的孩子結點為空，無需移動處理。 } node->key[node->keynum-1] = 0; //node->child[node->keynum] = NULL; --node->keynum; if (node->keynum == 0) { assert(node == *tree); free(node); *tree = NULL; } return; } /*2.選擇脫貧致富的孩子結點。*/ // 2a，選擇相對富有的左孩子結點。 // 如果位于 key 前的左孩子結點的 key 數目 >= BTree_D， // 在其中找 key 的左孩子結點的最后一個元素上移至父節點key的位置。 // 然后在左孩子節點中遞歸刪除元素leftKey。 else if (node->child[index]->keynum >= BTree_D) { leftChild = node->child[index]; leftKey = leftChild->key[leftChild->keynum - 1]; node->key[index] = leftKey; BTree_recursive_remove(&leftChild, leftKey); } // 2b，選擇相對富有的右孩子結點。 // 如果位于 key 后的右孩子結點的 key 數目 >= BTree_D， // 在其中找 key 的右孩子結點的第一個元素上移至父節點key的位置 // 然后在右孩子節點中遞歸刪除元素rightKey。 else if (node->child[index + 1]->keynum >= BTree_D) { rightChild = node->child[index + 1]; rightKey = rightChild->key[0]; node->key[index] = rightKey; BTree_recursive_remove(&rightChild, rightKey); } /*左右孩子結點都剛脫貧。刪除前需要孩子結點的合并操作*/ // 2c，左右孩子結點只包含 BTree_D - 1 個節點， // 合并是將 key 下移至左孩子節點，并將右孩子節點合并到左孩子節點中， // 刪除右孩子節點，在父節點node中移除 key 和指向右孩子節點的指針， // 然后在合并了的左孩子節點中遞歸刪除元素key。 else if (node->child[index]->keynum == BTree_D - 1 && node->child[index + 1]->keynum == BTree_D - 1){ leftChild = node->child[index]; BTree_merge_child(tree, node, index); // 在合并了的左孩子節點中遞歸刪除 key BTree_recursive_remove(&leftChild, key); } } /*======================未含有key的當前結點時的情況==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * keyi * +---+---+---+---+---+ / | \ index of Child: i-1 i i+1 / | \ +---+---+ +---+---+ +---+---+ * * * * * * +---+---+---+ +---+---+---+ +---+---+---+ leftSibling Child rightSibling ============================================================*/ /*二、結點中未找到了關鍵字key的情況.*/ else { BTNode *leftSibling, *rightSibling, *child; // 3. key 不在內節點 node 中，則應當在某個包含 key 的子節點中。 // key < node->key[index], 所以 key 應當在孩子節點 node->child[index] 中 child = node->child[index]; if (!child) { printf("Failed to remove %c, it is not in the tree!\n", key); return; } /*所需查找的該孩子結點剛脫貧的情況*/ if (child->keynum == BTree_D - 1) { leftSibling = NULL; rightSibling = NULL; if (index - 1 >= 0) { leftSibling = node->child[index - 1]; } if (index + 1 <= node->keynum) { rightSibling = node->child[index + 1]; } /*選擇致富的相鄰兄弟結點。*/ // 3a，如果所在孩子節點相鄰的兄弟節點中有節點至少包含 BTree_D 個關鍵字 // 將 node 的一個關鍵字key[index]下移到 child 中，將相對富有的相鄰兄弟節點中一個關鍵字上移到 // node 中，然后在 child 孩子節點中遞歸刪除 key。 if ((leftSibling && leftSibling->keynum >= BTree_D) || (rightSibling && rightSibling->keynum >= BTree_D)) { int richR = 0; if(rightSibling) richR = 1; if(leftSibling && rightSibling) { richR = cmp(rightSibling->keynum,leftSibling->keynum); } if (rightSibling && rightSibling->keynum >= BTree_D && richR) { //相鄰右兄弟相對富有，則該孩子先向父節點借一個元素，右兄弟中的第一個元素上移至父節點所借位置，并進行相應調整。 child->key[child->keynum] = node->key[index]; child->child[child->keynum + 1] = rightSibling->child[0]; ++child->keynum; node->key[index] = rightSibling->key[0]; for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移 rightSibling->key[j] = rightSibling->key[j + 1]; rightSibling->child[j] = rightSibling->child[j + 1]; } rightSibling->key[rightSibling->keynum-1] = 0; rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum]; rightSibling->child[rightSibling->keynum] = NULL; --rightSibling->keynum; } else {//相鄰左兄弟相對富有，則該孩子向父節點借一個元素，左兄弟中的最后元素上移至父節點所借位置，并進行相應調整。 for (j = child->keynum; j > 0; --j) {//元素后移 child->key[j] = child->key[j - 1]; child->child[j + 1] = child->child[j]; } child->child[1] = child->child[0]; child->child[0] = leftSibling->child[leftSibling->keynum]; child->key[0] = node->key[index - 1]; ++child->keynum; node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1]; leftSibling->key[leftSibling->keynum - 1] = 0; leftSibling->child[leftSibling->keynum] = NULL; --leftSibling->keynum; } } /*相鄰兄弟結點都剛脫貧。刪除前需要兄弟結點的合并操作,*/ // 3b, 如果所在孩子節點相鄰的兄弟節點都只包含 BTree_D - 1 個關鍵字， // 將 child 與其一相鄰節點合并，并將 node 中的一個關鍵字下降到合并節點中， // 再在 node 中刪除那個關鍵字和相關指針，若 node 的 key 為空，刪之，并調整根為合并結點。 // 最后，在相關孩子節點child中遞歸刪除 key。 else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1)) && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) { if (leftSibling && leftSibling->keynum == BTree_D - 1) { BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。 child = leftSibling; } else if (rightSibling && rightSibling->keynum == BTree_D - 1) { BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。 } } } BTree_recursive_remove(&child, key);//調整后，在key所在孩子結點中繼續遞歸刪除key。 } } void BTree_remove(BTree* tree, KeyType key) { #ifdef DEBUG_BTREE printf("BTree_remove:\n"); #endif if (*tree==NULL) { printf("BTree is NULL!\n"); return; } BTree_recursive_remove(tree, key); } //=====================================search==================================== BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos) { int i = 0; while (i < tree->keynum && key > tree->key[i]) { ++i; } // Find the key. if (i < tree->keynum && tree->key[i] == key) { *pos = i; return tree; } // tree 為葉子節點，找不到 key，查找失敗返回 if (tree->isLeaf) { return NULL; } // 節點內查找失敗，但 tree->key[i - 1]< key < tree->key[i]， // 下一個查找的結點應為 child[i] // 從磁盤讀取第 i 個孩子的數據 disk_read(&tree->child[i]); // 遞歸地繼續查找于樹 tree->child[i] return BTree_recursive_search(tree->child[i], key, pos); } BTNode* BTree_search(const BTree tree, KeyType key, int* pos) { #ifdef DEBUG_BTREE printf("BTree_search:\n"); #endif if (!tree) { printf("BTree is NULL!\n"); return NULL; } *pos = -1; return BTree_recursive_search(tree,key,pos); } //===============================create=============================== void BTree_create(BTree* tree, const KeyType* data, int length) { assert(tree); int i; #ifdef DEBUG_BTREE printf("\n 開始創建 B-樹，關鍵字為:\n"); for (i = 0; i < length; i++) { printf(" %c ", data[i]); } printf("\n"); #endif for (i = 0; i < length; i++) { #ifdef DEBUG_BTREE printf("\n插入關鍵字 %c:\n", data[i]); #endif int pos = -1; BTree_search(*tree,data[i],&pos);//樹的遞歸搜索。 if (pos!=-1) { printf("this key %c is in the B-tree,not to insert.\n",data[i]); }else{ BTree_insert(tree, data[i]);//插入元素到BTree中。 } #ifdef DEBUG_BTREE BTree_print(*tree);//樹的深度遍歷。 #endif } printf("\n"); } //===============================destroy=============================== void BTree_destroy(BTree* tree) { int i; BTNode* node = *tree; if (node) { for (i = 0; i <= node->keynum; i++) { BTree_destroy(&node->child[i]); } free(node); } *tree = NULL; }

• 最后，給出測試文件：

//測試order序(階)的B-TREE結構基本操作。 //查找：search，插入：insert，刪除：remove。 //創建：create，銷毀：destory，打印：print。 #include <stdio.h> #include "btree.h" void test_BTree_search(BTree tree, KeyType key) { int pos = -1; BTNode* node = BTree_search(tree, key, &pos); if (node) { printf("在%s節點（包含 %d 個關鍵字）中找到關鍵字 %c，其索引為 %d\n", node->isLeaf ? "葉子" : "非葉子", node->keynum, key, pos); } else { printf("在樹中找不到關鍵字 %c\n", key); } } void test_BTree_remove(BTree* tree, KeyType key) { printf("\n移除關鍵字 %c \n", key); BTree_remove(tree, key); BTree_print(*tree); printf("\n"); } void test_btree() { KeyType array[] = { 'G','G', 'M', 'P', 'X', 'A', 'C', 'D', 'E', 'J', 'K', 'N', 'O', 'R', 'S', 'T', 'U', 'V', 'Y', 'Z', 'F', 'X' }; const int length = sizeof(array)/sizeof(KeyType); BTree tree = NULL; BTNode* node = NULL; int pos = -1; KeyType key1 = 'R'; // in the tree. KeyType key2 = 'B'; // not in the tree. // 創建 BTree_create(&tree, array, length); printf("\n=== 創建 B- 樹 ===\n"); BTree_print(tree); printf("\n"); // 查找 test_BTree_search(tree, key1); printf("\n"); test_BTree_search(tree, key2); // 移除不在B樹中的元素 test_BTree_remove(&tree, key2); printf("\n"); // 插入關鍵字 printf("\n插入關鍵字 %c \n", key2); BTree_insert(&tree, key2); BTree_print(tree); printf("\n"); test_BTree_search(tree, key2); // 移除關鍵字 test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'M'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'E'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'G'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'A'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'D'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'K'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'P'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'J'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'C'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'X'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'O'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'V'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'R'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'U'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'T'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'N'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'S'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'Y'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'F'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); key2 = 'Z'; test_BTree_remove(&tree, key2); test_BTree_search(tree, key2); // 銷毀 BTree_destroy(&tree); } int main() { test_btree(); return 0; }

參考：

• http://www.shnenglu.com/converse/archive/2009/10/13/98521.html

聯系作者：

    若有任何問題，歡迎隨時不吝指正。或者聯系我們：

• weedge，E-mail:weege@126.com
• July，zhoulei0907@yahoo.cn

后記：

    本blog日后會更多的關注數據結構與算法之外的東西，如分布式架構，海量數據處理，搜索引擎相關。畢竟，算法之外的東西，如瀚海般無止境，要學的東西，還有很多。

    若轉載，請注明出處，謝謝。完。二零一一年八月三十一日。