请帮我用C++写一个B-tree程序,内容包括:B-tree的结构、B-tree的创建、插入若干个关键字、查找指定关键字、找出树中最大的K个值
时间: 2024-01-24 10:05:07 浏览: 29
好的,B-tree是一种多叉树,节点可以有多个子节点,用于高效地存储和查找大量数据。下面是一个简单的B-tree程序的实现:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 4; // B-tree的阶数
struct BNode {
vector<int> keys; // 存储关键字
vector<BNode*> children; // 存储子节点指针
bool is_leaf; // 是否是叶子节点
BNode() {
keys.resize(M - 1);
children.resize(M, nullptr);
is_leaf = true;
}
};
class BTree {
public:
BTree() {
root = new BNode();
}
~BTree() {
clear(root);
}
void insert(int key) {
if (root->keys.size() == M - 1) { // 根节点已满
BNode *new_root = new BNode();
new_root->is_leaf = false;
new_root->children[0] = root;
split_child(new_root, 0, root);
root = new_root;
}
insert_nonfull(root, key);
}
bool search(int key) {
return search_node(root, key) != nullptr;
}
vector<int> find_k_largest(int k) {
vector<int> result;
find_k_largest(root, k, result);
return result;
}
private:
BNode *root;
void split_child(BNode *node, int i, BNode *child) {
BNode *new_node = new BNode();
new_node->is_leaf = child->is_leaf;
// 将子节点的后一半移动到新节点
for (int j = 0; j < M / 2 - 1; j++) {
new_node->keys[j] = child->keys[M / 2 + j];
}
if (!child->is_leaf) {
for (int j = 0; j < M / 2; j++) {
new_node->children[j] = child->children[M / 2 + j];
}
}
// 更新原节点和父节点
child->keys.resize(M / 2 - 1);
if (!child->is_leaf) {
child->children.resize(M / 2);
}
node->children.resize(node->keys.size() + 2);
for (int j = node->keys.size() + 1; j > i + 1; j--) {
node->children[j] = node->children[j - 1];
}
node->children[i + 1] = new_node;
for (int j = node->keys.size(); j > i; j--) {
node->keys[j] = node->keys[j - 1];
}
node->keys[i] = child->keys[M / 2 - 1];
}
void insert_nonfull(BNode *node, int key) {
int i = node->keys.size() - 1;
if (node->is_leaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
} else {
while (i >= 0 && key < node->keys[i]) {
i--;
}
i++;
if (node->children[i]->keys.size() == M - 1) {
split_child(node, i, node->children[i]);
if (key > node->keys[i]) {
i++;
}
}
insert_nonfull(node->children[i], key);
}
}
BNode *search_node(BNode *node, int key) {
int i = 0;
while (i < node->keys.size() && key > node->keys[i]) {
i++;
}
if (i < node->keys.size() && key == node->keys[i]) {
return node;
} else if (node->is_leaf) {
return nullptr;
} else {
return search_node(node->children[i], key);
}
}
void find_k_largest(BNode *node, int k, vector<int> &result) {
if (node == nullptr) {
return;
}
if (node->is_leaf) {
for (int i = node->keys.size() - 1; i >= 0 && result.size() < k; i--) {
result.push_back(node->keys[i]);
}
} else {
for (int i = node->keys.size() - 1; i >= 0; i--) {
find_k_largest(node->children[i + 1], k, result);
if (result.size() == k) {
return;
}
result.push_back(node->keys[i]);
}
find_k_largest(node->children[0], k, result);
}
}
void clear(BNode *node) {
if (node == nullptr) {
return;
}
for (int i = 0; i < node->children.size(); i++) {
clear(node->children[i]);
}
delete node;
}
};
int main() {
BTree tree;
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(6);
tree.insert(4);
tree.insert(10);
tree.insert(1);
cout << tree.search(5) << endl;
cout << tree.search(2) << endl;
vector<int> result = tree.find_k_largest(3);
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
```
以上代码中,BNode表示B-tree的节点,包括存储关键字的keys、存储子节点指针的children和标识是否是叶子节点的is_leaf。BTree表示B-tree数据结构,包括插入关键字、查找关键字、找出树中最大的K个值等操作。关键的实现是插入操作和查找操作,都是通过递归实现的。另外,找出树中最大的K个值的操作也是通过递归实现,先找到最右边的叶子节点,然后依次向上遍历,找到前K大的关键字。