请帮我设计一个C++程序,该程序的功能是有关各种搜索树效率比较,使用BST、AVL、B+树进行比较,要求拥有数组作为存储模块存储数据,时间模块进行计算各搜索树的时间,随机数生成模块进行随机数的生成并且传输给各搜索树进行计算,最后设计一个输出模块要求给出计算后的时间比较
时间: 2024-03-18 15:41:12 浏览: 62
基于C++进行B+树的模拟【100012527】
好的,我可以帮你设计一个C++程序,该程序可以比较BST、AVL、B+树的效率,并输出它们的时间比较结果。下面是程序的基本框架:
```cpp
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <chrono>
#include <vector>
#include "bst.h" // 包含BST的头文件
#include "avl.h" // 包含AVL的头文件
#include "bptree.h" // 包含B+树的头文件
using namespace std;
int main() {
int n; // 数据量
cout << "请输入数据量n:";
cin >> n;
// 随机生成n个数据
vector<int> data(n);
srand(time(0));
for (int i = 0; i < n; i++) {
data[i] = rand();
}
// BST
BST bst;
auto start = chrono::steady_clock::now();
for (int i = 0; i < n; i++) {
bst.insert(data[i]);
}
auto end = chrono::steady_clock::now();
chrono::duration<double> elapsed_seconds = end - start;
cout << "BST插入" << n << "个数据所需时间:" << elapsed_seconds.count() << "秒" << endl;
// AVL
AVL avl;
start = chrono::steady_clock::now();
for (int i = 0; i < n; i++) {
avl.insert(data[i]);
}
end = chrono::steady_clock::now();
elapsed_seconds = end - start;
cout << "AVL插入" << n << "个数据所需时间:" << elapsed_seconds.count() << "秒" << endl;
// B+树
BPTree bptree;
start = chrono::steady_clock::now();
for (int i = 0; i < n; i++) {
bptree.insert(data[i]);
}
end = chrono::steady_clock::now();
elapsed_seconds = end - start;
cout << "B+树插入" << n << "个数据所需时间:" << elapsed_seconds.count() << "秒" << endl;
return 0;
}
```
在这个程序中,我们使用了 `chrono` 库来计算各搜索树的时间,使用了 `vector` 存储随机生成的数据。同时,我们还需要实现BST、AVL和B+树的代码,可以参考以下代码:
```cpp
// BST
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class BST {
public:
BST() {
root = NULL;
}
void insert(int val) {
if (root == NULL) {
root = new TreeNode(val);
return;
}
TreeNode* cur = root;
while (cur != NULL) {
if (val < cur->val) {
if (cur->left == NULL) {
cur->left = new TreeNode(val);
return;
} else {
cur = cur->left;
}
} else {
if (cur->right == NULL) {
cur->right = new TreeNode(val);
return;
} else {
cur = cur->right;
}
}
}
}
private:
TreeNode* root;
};
// AVL
class AVL {
public:
AVL() {
root = NULL;
}
void insert(int val) {
root = insertHelper(root, val);
}
private:
struct TreeNode {
int val;
int height;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), height(1), left(NULL), right(NULL) {}
};
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
int getBalanceFactor(TreeNode* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
TreeNode* leftRotate(TreeNode* node) {
TreeNode* right = node->right;
TreeNode* left = right->left;
right->left = node;
node->right = left;
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
return right;
}
TreeNode* rightRotate(TreeNode* node) {
TreeNode* left = node->left;
TreeNode* right = left->right;
left->right = node;
node->left = right;
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
return left;
}
TreeNode* insertHelper(TreeNode* node, int val) {
if (node == NULL) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insertHelper(node->left, val);
} else {
node->right = insertHelper(node->right, val);
}
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0) {
return rightRotate(node);
}
if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0) {
return leftRotate(node);
}
if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
TreeNode* root;
};
// B+树
class BPTree {
public:
BPTree() {
// 初始化根节点
root = new BPNode();
root->isLeaf = true;
root->keyNum = 0;
}
void insert(int val) {
BPNode* curNode = root;
// 找到插入的叶子节点
while (!curNode->isLeaf) {
int i = 0;
while (i < curNode->keyNum && curNode->keys[i] <= val) {
i++;
}
curNode = curNode->children[i];
}
// 插入到叶子节点中
insertToNode(curNode, val);
// 调整B+树
while (curNode != root && curNode->keyNum == MAX_KEY_NUM) {
BPNode* parent = curNode->parent;
BPNode* newNode = splitNode(curNode);
insertToNode(parent, newNode->keys[0]);
newNode->parent = parent;
curNode = parent;
}
if (curNode == root && curNode->keyNum == MAX_KEY_NUM) {
BPNode* newNode = splitNode(curNode);
BPNode* newRoot = new BPNode();
newRoot->keys[0] = newNode->keys[0];
newRoot->children[0] = curNode;
newRoot->children[1] = newNode;
newRoot->keyNum = 1;
curNode->parent = newRoot;
newNode->parent = newRoot;
root = newRoot;
}
}
private:
static const int MAX_KEY_NUM = 4; // 每个节点最多存储的关键字数
static const int MIN_KEY_NUM = MAX_KEY_NUM / 2; // 每个节点最少存储的关键字数
static const int MAX_CHILD_NUM = MAX_KEY_NUM + 1; // 每个节点最多的孩子数
struct BPNode {
int keys[MAX_KEY_NUM];
BPNode* children[MAX_CHILD_NUM];
BPNode* parent;
int keyNum;
bool isLeaf;
BPNode() : keyNum(0), isLeaf(false) {}
};
void insertToNode(BPNode* node, int val) {
int i = node->keyNum - 1;
while (i >= 0 && node->keys[i] > val) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = val;
node->keyNum++;
}
BPNode* splitNode(BPNode* node) {
BPNode* newNode = new BPNode();
newNode->isLeaf = node->isLeaf;
int mid = node->keyNum / 2;
for (int i = mid + 1; i < node->keyNum; i++) {
newNode->keys[i - mid - 1] = node->keys[i];
newNode->children[i - mid - 1] = node->children[i];
if (node->children[i] != NULL) {
node->children[i]->parent = newNode;
}
}
newNode->children[node->keyNum - mid - 1] = node->children[node->keyNum];
if (node->children[node->keyNum] != NULL) {
node->children[node->keyNum]->parent = newNode;
}
node->keyNum = mid;
newNode->keyNum = node->keyNum;
if (node->parent != NULL) {
int i = node->parent->keyNum - 1;
while (i >= 0 && node->parent->children[i] != node) {
i--;
}
insertToNode(node->parent, node->keys[mid]);
node->parent->children[i + 1] = newNode;
}
return newNode;
}
BPNode* root;
};
```
在这个程序中,我们实现了BST、AVL和B+树的代码,其中B+树的实现比较复杂,需要注意。另外,代码中的 `bst.h`、`avl.h` 和 `bptree.h` 分别是BST、AVL和B+树的头文件,需要根据实际情况进行修改。
最后,运行程序,输入数据量n,程序会自动随机生成n个数据,然后分别计算BST、AVL和B+树的插入时间,并输出时间比较结果。你可以根据需要对代码进行修改和扩展,以满足更多的需求。
阅读全文