2-3-4树和B树
比如構(gòu)造如下的2-3-4樹。
下面要刪除1和6。
刪除后如下圖所示:
下面刪除元素3
刪除元素4
下面是B樹
一個m階的B樹具有如下屬性:
如果根結(jié)點(diǎn)不是葉結(jié)點(diǎn),則其至少有兩棵子樹
每一個非根的分支結(jié)點(diǎn)都有k-1個元素(關(guān)鍵字)和k個孩子,其中k滿足:?m/2? <= k <= m
所有葉子結(jié)點(diǎn)都位于同一層次
每一個分支結(jié)點(diǎn)包含下列信息數(shù)據(jù):
n, A?, K?, A?, K?, A?, K?, A?……
其中K為關(guān)鍵字,且Ki < Ki+1
Ai為指向子樹根結(jié)點(diǎn)的指針
如下圖所示:
btree.h
//實(shí)現(xiàn)對order序(階)的B-TREE結(jié)構(gòu)基本操作的封裝。 //查找:search,插入:insert,刪除:remove。 //創(chuàng)建:create,銷毀:destory,打印:print。 #ifndef BTREE_H #define BTREE_H #ifdef __cplusplus extern "C" { #endif * 定義m序(階)B 樹的最小度數(shù)BTree_D=ceil(m)*/ /// 在這里定義每個節(jié)點(diǎn)中關(guān)鍵字的最大數(shù)目為: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; /// 結(jié)點(diǎn)中關(guān)鍵字的個數(shù),keynum <= BTree_N KeyType key[ORDER-1]; /// 關(guān)鍵字向量為key[0..keynum - 1] struct BTNode* child[ORDER]; /// 孩子指針向量為child[0..keynum] bool isLeaf; /// 是否是葉子節(jié)點(diǎn)的標(biāo)志 }BTNode; typedef BTNode* BTree; ///定義BTree ///給定數(shù)據(jù)集data,創(chuàng)建BTree。 void BTree_create(BTree* tree, const KeyType* data, int length); ///銷毀BTree,釋放內(nèi)存空間。 void BTree_destroy(BTree* tree); ///在BTree中插入關(guān)鍵字key。 void BTree_insert(BTree* tree, KeyType key); ///在BTree中移除關(guān)鍵字key。 void BTree_remove(BTree* tree, KeyType key); ///深度遍歷BTree打印各層結(jié)點(diǎn)信息。 void BTree_print(const BTree tree, int layer=1); /// 在BTree中查找關(guān)鍵字 key, /// 成功時返回找到的節(jié)點(diǎn)的地址及 key 在其中的位置 *pos /// 失敗時返回 NULL 及查找失敗時掃描到的節(jié)點(diǎn)位置 *pos BTNode* BTree_search(const BTree tree, int key, int* pos); #ifdef __cplusplus } #endif #endifbtree.c
//代碼來自(該文章有細(xì)致講解):http://blog.csdn.net/v_july_v/article/details/6735293 //實(shí)現(xiàn)對order序(階)的B-TREE結(jié)構(gòu)基本操作的封裝。 //查找:search,插入:insert,刪除:remove。 //創(chuàng)建: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 // 模擬向磁盤寫入節(jié)點(diǎn) void disk_write(BTNode* node) { //打印出結(jié)點(diǎn)中的全部元素,方便調(diào)試查看keynum之后的元素是否為0(即是否存在垃圾數(shù)據(jù));而不是keynum個元素。 printf("向磁盤寫入節(jié)點(diǎn)"); for(int i=0;i<ORDER-1;i++){ printf("%c",node->key[i]); } printf("\n"); } // 模擬從磁盤讀取節(jié)點(diǎn) void disk_read(BTNode** node) { //打印出結(jié)點(diǎn)中的全部元素,方便調(diào)試查看keynum之后的元素是否為0(即是否存在垃圾數(shù)據(jù));而不是keynum個元素。 printf("向磁盤讀取節(jié)點(diǎn)"); 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); //打印出結(jié)點(diǎn)中的全部元素,方便調(diào)試查看keynum之后的元素是否為0(即是否存在垃圾數(shù)據(jù));而不是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"); } } // 結(jié)點(diǎn)node內(nèi)對關(guān)鍵字進(jìn)行二分查找。 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;//返回下標(biāo)。 } } return 0;//未找到返回0. } //insert /*************************************************************************************** 將分裂的結(jié)點(diǎn)中的一半元素給新建的結(jié)點(diǎn),并且將分裂結(jié)點(diǎn)中的中間關(guān)鍵字元素上移至父節(jié)點(diǎn)中。 parent 是一個非滿的父節(jié)點(diǎn) node 是 tree 孩子表中下標(biāo)為 index 的孩子節(jié)點(diǎn),且是滿的,需分裂。 *******************************************************************/ void BTree_split_child(BTNode* parent, int index, BTNode* node) { #ifdef DEBUG_BTREE printf("BTree_split_child!\n"); #endif assert(parent && node); int i; // 創(chuàng)建新節(jié)點(diǎn),存儲 node 中后半部分的數(shù)據(jù) 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 后半部分關(guān)鍵字,然后將node后半部分置為0。 for (i = 0; i < newNode->keynum; ++i){ newNode->key[i] = node->key[BTree_D + i]; node->key[BTree_D + i] = 0; } // 如果 node 不是葉子節(jié)點(diǎn),拷貝 node 后半部分的指向孩子節(jié)點(diǎn)的指針,然后將node后半部分指向孩子節(jié)點(diǎn)的指針置為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 之后,里面的數(shù)據(jù)減半 node->keynum = BTree_D - 1; // 調(diào)整父節(jié)點(diǎn)中的指向孩子的指針和關(guān)鍵字元素。分裂時父節(jié)點(diǎn)增加指向孩子的指針和關(guān)鍵元素。 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; // 節(jié)點(diǎn)是葉子節(jié)點(diǎn),直接插入 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); } // 節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn) else { /* 查找插入的位置*/ i = node->keynum - 1; while (i >= 0 && key < node->key[i]) { --i; } ++i; // 從磁盤讀取孩子節(jié)點(diǎn) disk_read(&node->child[i]); // 如果該孩子節(jié)點(diǎn)已滿,分裂調(diào)整值 if (node->child[i]->keynum == (ORDER-1)) { BTree_split_child(node, i, node->child[i]); // 如果待插入的關(guān)鍵字大于該分裂結(jié)點(diǎn)中上移到父節(jié)點(diǎn)的關(guān)鍵字,在該關(guān)鍵字的右孩子結(jié)點(diǎn)中進(jìn)行插入操作。 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; } // 根節(jié)點(diǎn)已滿,插入前需要進(jìn)行分裂調(diào)整 if (root->keynum == (ORDER-1)) { // 產(chǎn)生新節(jié)點(diǎn)當(dāng)作根 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); } // 根節(jié)點(diǎn)未滿,在當(dāng)前節(jié)點(diǎn)中插入 key else { BTree_insert_nonfull(root, key); } } //remove // 對 tree 中的節(jié)點(diǎn) node 進(jìn)行合并孩子節(jié)點(diǎn)處理. // 注意:孩子節(jié)點(diǎn)的 keynum 必須均已達(dá)到下限,即均等于 BTree_D - 1 // 將 tree 中索引為 index 的 key 下移至左孩子結(jié)點(diǎn)中, // 將 node 中索引為 index + 1 的孩子節(jié)點(diǎn)合并到索引為 index 的孩子節(jié)點(diǎn)中,右孩子合并到左孩子結(jié)點(diǎn)中。 // 并調(diào)相關(guān)的 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中關(guān)鍵字下標(biāo)為index 的 key 下移至左孩子結(jié)點(diǎn)中,該key所對應(yīng)的右孩子結(jié)點(diǎn)指向node的右孩子結(jié)點(diǎn)中的第一個孩子。 leftChild->key[leftChild->keynum] = key; leftChild->child[leftChild->keynum + 1] = rightChild->child[0]; ++leftChild->keynum; // 右孩子的元素合并到左孩子結(jié)點(diǎn)中。 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; // 如果根節(jié)點(diǎn)沒有 key 了,并將根節(jié)點(diǎn)調(diào)整為合并后的左孩子節(jié)點(diǎn);然后刪除釋放空間。 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-數(shù)的保持條件之一: // 非根節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目不能少于 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; } // 結(jié)點(diǎn)中找key。 index = 0; while (index < node->keynum && key > node->key[index]) { ++index; } /*======================含有key的當(dāng)前結(jié)點(diǎn)時的情況==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * key * +---+---+---+---+---+ / \ index of Child: i i+1 / \ +---+---+ +---+---+ * * * * +---+---+---+ +---+---+---+ leftChild rightChild ============================================================*/ /*一、結(jié)點(diǎn)中找到了關(guān)鍵字key的情況.*/ BTNode *leftChild, *rightChild; KeyType leftKey, rightKey; if (index < node->keynum && node->key[index] == key) { /* 1,所在節(jié)點(diǎn)是葉子節(jié)點(diǎn),直接刪除*/ 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];葉子節(jié)點(diǎn)的孩子結(jié)點(diǎn)為空,無需移動處理。 } 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.選擇脫貧致富的孩子結(jié)點(diǎn)。*/ // 2a,選擇相對富有的左孩子結(jié)點(diǎn)。 // 如果位于 key 前的左孩子結(jié)點(diǎn)的 key 數(shù)目 >= BTree_D, // 在其中找 key 的左孩子結(jié)點(diǎn)的最后一個元素上移至父節(jié)點(diǎn)key的位置。 // 然后在左孩子節(jié)點(diǎn)中遞歸刪除元素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,選擇相對富有的右孩子結(jié)點(diǎn)。 // 如果位于 key 后的右孩子結(jié)點(diǎn)的 key 數(shù)目 >= BTree_D, // 在其中找 key 的右孩子結(jié)點(diǎn)的第一個元素上移至父節(jié)點(diǎn)key的位置 // 然后在右孩子節(jié)點(diǎn)中遞歸刪除元素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); } /*左右孩子結(jié)點(diǎn)都剛脫貧。刪除前需要孩子結(jié)點(diǎn)的合并操作*/ // 2c,左右孩子結(jié)點(diǎn)只包含 BTree_D - 1 個節(jié)點(diǎn), // 合并是將 key 下移至左孩子節(jié)點(diǎn),并將右孩子節(jié)點(diǎn)合并到左孩子節(jié)點(diǎn)中, // 刪除右孩子節(jié)點(diǎn),在父節(jié)點(diǎn)node中移除 key 和指向右孩子節(jié)點(diǎn)的指針, // 然后在合并了的左孩子節(jié)點(diǎn)中遞歸刪除元素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); // 在合并了的左孩子節(jié)點(diǎn)中遞歸刪除 key BTree_recursive_remove(&leftChild, key); } } /*======================未含有key的當(dāng)前結(jié)點(diǎn)時的情況==================== node: index of Key: i-1 i i+1 +---+---+---+---+ * keyi * +---+---+---+---+---+ / | \ index of Child: i-1 i i+1 / | \ +---+---+ +---+---+ +---+---+ * * * * * * +---+---+---+ +---+---+---+ +---+---+---+ leftSibling Child rightSibling ============================================================*/ /*二、結(jié)點(diǎn)中未找到了關(guān)鍵字key的情況.*/ else { BTNode *leftSibling, *rightSibling, *child; // 3. key 不在內(nèi)節(jié)點(diǎn) node 中,則應(yīng)當(dāng)在某個包含 key 的子節(jié)點(diǎn)中。 // key < node->key[index], 所以 key 應(yīng)當(dāng)在孩子節(jié)點(diǎn) node->child[index] 中 child = node->child[index]; if (!child) { printf("Failed to remove %c, it is not in the tree!\n", key); return; } /*所需查找的該孩子結(jié)點(diǎn)剛脫貧的情況*/ 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]; } /*選擇致富的相鄰兄弟結(jié)點(diǎn)。*/ // 3a,如果所在孩子節(jié)點(diǎn)相鄰的兄弟節(jié)點(diǎn)中有節(jié)點(diǎn)至少包含 BTree_D 個關(guān)鍵字 // 將 node 的一個關(guān)鍵字key[index]下移到 child 中,將相對富有的相鄰兄弟節(jié)點(diǎn)中一個關(guān)鍵字上移到 // node 中,然后在 child 孩子節(jié)點(diǎn)中遞歸刪除 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) { //相鄰右兄弟相對富有,則該孩子先向父節(jié)點(diǎn)借一個元素,右兄弟中的第一個元素上移至父節(jié)點(diǎn)所借位置,并進(jìn)行相應(yīng)調(diào)整。 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 {//相鄰左兄弟相對富有,則該孩子向父節(jié)點(diǎn)借一個元素,左兄弟中的最后元素上移至父節(jié)點(diǎn)所借位置,并進(jìn)行相應(yīng)調(diào)整。 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; } } /*相鄰兄弟結(jié)點(diǎn)都剛脫貧。刪除前需要兄弟結(jié)點(diǎn)的合并操作,*/ // 3b, 如果所在孩子節(jié)點(diǎn)相鄰的兄弟節(jié)點(diǎn)都只包含 BTree_D - 1 個關(guān)鍵字, // 將 child 與其一相鄰節(jié)點(diǎn)合并,并將 node 中的一個關(guān)鍵字下降到合并節(jié)點(diǎn)中, // 再在 node 中刪除那個關(guān)鍵字和相關(guān)指針,若 node 的 key 為空,刪之,并調(diào)整根為合并結(jié)點(diǎn)。 // 最后,在相關(guān)孩子節(jié)點(diǎn)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);//調(diào)整后,在key所在孩子結(jié)點(diǎn)中繼續(xù)遞歸刪除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 為葉子節(jié)點(diǎn),找不到 key,查找失敗返回 if (tree->isLeaf) { return NULL; } // 節(jié)點(diǎn)內(nèi)查找失敗,但 tree->key[i - 1]< key < tree->key[i], // 下一個查找的結(jié)點(diǎn)應(yīng)為 child[i] // 從磁盤讀取第 i 個孩子的數(shù)據(jù) disk_read(&tree->child[i]); // 遞歸地繼續(xù)查找于樹 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 開始創(chuàng)建 B-樹,關(guān)鍵字為:\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插入關(guā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; }
總結(jié)
- 上一篇: Qt5.7| C/C++ 超级简单一
- 下一篇: C/C++基础面试-Const的全面理解