c++怎么实现一个B树_c++平衡树数据结构B树实现过程

// 拷贝后半部分关键字
for (int i = 0; i < newNode->n; ++i) {
    newNode->keys[i] = fullNode->keys[(M + 1) / 2 + i];
}

if (!fullNode->isLeaf) {
    for (int i = 0; i <= newNode->n; ++i) {
        newNode->children[i] = fullNode->children[(M + 1) / 2 + i];
    }
}

// 中间关键字上移
for (int i = parent->n; i > idx; --i) {
    parent->children[i + 1] = parent->children[i];
}
parent->children[idx + 1] = newNode;

for (int i = parent->n - 1; i >= idx; --i) {
    parent->keys[i + 1] = parent->keys[i];
}
parent->keys[idx] = fullNode->keys[(M - 1) / 2];
parent->n++;

fullNode->n = (M - 1) / 2;

}

template void BTree::insertNonFull(BTreeNode* node, const T& key) { int i = node->n - 1; if (node->isLeaf) { while (i >= 0 && key keys[i]) { node->keys[i + 1] = node->keys[i]; --i; } node->keys[i + 1] = key; node->n++; } else { while (i >= 0 && key keys[i]) --i; ++i; if (node->children[i]->n == M - 1) { splitChild(node, i); if (key > node->keys[i]) ++i; } insertNonFull(node->children[i], key); } }

template void BTree::insert(const T& key) { if (root == nullptr) { root = new BTreeNode(); root->keys[0] = key; root->n = 1; return; }

if (root->n == M - 1) {
    auto newRoot = new BTreeNode();
    newRoot->isLeaf = false;
    newRoot->children[0] = root;
    splitChild(newRoot, 0);
    root = newRoot;
}
insertNonFull(root, key);

}

5. 遍历与查找
中序遍历输出所有元素，查找类似二叉搜索树：
```cpp
template
void BTree::traverseNode(BTreeNode* node) {
    if (node) {
        int i = 0;
        for (; i < node->n; ++i) {
            if (!node->isLeaf) {
                traverseNode(node->children[i]);
            }
            std::cout << node->keys[i] << " ";
        }
        if (!node->isLeaf) {
            traverseNode(node->children[i]);
        }
    }
}

template
void BTree::traverse() {
    traverseNode(root);
    std::cout << std::endl;
}

template
BTreeNode* BTree::search(BTreeNode* node, const T& key) {
    int i = 0;
    while (i < node->n && key > node->keys[i]) ++i;

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

    if (node->isLeaf) return nullptr;

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

template
BTreeNode* BTree::search(const T& key) {
    return root ? search(root, key) : nullptr;
}

6. 使用示例

测试代码：

btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(6);
btree.insert(12);
btree.insert(30);

std::cout << "Traverse: ";
btree.traverse();  // 输出: 5 6 10 12 20 30

auto node = btree.search(12);
if (node) {
    std::cout << "Found 12\n";
}

return 0;

基本上就这些。B树通过分裂维持平衡，插入复杂度为O(log N)，适合大规模有序数据管理。实现时注意边界条件和指针管理，避免内存泄漏。