B树的实现
B树（B-tree）是一种平衡的多路查找树，用于存储和管理大量有序数据。与二叉搜索树不同，B树可以在节点中存储多个关键字，并拥有多个子节点，使得查找、插入和删除操作具有更高的效率。
B树的基本定义：
- B树的阶数 t 指定了每个节点最多可以拥有 2t - 1 个键值。
- 叶子节点包含 2t - 1 个键值，内部节点包含 2t - 1 到 2t 个子节点。
- B树保持平衡，确保查找、插入和删除的时间复杂度为 O(log n)。
B树的特性：
- 根节点至少包含 1 个关键字，最多 2t - 1 个。
- 非叶子节点包含 2t 个子节点。
- 叶子节点具有相同的深度。
B树的操作：
-
插入操作：
- 如果节点满了，就分裂节点。
- 如果父节点也满了，就递归分裂，直到根节点。
-
查找操作：
- 从根节点开始，按键值进行遍历，找到目标位置。
-
删除操作：
- 如果键值在非叶子节点，找到前驱或后继进行替换。
- 如果在叶子节点，直接删除并调整。
1. 定义和结构体定义
#define DEGREE 3
typedef int KEY_VALUE;
// 定义B树节点结构体
typedef struct _btree_node {
KEY_VALUE *keys; // 键值数组
struct _btree_node **childrens; // 子节点指针
int num; // 当前节点的键值数量
int leaf; // 是否为叶子节点：1表示叶子，0表示非叶子
} btree_node;
// 定义B树结构体
typedef struct _btree {
btree_node *root; // 根节点
int t; // 阶数
} btree;
DEGREE：定义B树的阶数，这决定了每个节点的最大子节点数（2t - 1 键值，2t 子节点）。btree_node：每个节点包含：keys：存储键值。childrens：存储子节点指针。num：当前节点中实际的键值数量。leaf：标志当前节点是否是叶子节点。
btree：包含B树的根节点和阶数。
2. 节点创建函数 btree_create_node
btree_node *btree_create_node(int t, int leaf) {
btree_node *node = (btree_node *)calloc(1, sizeof(btree_node));
if (node == NULL) {
return NULL;
}
node->leaf = leaf;
node->keys = (KEY_VALUE *)calloc(1, (2 * t - 1) * sizeof(KEY_VALUE));
node->childrens = (btree_node **)calloc(1, (2 * t) * sizeof(btree_node *));
node->num = 0;
return node;
}
btree_create_node：创建一个新的B树节点。- 参数
t：阶数。 - 参数
leaf：是否为叶子节点。 - 返回创建的节点。
3. 节点销毁函数 btree_destroy_node
void btree_destroy_node(btree_node *node) {
if (node) {
free(node->childrens);
free(node->keys);
free(node);
}
}
btree_destroy_node：释放节点内存。
4. B树初始化函数 btree_create
void btree_create(btree *T, int t) {
T->t = t;
btree_node *x = btree_create_node(t, 1); // 根节点为叶子节点
T->root = x;
}
btree_create：初始化B树，创建一个根节点为叶子的B树结构。
5. 分裂函数 btree_split_child
void btree_split_child(btree *T, btree_node *x, int i) {
int t = T->t;
btree_node *y = x->childrens[i]; // 被分裂的节点
btree_node *z = btree_create_node(t, y->leaf); // 新的节点
z->num = t - 1; // 新节点的键值数量
// 复制y节点后半部分的键值到z节点
for (int j = 0; j < t - 1; j++) {
z->keys[j] = y->keys[j + t];
}
if (y->leaf == 0) {
for (int j = 0; j < t; j++) {
z->childrens[j] = y->childrens[j + t];
}
}
y->num = t - 1; // y节点的键值数量调整
// 为x节点腾出位置插入新的子节点指针
for (int j = x->num; j >= i + 1; j--) {
x->childrens[j + 1] = x->childrens[j];
}
x->childrens[i + 1] = z;
// 调整x节点的键值，将分裂出来的键值放到合适位置
for (int j = x->num - 1; j >= i; j--) {
x->keys[j + 1] = x->keys[j];
}
x->keys[i] = y->keys[t - 1];
x->num += 1;
}
btree_split_child：分裂节点x的第i个子节点，确保B树保持平衡。- 如果某个节点的子节点满了，就需要将它分裂成两个新的子节点。
6. 非满节点插入函数 btree_insert_nonfull
void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {
int i = x->num - 1;
if (x->leaf == 1) {
// 从后往前找到合适的插入位置
while (i >= 0 && x->keys[i] > k) {
x->keys[i + 1] = x->keys[i];
i--;
}
x->keys[i + 1] = k;
x->num += 1;
}
else {
while (i >= 0 && x->keys[i] > k) {
i--;
}
if (x->childrens[i + 1]->num == (2 * (T->t)) - 1) {
btree_split_child(T, x, i + 1);
if (k > x->keys[i + 1]) {
i++;
}
}
btree_insert_nonfull(T, x->childrens[i + 1], k);
}
}
btree_insert_nonfull：向非满的节点插入键值k。- 如果插入位置满了，则需要分裂对应的子节点，确保节点和树结构的平衡。
7. B树插入函数 btree_insert
void btree_insert(btree *T, KEY_VALUE key) {
btree_node *r = T->root;
if (r->num == 2 * T->t - 1) {
btree_node *node = btree_create_node(T->t, 0); // 创建新的根节点
if (node == NULL) {
return; // 内存分配失败处理
}
T->root = node;
node->childrens[0] = r;
btree_split_child(T, node, 0);
int i = 0;
if (node->keys[0] < key) {
i++;
}
btree_insert_nonfull(T, node->childrens[i], key);
}
else {
btree_insert_nonfull(T, r, key);
}
}
btree_insert：插入一个键值key。- 如果根节点满了，就创建一个新的根节点，进行分裂并插入新节点。
8. 中序遍历函数 btree_traverse
void btree_traverse(btree_node *x) {
for (int i = 0; i < x->num; i++) {
if (x->leaf == 0) {
btree_traverse(x->childrens[i]);
}
printf("%d ", x->keys[i]);
}
if (x->leaf == 0) {
btree_traverse(x->childrens[x->num]);
}
}
btree_traverse：递归地中序遍历B树。
9. 打印B树结构 btree_print
void btree_print(btree *T, btree_node *node, int layer) {
if (node) {
printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, node->num, node->leaf);
for (int i = 0; i < node->num; i++) {
printf("%d ", node->keys[i]);
}
printf("\n");
layer++;
for (int i = 0; i <= node->num; i++) {
if (node->childrens[i]) {
btree_print(T, node->childrens[i], layer);
}
}
}
else {
printf("the tree is empty\n");
}
}
btree_print：打印B树的结构，展示每个节点的层级和键值。
10. 删除函数 btree_delete_key
void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {
if (node == NULL) {
return;
}
int idx = 0;
while (idx < node->num && key > node->keys[idx]) {
idx++;
}
if (idx < node->num && key == node->keys[idx]) {
if (node->leaf) {
for (int i = idx; i < node->num - 1; i++) {
node->keys[i] = node->keys[i + 1];
}
node->keys[node->num - 1] = 0;
node->num--;
if (node->num == 0) {
free(node);
T->root = NULL;
}
}
else {
// Find predecessor or successor
btree_node *child = node->childrens[idx];
if (child->num >= T->t) {
btree_node *left = node->childrens[idx];
node->keys[idx] = left->keys[left->num - 1];
btree_delete_key(T, left, left->keys[left->num - 1]);
}
else {
// Merge and delete
btree_merge(T, node, idx);
btree_delete_key(T, node->childrens[idx], key);
}
}
}
else {
btree_node *child = node->childrens[idx];
if (child && child->num == T->t - 1) {
btree_node *left = NULL, *right = NULL;
if (idx > 0) {
left = node->childrens[idx - 1];
}
if (idx < node->num) {
right = node->childrens[idx + 1];
}
if ((left && left->num >= T->t) || (right && right->num >= T->t)) {
int richR = 0;
if (right) {
richR = 1;
}
if (left && right) {
richR = (right->num > left->num) ? 1 : 0;
}
if (right && right->num >= T->t && richR) {
// Borrow from right
child->keys[child->num] = node->keys[idx];
child->childrens[child->num + 1] = right->childrens[0];
child->num++;
node->keys[idx] = right->keys[0];
for (int i = 0; i < right->num - 1; i++) {
right->keys[i] = right->keys[i + 1];
right->childrens[i] = right->childrens[i + 1];
}
right->keys[right->num - 1] = 0;
right->childrens[right->num] = NULL;
right->num--;
}
else {
// Borrow from left
for (int i = child->num; i > 0; i--) {
child->keys[i] = child->keys[i - 1];
child->childrens[i + 1] = child->childrens[i];
}
child->childrens[1] = child->childrens[0];
child->childrens[0] = left->childrens[left->num];
child->keys[0] = node->keys[idx - 1];
child->num++;
node->keys[idx - 1] = left->keys[left->num - 1];
left->keys[left->num - 1] = 0;
left->childrens[left->num] = NULL;
left->num--;
}
}
else if ((!left || (left->num == T->t - 1)) && (!right || (right->num == T->t - 1))) {
if (left && left->num == T->t - 1) {
btree_merge(T, node, idx - 1);
child = left;
}
else if (right && right->num == T->t - 1) {
btree_merge(T, node, idx);
}
}
}
btree_delete_key(T, child, key);
}
}
btree_delete_key：在B树中删除指定的键值key。- 通过递归的方式调整树结构，维护B树的平衡。
11. B树删除函数 btree_delete
int btree_delete(btree *T, KEY_VALUE key) {
if (!T->root) {
return -1; // 树为空
}
btree_delete_key(T, T->root, key);
if (T->root->num == 0) {
btree_node *temp = T->root;
T->root = T->root->childrens[0];
free(temp);
}
return 0; // 删除成功
}
btree_delete：外部接口，删除B树中的一个键值。
12. 示例主函数 main
int main() {
btree T;
btree_create(&T, DEGREE); // 创建B树，阶数为3
btree_insert(&T, 10);
btree_insert(&T, 20);
btree_insert(&T, 5);
btree_insert(&T, 6);
btree_insert(&T, 15);
btree_insert(&T, 25);
printf("B-tree traversal: ");
btree_traverse(T.root); // 中序遍历输出
btree_delete(&T, 15); // 删除键值15
printf("\nAfter deletion: ");
btree_traverse(T.root); // 中序遍历输出
btree_print(&T, T.root, 0); // 打印B树结构
return 0;
}