首页 > 代码库 > 算法14---B树
算法14---B树
算法14---B树
更详细的讲解见http://www.xuebuyuan.com/509072.html
一棵m阶的B 树 (m叉树)的特性,如下:
(1)树中每个结点含有最多含有个孩子,即m满足:ceil(m/2)-1<=n<=m-1。
(2)除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
(3)若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
1.1、插入(insert)操作
插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素,注意:
- 如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,
- 如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。
- 如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。
1.2、删除(delete)操作
首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除,如果删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素到父节点中,然后是移动之后的情况;如果没有,直接删除后,移动之后的情况。
删除元素,移动相应元素之后,
(1)如果某结点中元素数目(即关键字数)小于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),
(2) 如果丰满,则向父节点借一个元素来满足条件;
(3)如果其相邻兄弟都刚脱贫,即借了之后其结点数目小于ceil(m/2)-1,则该结点与其相邻的某一兄弟结点进行“合并”成一个结点,以此来满足条件。
源代码实现:代码中给出了参考的出处,代码写的很好,值得好好学习。
1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <assert.h> 4 5 //参考地址:http://www.xuebuyuan.com/509072.html 6 7 8 9 //实现对order序(阶)的B-TREE结构基本操作的封装。 10 //查找:search,插入:insert,删除:remove。 11 //创建:create,销毁:destory,打印:print。 12 13 14 15 ////* 定义m序(阶)B 树的最小度数BTree_D=ceil(m)*/ 16 /// 在这里定义每个节点中关键字的最大数目为:2 * BTree_D - 1,即序(阶):2 * BTree_D. 17 #define BTree_D 2 18 #define ORDER (BTree_D * 2) //定义为4阶B-tree,2-3-4树。最简单为3阶B-tree,2-3树。 19 //#define ORDER (BTree_T * 2-1) //最简单为3阶B-tree,2-3树。 20 21 typedef int KeyType; 22 typedef struct BTNode{ 23 int keynum; /// 结点中关键字的个数,keynum <= BTree_N 24 KeyType key[ORDER-1]; /// 关键字向量为key[0..keynum - 1] 25 struct BTNode* child[ORDER]; /// 孩子指针向量为child[0..keynum] 26 bool isLeaf; /// 是否是叶子节点的标志 27 }BTNode; 28 29 typedef BTNode* BTree; ///定义BTree 30 31 ///给定数据集data,创建BTree。 32 void BTree_create(BTree* tree, const KeyType* data, int length); 33 34 ///销毁BTree,释放内存空间。 35 void BTree_destroy(BTree* tree); 36 37 ///在BTree中插入关键字key。 38 void BTree_insert(BTree* tree, KeyType key); 39 40 ///在BTree中移除关键字key。 41 void BTree_remove(BTree* tree, KeyType key); 42 43 ///深度遍历BTree打印各层结点信息。 44 void BTree_print(const BTree tree, int layer=1); 45 46 /// 在BTree中查找关键字 key, 47 /// 成功时返回找到的节点的地址及 key 在其中的位置 *pos 48 /// 失败时返回 NULL 及查找失败时扫描到的节点位置 *pos 49 BTNode* BTree_search(const BTree tree, int key, int* pos); 50 51 52 53 #define cmp(a, b) ( ( ((a)-(b)) >= (0) ) ? (1) : (0) ) //比较a,b大小 54 #define DEBUG_BTREE 55 56 57 58 // 模拟向磁盘写入节点 59 void disk_write(BTNode* node) 60 { 61 //打印出结点中的全部元素,方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据);而不是keynum个元素。 62 printf("向磁盘写入节点"); 63 for(int i=0;i<ORDER-1;i++){ 64 printf("%c",node->key[i]); 65 } 66 printf("\n"); 67 } 68 69 70 // 模拟从磁盘读取节点 71 void disk_read(BTNode** node) 72 { 73 //打印出结点中的全部元素,方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据);而不是keynum个元素。 74 printf("向磁盘读取节点"); 75 for(int i=0;i<ORDER-1;i++){ 76 printf("%c",(*node)->key[i]); 77 } 78 printf("\n"); 79 } 80 81 82 // 按层次打印 B 树 83 void BTree_print(const BTree tree, int layer) 84 { 85 int i; 86 BTNode* node = tree; 87 88 if (node) { 89 printf("第 %d 层, %d node : ", layer, node->keynum); 90 91 //打印出结点中的全部元素,方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据);而不是keynum个元素。 92 for (i = 0; i < ORDER-1; ++i) { 93 //for (i = 0; i < node->keynum; ++i) { 94 printf("%c ", node->key[i]); 95 } 96 97 printf("\n"); 98 99 ++layer;100 for (i = 0 ; i <= node->keynum; i++) {101 if (node->child[i]) {102 BTree_print(node->child[i], layer);103 }104 }105 }106 else {107 printf("树为空。\n");108 }109 }110 111 112 // 结点node内对关键字进行二分查找。113 int binarySearch(BTNode* node, int low, int high, KeyType Fkey)114 {115 int mid;116 while (low<=high)117 {118 mid = low + (high-low)/2;119 if (Fkey<node->key[mid])120 {121 high = mid-1;122 }123 if (Fkey>node->key[mid])124 {125 low = mid+1;126 }127 if (Fkey==node->key[mid])128 {129 return mid;//返回下标。130 }131 }132 return 0;//未找到返回0.133 }134 135 //insert136 /***************************************************************************************137 将分裂的结点中的一半元素给新建的结点,并且将分裂结点中的中间关键字元素上移至父节点中。138 parent 是一个非满的父节点139 node 是 tree 孩子表中下标为 index 的孩子节点,且是满的,需分裂。140 *******************************************************************/141 void BTree_split_child(BTNode* parent, int index, BTNode* node)142 {143 #ifdef DEBUG_BTREE144 printf("BTree_split_child!\n");145 #endif146 assert(parent && node);147 int i;148 149 // 创建新节点,存储 node 中后半部分的数据150 BTNode* newNode = (BTNode*)calloc(sizeof(BTNode), 1);151 if (!newNode) {152 printf("Error! out of memory!\n");153 return;154 }155 156 newNode->isLeaf = node->isLeaf;157 newNode->keynum = BTree_D - 1;158 159 // 拷贝 node 后半部分关键字,然后将node后半部分置为0。160 for (i = 0; i < newNode->keynum; ++i){161 newNode->key[i] = node->key[BTree_D + i];162 node->key[BTree_D + i] = 0;163 }164 165 // 如果 node 不是叶子节点,拷贝 node 后半部分的指向孩子节点的指针,然后将node后半部分指向孩子节点的指针置为NULL。166 if (!node->isLeaf) {167 for (i = 0; i < BTree_D; i++) {168 newNode->child[i] = node->child[BTree_D + i];169 node->child[BTree_D + i] = NULL;170 }171 }172 173 // 将 node 分裂出 newNode 之后,里面的数据减半174 node->keynum = BTree_D - 1;175 176 // 调整父节点中的指向孩子的指针和关键字元素。分裂时父节点增加指向孩子的指针和关键元素。177 for (i = parent->keynum; i > index; --i) {178 parent->child[i + 1] = parent->child[i];179 }180 181 parent->child[index + 1] = newNode;182 183 for (i = parent->keynum - 1; i >= index; --i) {184 parent->key[i + 1] = parent->key[i];185 }186 187 parent->key[index] = node->key[BTree_D - 1];188 ++parent->keynum;189 190 node->key[BTree_D - 1] = 0;191 192 // 写入磁盘193 disk_write(parent);194 disk_write(newNode);195 disk_write(node);196 }197 198 void BTree_insert_nonfull(BTNode* node, KeyType key)199 {200 assert(node);201 202 int i;203 204 // 节点是叶子节点,直接插入205 if (node->isLeaf) {206 i = node->keynum - 1;207 while (i >= 0 && key < node->key[i]) {208 node->key[i + 1] = node->key[i];209 --i;210 }211 212 node->key[i + 1] = key;213 ++node->keynum;214 215 // 写入磁盘216 disk_write(node);217 }218 219 // 节点是内部节点220 else {221 /* 查找插入的位置*/222 i = node->keynum - 1;223 while (i >= 0 && key < node->key[i]) {224 --i;225 }226 227 ++i;228 229 // 从磁盘读取孩子节点230 disk_read(&node->child[i]);231 232 // 如果该孩子节点已满,分裂调整值233 if (node->child[i]->keynum == (ORDER-1)) {234 BTree_split_child(node, i, node->child[i]);235 // 如果待插入的关键字大于该分裂结点中上移到父节点的关键字,在该关键字的右孩子结点中进行插入操作。236 if (key > node->key[i]) {237 ++i;238 }239 }240 BTree_insert_nonfull(node->child[i], key);241 }242 }243 244 void BTree_insert(BTree* tree, KeyType key)245 {246 #ifdef DEBUG_BTREE247 printf("BTree_insert:\n");248 #endif249 BTNode* node;250 BTNode* root = *tree;251 252 // 树为空253 if (NULL == root) {254 root = (BTNode*)calloc(sizeof(BTNode), 1);255 if (!root) {256 printf("Error! out of memory!\n");257 return;258 }259 root->isLeaf = true;260 root->keynum = 1;261 root->key[0] = key;262 263 *tree = root;264 265 // 写入磁盘266 disk_write(root);267 268 return;269 }270 271 // 根节点已满,插入前需要进行分裂调整272 if (root->keynum == (ORDER-1)) {273 // 产生新节点当作根274 node = (BTNode*)calloc(sizeof(BTNode), 1);275 if (!node) {276 printf("Error! out of memory!\n");277 return;278 }279 280 *tree = node;281 node->isLeaf = false;282 node->keynum = 0;283 node->child[0] = root;284 285 BTree_split_child(node, 0, root);286 287 BTree_insert_nonfull(node, key);288 }289 290 // 根节点未满,在当前节点中插入 key291 else {292 BTree_insert_nonfull(root, key);293 }294 }295 296 297 298 299 300 //remove301 // 对 tree 中的节点 node 进行合并孩子节点处理.302 // 注意:孩子节点的 keynum 必须均已达到下限,即均等于 BTree_D - 1303 // 将 tree 中索引为 index 的 key 下移至左孩子结点中,304 // 将 node 中索引为 index + 1 的孩子节点合并到索引为 index 的孩子节点中,右孩子合并到左孩子结点中。305 // 并调相关的 key 和指针。306 307 void BTree_merge_child(BTree* tree, BTNode* node, int index)308 {309 #ifdef DEBUG_BTREE310 printf("BTree_merge_child!\n");311 #endif312 assert(tree && node && index >= 0 && index < node->keynum);313 314 int i;315 316 KeyType key = node->key[index];317 BTNode* leftChild = node->child[index];318 BTNode* rightChild = node->child[index + 1];319 320 assert(leftChild && leftChild->keynum == BTree_D - 1321 && rightChild && rightChild->keynum == BTree_D - 1);322 323 // 将 node中关键字下标为index 的 key 下移至左孩子结点中,该key所对应的右孩子结点指向node的右孩子结点中的第一个孩子。324 leftChild->key[leftChild->keynum] = key;325 leftChild->child[leftChild->keynum + 1] = rightChild->child[0];326 ++leftChild->keynum;327 328 // 右孩子的元素合并到左孩子结点中。329 for (i = 0; i < rightChild->keynum; ++i) {330 leftChild->key[leftChild->keynum] = rightChild->key[i];331 leftChild->child[leftChild->keynum + 1] = rightChild->child[i + 1];332 ++leftChild->keynum;333 }334 335 // 在 node 中下移的 key后面的元素前移336 for (i = index; i < node->keynum - 1; ++i) {337 node->key[i] = node->key[i + 1];338 node->child[i + 1] = node->child[i + 2];339 }340 node->key[node->keynum - 1] = 0;341 node->child[node->keynum] = NULL;342 --node->keynum;343 344 // 如果根节点没有 key 了,并将根节点调整为合并后的左孩子节点;然后删除释放空间。345 if (node->keynum == 0) {346 if (*tree == node) {347 *tree = leftChild;348 }349 350 free(node);351 node = NULL;352 }353 354 free(rightChild);355 rightChild = NULL;356 }357 358 void BTree_recursive_remove(BTree* tree, KeyType key)359 {360 // B-数的保持条件之一:361 // 非根节点的内部节点的关键字数目不能少于 BTree_D - 1362 363 int i, j, index;364 BTNode *root = *tree;365 BTNode *node = root;366 367 if (!root) {368 printf("Failed to remove %c, it is not in the tree!\n", key);369 return;370 }371 372 // 结点中找key。373 index = 0;374 while (index < node->keynum && key > node->key[index]) {375 ++index;376 }377 378 /*======================含有key的当前结点时的情况====================379 node:380 index of Key: i-1 i i+1381 +---+---+---+---+382 * key *383 +---+---+---+---+---+384 / 385 index of Child: i i+1386 / 387 +---+---+ +---+---+388 * * * * 389 +---+---+---+ +---+---+---+390 leftChild rightChild391 ============================================================*/392 /*一、结点中找到了关键字key的情况.*/393 BTNode *leftChild, *rightChild;394 KeyType leftKey, rightKey;395 if (index < node->keynum && node->key[index] == key) {396 /* 1,所在节点是叶子节点,直接删除*/397 if (node->isLeaf) {398 for (i = index; i < node->keynum-1; ++i) {399 node->key[i] = node->key[i + 1];400 //node->child[i + 1] = node->child[i + 2];叶子节点的孩子结点为空,无需移动处理。401 }402 node->key[node->keynum-1] = 0;403 //node->child[node->keynum] = NULL;404 --node->keynum;405 406 if (node->keynum == 0) {407 assert(node == *tree);408 free(node);409 *tree = NULL;410 }411 412 return;413 }414 /*2.选择脱贫致富的孩子结点。*/415 // 2a,选择相对富有的左孩子结点。416 // 如果位于 key 前的左孩子结点的 key 数目 >= BTree_D,417 // 在其中找 key 的左孩子结点的最后一个元素上移至父节点key的位置。418 // 然后在左孩子节点中递归删除元素leftKey。419 else if (node->child[index]->keynum >= BTree_D) {420 leftChild = node->child[index];421 leftKey = leftChild->key[leftChild->keynum - 1];422 node->key[index] = leftKey;423 424 BTree_recursive_remove(&leftChild, leftKey);425 }426 // 2b,选择相对富有的右孩子结点。427 // 如果位于 key 后的右孩子结点的 key 数目 >= BTree_D,428 // 在其中找 key 的右孩子结点的第一个元素上移至父节点key的位置429 // 然后在右孩子节点中递归删除元素rightKey。430 else if (node->child[index + 1]->keynum >= BTree_D) {431 rightChild = node->child[index + 1];432 rightKey = rightChild->key[0];433 node->key[index] = rightKey;434 435 BTree_recursive_remove(&rightChild, rightKey);436 }437 /*左右孩子结点都刚脱贫。删除前需要孩子结点的合并操作*/438 // 2c,左右孩子结点只包含 BTree_D - 1 个节点,439 // 合并是将 key 下移至左孩子节点,并将右孩子节点合并到左孩子节点中,440 // 删除右孩子节点,在父节点node中移除 key 和指向右孩子节点的指针,441 // 然后在合并了的左孩子节点中递归删除元素key。442 else if (node->child[index]->keynum == BTree_D - 1443 && node->child[index + 1]->keynum == BTree_D - 1){444 leftChild = node->child[index];445 446 BTree_merge_child(tree, node, index);447 448 // 在合并了的左孩子节点中递归删除 key449 BTree_recursive_remove(&leftChild, key);450 }451 }452 453 /*======================未含有key的当前结点时的情况====================454 node:455 index of Key: i-1 i i+1456 +---+---+---+---+457 * keyi *458 +---+---+---+---+---+459 / | 460 index of Child: i-1 i i+1461 / | 462 +---+---+ +---+---+ +---+---+463 * * * * * * 464 +---+---+---+ +---+---+---+ +---+---+---+465 leftSibling Child rightSibling 466 ============================================================*/467 /*二、结点中未找到了关键字key的情况.*/468 else {469 BTNode *leftSibling, *rightSibling, *child;470 // 3. key 不在内节点 node 中,则应当在某个包含 key 的子节点中。471 // key < node->key[index], 所以 key 应当在孩子节点 node->child[index] 中472 child = node->child[index];473 if (!child) {474 printf("Failed to remove %c, it is not in the tree!\n", key);475 return;476 }477 /*所需查找的该孩子结点刚脱贫的情况*/478 if (child->keynum == BTree_D - 1) {479 leftSibling = NULL;480 rightSibling = NULL;481 482 if (index - 1 >= 0) {483 leftSibling = node->child[index - 1];484 }485 486 if (index + 1 <= node->keynum) {487 rightSibling = node->child[index + 1];488 }489 /*选择致富的相邻兄弟结点。*/490 // 3a,如果所在孩子节点相邻的兄弟节点中有节点至少包含 BTree_D 个关键字491 // 将 node 的一个关键字key[index]下移到 child 中,将相对富有的相邻兄弟节点中一个关键字上移到492 // node 中,然后在 child 孩子节点中递归删除 key。493 if ((leftSibling && leftSibling->keynum >= BTree_D)494 || (rightSibling && rightSibling->keynum >= BTree_D)) {495 int richR = 0;496 if(rightSibling) richR = 1;497 if(leftSibling && rightSibling) {498 richR = cmp(rightSibling->keynum,leftSibling->keynum);499 }500 if (rightSibling && rightSibling->keynum >= BTree_D && richR) {501 //相邻右兄弟相对富有,则该孩子先向父节点借一个元素,右兄弟中的第一个元素上移至父节点所借位置,并进行相应调整。502 child->key[child->keynum] = node->key[index];503 child->child[child->keynum + 1] = rightSibling->child[0];504 ++child->keynum;505 506 node->key[index] = rightSibling->key[0];507 508 for (j = 0; j < rightSibling->keynum - 1; ++j) {//元素前移509 rightSibling->key[j] = rightSibling->key[j + 1];510 rightSibling->child[j] = rightSibling->child[j + 1];511 }512 rightSibling->key[rightSibling->keynum-1] = 0;513 rightSibling->child[rightSibling->keynum-1] = rightSibling->child[rightSibling->keynum];514 rightSibling->child[rightSibling->keynum] = NULL;515 --rightSibling->keynum;516 }517 else {//相邻左兄弟相对富有,则该孩子向父节点借一个元素,左兄弟中的最后元素上移至父节点所借位置,并进行相应调整。518 for (j = child->keynum; j > 0; --j) {//元素后移519 child->key[j] = child->key[j - 1];520 child->child[j + 1] = child->child[j];521 }522 child->child[1] = child->child[0];523 child->child[0] = leftSibling->child[leftSibling->keynum];524 child->key[0] = node->key[index - 1];525 ++child->keynum;526 527 node->key[index - 1] = leftSibling->key[leftSibling->keynum - 1];528 529 leftSibling->key[leftSibling->keynum - 1] = 0;530 leftSibling->child[leftSibling->keynum] = NULL;531 532 --leftSibling->keynum;533 }534 }535 /*相邻兄弟结点都刚脱贫。删除前需要兄弟结点的合并操作,*/536 // 3b, 如果所在孩子节点相邻的兄弟节点都只包含 BTree_D - 1 个关键字,537 // 将 child 与其一相邻节点合并,并将 node 中的一个关键字下降到合并节点中,538 // 再在 node 中删除那个关键字和相关指针,若 node 的 key 为空,删之,并调整根为合并结点。539 // 最后,在相关孩子节点child中递归删除 key。540 else if ((!leftSibling || (leftSibling && leftSibling->keynum == BTree_D - 1))541 && (!rightSibling || (rightSibling && rightSibling->keynum == BTree_D - 1))) {542 if (leftSibling && leftSibling->keynum == BTree_D - 1) {543 544 BTree_merge_child(tree, node, index - 1);//node中的右孩子元素合并到左孩子中。545 546 child = leftSibling;547 }548 549 else if (rightSibling && rightSibling->keynum == BTree_D - 1) {550 551 BTree_merge_child(tree, node, index);//node中的右孩子元素合并到左孩子中。552 }553 }554 }555 556 BTree_recursive_remove(&child, key);//调整后,在key所在孩子结点中继续递归删除key。557 }558 }559 560 void BTree_remove(BTree* tree, KeyType key)561 {562 #ifdef DEBUG_BTREE563 printf("BTree_remove:\n");564 #endif565 if (*tree==NULL)566 { 567 printf("BTree is NULL!\n");568 return;569 }570 571 BTree_recursive_remove(tree, key);572 }573 574 575 576 //=====================================search====================================577 578 BTNode* BTree_recursive_search(const BTree tree, KeyType key, int* pos)579 {580 int i = 0;581 582 while (i < tree->keynum && key > tree->key[i]) {583 ++i;584 }585 586 // Find the key.587 if (i < tree->keynum && tree->key[i] == key) {588 *pos = i;589 return tree;590 }591 592 // tree 为叶子节点,找不到 key,查找失败返回593 if (tree->isLeaf) {594 return NULL;595 }596 597 // 节点内查找失败,但 tree->key[i - 1]< key < tree->key[i],598 // 下一个查找的结点应为 child[i]599 600 // 从磁盘读取第 i 个孩子的数据601 disk_read(&tree->child[i]);602 603 // 递归地继续查找于树 tree->child[i]604 return BTree_recursive_search(tree->child[i], key, pos);605 }606 607 BTNode* BTree_search(const BTree tree, KeyType key, int* pos)608 {609 #ifdef DEBUG_BTREE610 printf("BTree_search:\n");611 #endif612 if (!tree) {613 printf("BTree is NULL!\n");614 return NULL;615 }616 *pos = -1;617 return BTree_recursive_search(tree,key,pos);618 }619 620 //===============================create===============================621 void BTree_create(BTree* tree, const KeyType* data, int length)622 {623 assert(tree);624 625 int i;626 627 #ifdef DEBUG_BTREE628 printf("\n 开始创建 B-树,关键字为:\n");629 for (i = 0; i < length; i++) {630 printf(" %c ", data[i]);631 }632 printf("\n");633 #endif634 635 for (i = 0; i < length; i++) {636 #ifdef DEBUG_BTREE637 printf("\n插入关键字 %c:\n", data[i]);638 #endif639 int pos = -1;640 BTree_search(*tree,data[i],&pos);//树的递归搜索。641 if (pos!=-1)642 {643 printf("this key %c is in the B-tree,not to insert.\n",data[i]);644 }else{645 BTree_insert(tree, data[i]);//插入元素到BTree中。646 }647 648 #ifdef DEBUG_BTREE649 BTree_print(*tree);//树的深度遍历。650 #endif651 }652 653 printf("\n");654 }655 656 657 658 659 660 //===============================destroy===============================661 void BTree_destroy(BTree* tree)662 {663 int i;664 BTNode* node = *tree;665 666 if (node) {667 for (i = 0; i <= node->keynum; i++) {668 BTree_destroy(&node->child[i]);669 }670 671 free(node);672 }673 674 *tree = NULL;675 }676 677 678 679 680 681 //================以下是测试的部分===================682 683 void test_BTree_search(BTree tree, KeyType key)684 {685 int pos = -1;686 BTNode* node = BTree_search(tree, key, &pos);687 if (node) {688 printf("在%s节点(包含 %d 个关键字)中找到关键字 %c,其索引为 %d\n",689 node->isLeaf ? "叶子" : "非叶子",690 node->keynum, key, pos);691 }692 else {693 printf("在树中找不到关键字 %c\n", key);694 }695 }696 697 void test_BTree_remove(BTree* tree, KeyType key)698 {699 printf("\n移除关键字 %c \n", key);700 BTree_remove(tree, key);701 BTree_print(*tree);702 printf("\n");703 }704 705 void test_btree()706 {707 708 KeyType array[] = {709 ‘G‘,‘G‘, ‘M‘, ‘P‘, ‘X‘, ‘A‘, ‘C‘, ‘D‘, ‘E‘, ‘J‘, ‘K‘,710 ‘N‘, ‘O‘, ‘R‘, ‘S‘, ‘T‘, ‘U‘, ‘V‘, ‘Y‘, ‘Z‘, ‘F‘, ‘X‘711 };712 const int length = sizeof(array)/sizeof(KeyType);713 BTree tree = NULL;714 BTNode* node = NULL;715 int pos = -1;716 KeyType key1 = ‘R‘; // in the tree.717 KeyType key2 = ‘B‘; // not in the tree.718 719 // 创建720 BTree_create(&tree, array, length);721 722 printf("\n=== 创建 B- 树 ===\n");723 BTree_print(tree);724 printf("\n");725 726 // 查找727 test_BTree_search(tree, key1);728 printf("\n");729 test_BTree_search(tree, key2);730 731 // 移除不在B树中的元素732 test_BTree_remove(&tree, key2);733 printf("\n");734 735 // 插入关键字736 printf("\n插入关键字 %c \n", key2);737 BTree_insert(&tree, key2);738 BTree_print(tree);739 printf("\n");740 741 test_BTree_search(tree, key2);742 743 // 移除关键字744 test_BTree_remove(&tree, key2);745 test_BTree_search(tree, key2);746 747 key2 = ‘M‘;748 test_BTree_remove(&tree, key2);749 test_BTree_search(tree, key2);750 751 key2 = ‘E‘;752 test_BTree_remove(&tree, key2);753 test_BTree_search(tree, key2);754 755 key2 = ‘G‘;756 test_BTree_remove(&tree, key2);757 test_BTree_search(tree, key2);758 759 key2 = ‘A‘;760 test_BTree_remove(&tree, key2);761 test_BTree_search(tree, key2);762 763 key2 = ‘D‘;764 test_BTree_remove(&tree, key2);765 test_BTree_search(tree, key2);766 767 key2 = ‘K‘;768 test_BTree_remove(&tree, key2);769 test_BTree_search(tree, key2);770 771 key2 = ‘P‘;772 test_BTree_remove(&tree, key2);773 test_BTree_search(tree, key2);774 775 key2 = ‘J‘;776 test_BTree_remove(&tree, key2);777 test_BTree_search(tree, key2);778 779 key2 = ‘C‘;780 test_BTree_remove(&tree, key2);781 test_BTree_search(tree, key2);782 783 key2 = ‘X‘;784 test_BTree_remove(&tree, key2);785 test_BTree_search(tree, key2);786 787 key2 = ‘O‘;788 test_BTree_remove(&tree, key2);789 test_BTree_search(tree, key2);790 791 key2 = ‘V‘;792 test_BTree_remove(&tree, key2);793 test_BTree_search(tree, key2);794 795 key2 = ‘R‘;796 test_BTree_remove(&tree, key2);797 test_BTree_search(tree, key2);798 799 key2 = ‘U‘;800 test_BTree_remove(&tree, key2);801 test_BTree_search(tree, key2);802 803 key2 = ‘T‘;804 test_BTree_remove(&tree, key2);805 test_BTree_search(tree, key2);806 807 key2 = ‘N‘;808 test_BTree_remove(&tree, key2);809 test_BTree_search(tree, key2);810 key2 = ‘S‘;811 test_BTree_remove(&tree, key2);812 test_BTree_search(tree, key2);813 key2 = ‘Y‘;814 test_BTree_remove(&tree, key2);815 test_BTree_search(tree, key2);816 key2 = ‘F‘;817 test_BTree_remove(&tree, key2);818 test_BTree_search(tree, key2);819 key2 = ‘Z‘;820 test_BTree_remove(&tree, key2);821 test_BTree_search(tree, key2);822 823 // 销毁824 BTree_destroy(&tree);825 }826 827 int main()828 {829 test_btree();830 831 return 0;832 }
算法14---B树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。