创建一个4阶B树，对其进行插入（所有上溢出情况）及删除（所有下溢出情况）操作的代码及其相关数学分析

Question

创建一个4阶B树，对其进行插入（所有上溢出情况）及删除（所有下溢出情况）操作的代码及其相关数学分析

Answer 1

引自免费微信小程序：皆我百晓生

为了实现一个4阶B树，并进行插入和删除操作，我们需要定义数据结构、插入和删除函数。首先，我们定义一个节点结构体，包含键值对数组、子节点指针数组以及节点的度数。

#include <stdio.h>
#include <stdlib.h>

#define MAX_KEYS 4 // 每个节点最多有4个键值对
#define MIN_DEGREE 2 // 节点至少有2个键值对

typedef struct Node {
    int keys[MAX_KEYS]; // 键值对
    int values[MAX_KEYS];
    struct Node* children[MAX_KEYS + 1]; // 子节点指针，最后一个用于指向右兄弟
    int degree; // 当前节点的键值对数量
} Node;

Node* create_node(void);
void insert(Node**, int, int);
void remove(Node**, int, int);

接下来，我们将实现create_node()函数，用于创建一个新的空节点。

Node* create_node() {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->degree = 0;
    return newNode;
}

现在我们编写插入函数insert()，这个函数接收一个指向根节点的指针、要插入的键值对的键和值。在插入过程中，我们需要处理节点满的情况，即当前节点的键值对数量达到MAX_KEYS。这时，我们会创建一个新的节点作为父节点，然后将原节点和新节点一起重新分配到父节点的子节点列表中。

void insert(Node** root, int key, int value) {
    if (*root == NULL) {
        *root = create_node();
        (*root)->keys[(*root)->degree++] = key;
        (*root)->values[(*root)->degree - 1] = value;
    } else {
        insert_helper(root, key, value, 0);
    }
}

void insert_helper(Node** current, int key, int value, int level) {
    if ((*current)->degree < MAX_KEYS) { // 如果还有空间，则直接插入
        (*current)->keys[(*current)->degree++] = key;
        (*current)->values[(*current)->degree - 1] = value;
    } else {
        Node* newRoot = create_node();
        newRoot->children[0] = *current;
        insert_split(newRoot, &newRoot->children[1], key, value, level + 1);
        *current = newRoot;
    }
}

void insert_split(Node* parent, Node** splitTarget, int key, int value, int level) {
    Node* oldChild = parent->children[level];
    Node* newChild = create_node();
    for (int i = 0; i < MAX_KEYS && i < oldChild->degree; ++i) {
        if (key > oldChild->keys[i]) {
            newChild->keys[newChild->degree++] = oldChild->keys[i];
            newChild->values[newChild->degree - 1] = oldChild->values[i];
        }
    }
    if (level < MAX_KEYS - 1) {
        parent->keys[level] = oldChild->keys[MAX_KEYS - 1];
        parent->values[level] = oldChild->values[MAX_KEYS - 1];
    }
    if (oldChild->degree >= MIN_DEGREE) {
        insert(oldChild, oldChild->keys[MAX_KEYS - 1], oldChild->values[MAX_KEYS - 1]);
    }
    oldChild->keys[MAX_KEYS - 1] = key;
    oldChild->values[MAX_KEYS - 1] = value;
    newChild->degree++;
    oldChild->degree--;
    parent->children[level + 1] = newChild;
    if (parent->degree == MAX_KEYS) {
        insert_split(parent, splitTarget, key, value, level);
    }
}

对于删除操作，我们需要处理节点下溢出的情况，即删除后节点的键值对数量少于MIN_DEGREE。这需要合并相邻的节点。我们首先实现一个通用的删除函数remove()，它会调用remove_helper()来进行具体的删除操作。

void remove(Node** root, int key) {
    if (*root != NULL) {
        remove_helper(root, key, 0);
    }
}

void remove_helper(Node** current, int key, int level) {
    if ((*current)->degree == 0) {
        return;
    }

    int index = find_key_index(*current, key, level);

    if (index < 0) {
        return;
    }

    if ((*current)->degree > MIN_DEGREE) {
        // 移除中间元素
        if (index < (*current)->degree / 2) {
            swap_keys_values(*current, index, (*current)->degree - 1);
        } else {
            // 移除末尾元素
            --(*current)->degree;
        }
        remove_leftover(current, level, index);
    } else {
        // 合并节点
        merge_with_neighbor(current, level);
    }
}

void remove_leftover(Node** current, int level, int removedIndex) {
    Node* sibling = (*current)->children[level + 1];
    if (sibling != NULL && sibling->degree > MIN_DEGREE) {
        // 从右侧兄弟节点借一个元素
        int borrowKey = sibling->keys[sibling->degree - 1];
        int borrowValue = sibling->values[sibling->degree - 1];

        sibling->keys[sibling->degree - 1] = (*current)->keys[removedIndex];
        sibling->values[sibling->degree - 1] = (*current)->values[removedIndex];
        (*current)->keys[removedIndex] = borrowKey;
        (*current)->values[removedIndex] = borrowValue;
        sibling->degree--;
        (*current)->degree++;
    }
}

void merge_with_neighbor(Node** current, int level) {
    Node* sibling = (*current)->children[level + 1];
    if (sibling != NULL && sibling->degree >= MIN_DEGREE) {
        Node* mergedNode = create_node();

        // 将左侧节点的所有元素复制到新节点
        for (int i = 0; i < (*current)->degree; ++i) {
            mergedNode->keys[i] = (*current)->keys[i];
            mergedNode->values[i] = (*current)->values[i];
        }

        // 将右侧节点的部分元素复制到新节点
        for (int i = 0; i < sibling->degree; ++i) {
            mergedNode->keys[(*current)->degree + i] = sibling->keys[i];
            mergedNode->values[(*current)->degree + i] = sibling->values[i];
        }

        // 更新父节点的子节点
        (*current)->children[level] = NULL;
        if (level < MAX_KEYS - 1) {
            (*current)->keys[level] = sibling->keys[sibling->degree - 1];
            (*current)->values[level] = sibling->values[sibling->degree - 1];
        }
        sibling->degree = 0;
        (*current)->degree += sibling->degree + 1;
        parent->children[level + 1] = NULL;
        free(sibling);
        *current = mergedNode;
    }
}

由于篇幅原因，这里仅提供了主要的C语言代码实现。实际运行这些代码时，还需要添加一些辅助功能，比如打印B树、查找键等。此外，上述代码没有处理错误条件，例如内存分配失败等情况。在实际应用中，你需要确保正确处理这些异常情况。

至于数学分析部分，B树的平衡性和性能取决于其阶数和每个节点的最小度数。对于一个4阶B树，其最大高度是O(logN)，其中N是树中的节点数。插入和删除操作的时间复杂度也是O(logN)，因为每次操作都会沿着树上升至根节点。然而，当发生节点分裂或合并时，可能会导致树的高度增加或减少，但总体来说，B树可以保持较好的平衡性，从而保证了查询效率。