C++如何实现B树 C++B树的基本操作与实现

#include <iostream>
#include <vector>
#include <algorithm>

template <typename T, int M> // M是B树的阶数
class BTreeNode {
public:
    bool leaf; // 是否是叶节点
    std::vector<T> keys; // 存储键值
    std::vector<BTreeNode<T, M>*> children; // 子节点指针
    int n; // 当前节点键值数量

    BTreeNode(bool leaf1) : leaf(leaf1), n(0) {}

    // 在非满节点中插入键值
    void insertNonFull(T k) {
        int i = n - 1;

        if (leaf) {
            while (i >= 0 && keys[i] > k) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = k;
            n++;
        } else {
            while (i >= 0 && keys[i] > k)
                i--;

            if (children[i + 1]->n == 2 * M - 1) {
                splitChild(i + 1, children[i + 1]);

                if (keys[i + 1] < k)
                    i++;
            }
            children[i + 1]->insertNonFull(k);
        }
    }

    // 分裂子节点
    void splitChild(int i, BTreeNode<T, M>* y) {
        BTreeNode<T, M>* z = new BTreeNode<T, M>(y->leaf);
        z->n = M - 1;

        for (int j = 0; j < M - 1; j++)
            z->keys[j] = y->keys[j + M];

        if (!y->leaf) {
            for (int j = 0; j < M; j++)
                z->children[j] = y->children[j + M];
        }

        y->n = M - 1;

        for (int j = n; j >= i + 1; j--)
            children[j + 1] = children[j];

        children[i + 1] = z;

        for (int j = n - 1; j >= i; j--)
            keys[j + 1] = keys[j];

        keys[i] = y->keys[M - 1];
        n++;
    }

    // 遍历B树
    void traverse() {
        int i;
        for (i = 0; i < n; i++) {
            if (!leaf)
                children[i]->traverse();
            std::cout << " " << keys[i];
        }

        if (!leaf)
            children[i]->traverse();
    }

    // 查找键值
    BTreeNode<T, M>* search(T k) {
        int i = 0;
        while (i < n && k > keys[i])
            i++;

        if (keys[i] == k)
            return this;

        if (leaf)
            return nullptr;

        return children[i]->search(k);
    }
};

template <typename T, int M>
class BTree {
public:
    BTreeNode<T, M>* root;

    BTree() : root(nullptr) {}

    void traverse() {
        if (root != nullptr)
            root->traverse();
    }

    BTreeNode<T, M>* search(T k) {
        return (root == nullptr) ? nullptr : root->search(k);
    }

    void insert(T k) {
        if (root == nullptr) {
            root = new BTreeNode<T, M>(true);
            root->keys[0] = k;
            root->n = 1;
        } else {
            if (root->n == 2 * M - 1) {
                BTreeNode<T, M>* s = new BTreeNode<T, M>(false);
                s->children[0] = root;
                s->splitChild(0, root);

                int i = 0;
                if (s->keys[0] < k)
                    i++;
                s->children[i]->insertNonFull(k);
                root = s;
            } else {
                root->insertNonFull(k);
            }
        }
    }
};

int main() {
    BTree<int, 3> t; // 创建一个3阶B树
    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    t.insert(30);
    t.insert(7);
    t.insert(17);

    std::cout << "Traversal of the constructed tree is ";
    t.traverse();
    std::cout << std::endl;

    BTreeNode<int, 3>* res = t.search(12);
    if (res != nullptr)
        std::cout << "Present" << std::endl;
    else
        std::cout << "Not Present" << std::endl;

    return 0;
}