数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时装研究
法律研究C++ 程序来实现 B+ 树
B+ 树是二叉查找树的一个推广，因为它的一个结点可以有大于两个的孩子。它基本上是一种自平衡树数据结构，它维护已排序的数据，并允许以对数时间进行顺序访问、搜索、插入和删除。
它可以看作是一棵 B 树，它的每个结点只包含键，并且在底部添加了一层具有链接的叶结点。
算法
Begin function insert() to insert the nodes into the tree: Initialize x as root. if x is leaf and having space for one more info then insert a to x. else if x is not leaf, do Find the child of x that is going to to be traversed next. If the child is not full, change x to point to the child. If the child is full, split it and change x to point to one of the two parts of the child. If a is smaller than mid key in the child, then set x as first part of the child. Else second part of the child. End
示例代码
#include<iostream>
using namespace std;
struct BplusTree {
int *d;
BplusTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
BplusTree* init()//to create nodes {
int i;
np = new BplusTree;
np->d = new int[6];//order 6
np->child_ptr = new BplusTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(BplusTree *p)//traverse tree {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout << " " << p->d[i];
}
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n)//sort the tree {
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j <= n; j++) {
if (p[i] >p[j]) {
t = p[i];
p[i] = p[j];
p[j] = t;
}
}
}
}
int split_child(BplusTree *x, int i) {
int j, mid;
BplusTree *np1, *np3, *y;
np3 = init();
np3->l = true;
if (i == -1) {
mid = x->d[2];
x->d[2] = 0;
x->n--;
np1 = init();
np1->l = false;
x->l = true;
for (j = 3; j < 6; j++) {
np3->d[j - 3] = x->d[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->d[j] = 0;
x->n--;
}
for (j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->d[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
r = np1;
} else {
y = x->child_ptr[i];
mid = y->d[2];
y->d[2] = 0;
y->n--;
for (j = 3; j <6 ; j++) {
np3->d[j - 3] = y->d[j];
np3->n++;
y->d[j] = 0;
y->n--;
}
x->child_ptr[i + 1] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a) {
int i, t;
x = r;
if (x == NULL) {
r = init();
x = r;
} else {
if (x->l== true && x->n == 6) {
t = split_child(x, -1);
x = r;
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->l == false) {
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 6) {
t = split_child(x, i);
x->d[x->n] = t;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->d[x->n] = a;
sort(x->d, x->n);
x->n++;
}
int main() {
int i, n, t;
cout<<"enter the no of elements to be inserted\n";
cin>>n;
for(i = 0; i < n; i++) {
cout<<"enter the element\n";
cin>>t;
insert(t);
}
cout<<"traversal of constructed B tree\n";
traverse(r);
}输出
enter the no of elements to be inserted 10 enter the element 10 enter the element 20 enter the element 30 enter the element 40 enter the element 50 enter the element 60 enter the element 70 enter the element 80 enter the element 90 enter the element 100 traversal of constructed B tree 10 20 30 40 50 60 70 80 90 100
更新于：30-7 月 -2019
3K+次浏览
广告