資料結構
網路
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+次瀏覽
廣告