了解B树的删除

文章目录

- - - - 1. 删除操作
      - 第一种情况
        第二种情况
        第三种情况
      - 2. C示例
      - 3. 删除复杂度
      - 参考文档

在本教程中，您将学习如何从B树中删除键。此外，您还可以找到C语言的示例。
删除B树上的元素包括三个主要事件：搜索要删除的键所在的节点、删除键和平衡树（如果需要）。
删除树时，可能会出现一种称为下溢的情况。当一个节点包含的键少于它应该持有的最小键数时，就会发生下溢。
在研究删除操作之前需要理解的术语是：

中序前置
节点左子节点上最大的键称为其中序前置。
中序后置
节点右子节点上的最小键称为其中序后置。

1. 删除操作

在完成下面的步骤之前，你必须知道关于m度B树的这些事实。（m可理解为子级数）

一个节点最多可以有m个子节点。
一个节点最多可以包含m-1个键。
一个节点至少应有 ⌈m/2⌉ 个子节点。
节点（根节点除外）至少应包含⌈m/2⌉-1个键。

B树中的删除操作主要有三种情况。

第一种情况

要删除的键位于叶中。有两种情况。

删除健不会违反节点应持有的最小健数的属性。
在下面的树中，删除32并不违反上述属性。
删除键违反了节点应持有的最小键数的属性。在这种情况下，我们按照从左到右的顺序从紧邻的兄弟节点借用一个键。
首先，去拜访他的左侧兄弟节点。如果左侧同级节点的键数超过最小值，则从该节点借用键。
否则，尝试从紧邻的右侧同级节点借用。
在下面的树中，删除31会导致上述情况。让我们从左侧同级节点借用一个键。

如果两个直接同级节点的键数都已达到最小值，则将该节点与左侧同级节点或右侧同级节点合并，这个合并是通过父节点完成的。
删除30会导致上述结果。

第二种情况

如果要删除的键位于内部节点中，则会发生以下情况。

如果左子节点的键数超过最小值，则删除的内部节点将替换为中序前置节点。
如果右子节点的键数超过最小值，则删除的内部节点将替换为中序后置节点。
如果任一子级的键数正好是最小的，则合并左子级和右子级。

合并后，如果父节点的键数小于最小值，则查找同级，如第一种情况所示。

第三种情况

在这种情况下，树的高度会缩小。如果目标键位于内部节点中，并且删除该键会导致节点中的键数量减少（即，少于所需的最小值），则查找中序前置和中序后置。如果两个子项都包含最少数量的键，则不能进行借用。这导致了第二种情况（3），即合并孩子。
再说一遍，找兄弟同级借键。但是，如果同级也只有最少数量的键，则将节点与同级以及父级合并。把孩子们按顺序排列好。
在这里插入图片描述

2. C示例

// Deleting a key from a B-tree in C#include <stdio.h>
#include <stdlib.h>#define MAX 3
#define MIN 2struct BTreeNode {int item[MAX + 1], count;struct BTreeNode *linker[MAX + 1];
};struct BTreeNode *root;// Node creation
struct BTreeNode *createNode(int item, struct BTreeNode *child) {struct BTreeNode *newNode;newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));newNode->item[1] = item;newNode->count = 1;newNode->linker[0] = root;newNode->linker[1] = child;return newNode;
}// Add value to the node
void addValToNode(int item, int pos, struct BTreeNode *node,struct BTreeNode *child) {int j = node->count;while (j > pos) {node->item[j + 1] = node->item[j];node->linker[j + 1] = node->linker[j];j--;}node->item[j + 1] = item;node->linker[j + 1] = child;node->count++;
}// Split the node
void splitNode(int item, int *pval, int pos, struct BTreeNode *node,struct BTreeNode *child, struct BTreeNode **newNode) {int median, j;if (pos > MIN)median = MIN + 1;elsemedian = MIN;*newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));j = median + 1;while (j <= MAX) {(*newNode)->item[j - median] = node->item[j];(*newNode)->linker[j - median] = node->linker[j];j++;}node->count = median;(*newNode)->count = MAX - median;if (pos <= MIN) {addValToNode(item, pos, node, child);} else {addValToNode(item, pos - median, *newNode, child);}*pval = node->item[node->count];(*newNode)->linker[0] = node->linker[node->count];node->count--;
}// Set the value in the node
int setValueInNode(int item, int *pval,struct BTreeNode *node, struct BTreeNode **child) {int pos;if (!node) {*pval = item;*child = NULL;return 1;}if (item < node->item[1]) {pos = 0;} else {for (pos = node->count;(item < node->item[pos] && pos > 1); pos--);if (item == node->item[pos]) {printf("Duplicates not allowed\n");return 0;}}if (setValueInNode(item, pval, node->linker[pos], child)) {if (node->count < MAX) {addValToNode(*pval, pos, node, *child);} else {splitNode(*pval, pval, pos, node, *child, child);return 1;}}return 0;
}// Insertion operation
void insertion(int item) {int flag, i;struct BTreeNode *child;flag = setValueInNode(item, &i, root, &child);if (flag)root = createNode(i, child);
}// Copy the successor
void copySuccessor(struct BTreeNode *myNode, int pos) {struct BTreeNode *dummy;dummy = myNode->linker[pos];for (; dummy->linker[0] != NULL;)dummy = dummy->linker[0];myNode->item[pos] = dummy->item[1];
}// Remove the value
void removeVal(struct BTreeNode *myNode, int pos) {int i = pos + 1;while (i <= myNode->count) {myNode->item[i - 1] = myNode->item[i];myNode->linker[i - 1] = myNode->linker[i];i++;}myNode->count--;
}// Do right shift
void rightShift(struct BTreeNode *myNode, int pos) {struct BTreeNode *x = myNode->linker[pos];int j = x->count;while (j > 0) {x->item[j + 1] = x->item[j];x->linker[j + 1] = x->linker[j];}x->item[1] = myNode->item[pos];x->linker[1] = x->linker[0];x->count++;x = myNode->linker[pos - 1];myNode->item[pos] = x->item[x->count];myNode->linker[pos] = x->linker[x->count];x->count--;return;
}// Do left shift
void leftShift(struct BTreeNode *myNode, int pos) {int j = 1;struct BTreeNode *x = myNode->linker[pos - 1];x->count++;x->item[x->count] = myNode->item[pos];x->linker[x->count] = myNode->linker[pos]->linker[0];x = myNode->linker[pos];myNode->item[pos] = x->item[1];x->linker[0] = x->linker[1];x->count--;while (j <= x->count) {x->item[j] = x->item[j + 1];x->linker[j] = x->linker[j + 1];j++;}return;
}// Merge the nodes
void mergeNodes(struct BTreeNode *myNode, int pos) {int j = 1;struct BTreeNode *x1 = myNode->linker[pos], *x2 = myNode->linker[pos - 1];x2->count++;x2->item[x2->count] = myNode->item[pos];x2->linker[x2->count] = myNode->linker[0];while (j <= x1->count) {x2->count++;x2->item[x2->count] = x1->item[j];x2->linker[x2->count] = x1->linker[j];j++;}j = pos;while (j < myNode->count) {myNode->item[j] = myNode->item[j + 1];myNode->linker[j] = myNode->linker[j + 1];j++;}myNode->count--;free(x1);
}// Adjust the node
void adjustNode(struct BTreeNode *myNode, int pos) {if (!pos) {if (myNode->linker[1]->count > MIN) {leftShift(myNode, 1);} else {mergeNodes(myNode, 1);}} else {if (myNode->count != pos) {if (myNode->linker[pos - 1]->count > MIN) {rightShift(myNode, pos);} else {if (myNode->linker[pos + 1]->count > MIN) {leftShift(myNode, pos + 1);} else {mergeNodes(myNode, pos);}}} else {if (myNode->linker[pos - 1]->count > MIN)rightShift(myNode, pos);elsemergeNodes(myNode, pos);}}
}// Delete a value from the node
int delValFromNode(int item, struct BTreeNode *myNode) {int pos, flag = 0;if (myNode) {if (item < myNode->item[1]) {pos = 0;flag = 0;} else {for (pos = myNode->count; (item < myNode->item[pos] && pos > 1); pos--);if (item == myNode->item[pos]) {flag = 1;} else {flag = 0;}}if (flag) {if (myNode->linker[pos - 1]) {copySuccessor(myNode, pos);flag = delValFromNode(myNode->item[pos], myNode->linker[pos]);if (flag == 0) {printf("Given data is not present in B-Tree\n");}} else {removeVal(myNode, pos);}} else {flag = delValFromNode(item, myNode->linker[pos]);}if (myNode->linker[pos]) {if (myNode->linker[pos]->count < MIN)adjustNode(myNode, pos);}}return flag;
}// Delete operaiton
void delete (int item, struct BTreeNode *myNode) {struct BTreeNode *tmp;if (!delValFromNode(item, myNode)) {printf("Not present\n");return;} else {if (myNode->count == 0) {tmp = myNode;myNode = myNode->linker[0];free(tmp);}}root = myNode;return;
}void searching(int item, int *pos, struct BTreeNode *myNode) {if (!myNode) {return;}if (item < myNode->item[1]) {*pos = 0;} else {for (*pos = myNode->count;(item < myNode->item[*pos] && *pos > 1); (*pos)--);if (item == myNode->item[*pos]) {printf("%d present in B-tree", item);return;}}searching(item, pos, myNode->linker[*pos]);return;
}void traversal(struct BTreeNode *myNode) {int i;if (myNode) {for (i = 0; i < myNode->count; i++) {traversal(myNode->linker[i]);printf("%d ", myNode->item[i + 1]);}traversal(myNode->linker[i]);}
}int main() {int item, ch;insertion(8);insertion(9);insertion(10);insertion(11);insertion(15);insertion(16);insertion(17);insertion(18);insertion(20);insertion(23);traversal(root);delete (20, root);printf("\n");traversal(root);
}