C++如何实现一个简单的B树_C++数据结构与B树实现-C++-PHP中文网

C++如何实现一个简单的B树_C++数据结构与B树实现

下次还敢

发布： 2025-11-13 19:19:08

原创

865人浏览过

实现B树需定义节点结构与插入、查找操作。1. 节点包含关键字数组、子节点指针及数量；2. 插入时若节点满则分裂，保持平衡；3. 查找沿子树递归进行，确保高效检索。

c++如何实现一个简单的b树_c++数据结构与b树实现

实现一个简单的B树需要理解它的基本结构和操作规则。B树是一种自平衡的多路搜索树，常用于文件系统和数据库中，能够高效地处理大量数据的插入、删除和查找。

B树的基本性质

一个m阶B树具有以下特性：

每个节点最多有m个子节点
除了根节点外，每个内部节点至少有⌈m/2⌉个子节点
根节点至少有两个子节点（如果它不是叶子）
所有叶子节点都在同一层
每个节点包含k-1个关键字，对应k个子节点（k为子节点数）

C++中的B树节点设计

定义一个B树节点类，保存关键字、子节点指针和当前关键字数量。

// 简化的B树节点结构 template <typename T, int M> class BTreeNode { public: bool isLeaf; // 是否为叶子节点 int n; // 当前关键字数量 T keys[M - 1]; // 存储关键字（最多M-1个） BTreeNode* children[M]; // 子节点指针数组

BTreeNode(bool leaf) : isLeaf(leaf), n(0) {
    for (int i = 0; i < M; ++i)
        children[i] = nullptr;
}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

BibiGPT-哔哔终结者

B站视频总结器-一键总结音视频内容

查看详情

B树主类与插入操作

实现BTree类，包含插入、分裂、查找等核心方法。

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

void splitChild(BTreeNode<T, M>* parent, int i) {
    BTreeNode<T, M>* fullChild = parent->children[i];
    BTreeNode<T, M>* newNode = new BTreeNode<T, M>(fullChild->isLeaf);
    newNode->n = (M - 1) / 2;

    // 拷贝后半部分关键字到新节点
    for (int j = 0; j < newNode->n; ++j)
        newNode->keys[j] = fullChild->keys[j + (M / 2)];

    if (!fullChild->isLeaf) {
        // 如果是非叶子，复制子节点指针
        for (int j = 0; j <= newNode->n; ++j)
            newNode->children[j] = fullChild->children[j + (M / 2)];
    }

    // 调整原节点数量
    fullChild->n = (M - 1) / 2;

    // 将新节点插入父节点
    for (int j = parent->n; j > i; --j)
        parent->children[j + 1] = parent->children[j];

    parent->children[i + 1] = newNode;

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

    parent->keys[i] = fullChild->keys[(M / 2) - 1];
    parent->n++;
}

void insertNonFull(BTreeNode<T, M>* node, const T& key) {
    int i = node->n - 1;

    if (node->isLeaf) {
        // 找到插入位置并插入
        while (i >= 0 && node->keys[i] > key) {
            node->keys[i + 1] = node->keys[i];
            --i;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // 找到对应的子节点
        while (i >= 0 && node->keys[i] > key)
            --i;
        ++i;

        // 若子节点满，则先分裂
        if (node->children[i]->n == M - 1) {
            splitChild(node, i);
            if (node->keys[i] < key)
                ++i;
        }
        insertNonFull(node->children[i], key);
    }
}

登录后复制

public: BTree() { root = new BTreeNode<T, M>(true); }

void insert(const T& key) {
    BTreeNode<T, M>* r = root;

    // 根节点满时需分裂并创建新根
    if (r->n == M - 1) {
        BTreeNode<T, M>* s = new BTreeNode<T, M>(false);
        s->children[0] = r;
        root = s;
        splitChild(s, 0);
        insertNonFull(s, key);
    } else {
        insertNonFull(r, key);
    }
}</font>

登录后复制

查找功能实现

添加一个查找函数来验证插入是否正确。

bool search(const T& key, BTreeNode<T, M>* node = nullptr) { if (node == nullptr) node = root;

    int i = 0;
    while (i < node->n && key > node->keys[i])
        ++i;

    if (i < node->n && key == node->keys[i])
        return true;

    if (node->isLeaf)
        return false;

    return search(key, node->children[i]);
}</font>

登录后复制

这个实现支持任意可比较类型（如int、double），通过模板参数控制阶数。例如使用 BTree<int, 3> 创建一个3阶B树。

基本上就这些。插入和查找是B树最基础的操作，扩展可以加入遍历、删除等功能。注意内存管理在实际项目中应使用智能指针或析构函数清理节点。

以上就是C++如何实现一个简单的B树_C++数据结构与B树实现的详细内容，更多请关注php中文网其它相关文章！