这是我在 B-Tree 中插入到第一级的代码。我正在创建 1 阶的 B-Tree，即 2 个键值和 3 个指针。
现在，当我根据 B-tree 算法添加 //6（见 main ）时，9 应该出现在父节点的最右边，但问题是程序运行后父节点最右边的 ptr 为 NULL，它不应该是。任何线索为什么会发生？
#include<iostream>
using namespace std;
const int d=1;
struct Btree{
public:
int key[2*d];
int count;
Btree *ptr[2*d+1];
Btree *pptr;
};
//for filling the B-Tree with values of array a starting from x till y.
void fill_n(Btree *N,int a[],int x,int y){
int g=0;
for(int i=x;i<y;i++){
N->key[g]=a[i];
N->count++;
g++;
}
}
//for sorting parent node
void sort_parent(Btree*&T){
Btree *a[2*d+2];
//creating an array of B-Tree pointers and storing the parent pointers
//before sorting it
for(int i=0;i<2*d+1;i++){
a[i]=T->ptr[i];
}
//for sorting and adjusting pointers accordingly
for(int j=0;j<2*d-1;j++){
for(int k=j+1;k<2*d;k++){
if(T->key[j]>T->key[k]&&T->key[j]!=-1&&T->key[k]!=-1){
Btree *P;
int x;
x=T->key[j];
T->key[j]=T->key[k];
T->key[k]=x;
P=a[j];
a[j]=a[k];
a[k]=P;
if(k+1<=2*d){
P=a[j+1];
a[j+1]=a[k+1];
a[k+1]=P;
}
}
}
}
//for assiging pointers accordingly
for(int k=0;k<2*d+1;k++)
T->ptr[k]=a[k];
}
//for assigning initial values to tree
void new_tree(Btree *&T){
for(int i=0;i<2*d;i++){
T->key[i]=-1;
T->ptr[i]=NULL;
}
T->ptr[2*d]=NULL;
T->count=0;
T->pptr=NULL;
}
//for sorting an array of elements
void sort_a(int a[]){
for(int i=0;i<(2*d);i++){
for(int j=i+1;j<2*d+1;j++){
if(a[i]>a[j]){
int x=a[i];
a[i]=a[j];
a[j]=x;
}
}
}
}
//for spliting the leaf node
void split(Btree *&T,int x){
int a[2*d+1];
//adding elements to array
for(int i=0;i<2*d;i++)
a[i]=T->key[i];
a[2*d]=x;
//sorting array
sort_a(a);
//creating parent if doesn't exist.
if(T->pptr==NULL)
{
T->pptr=new(Btree);
new_tree(T->pptr);
}
T=T->pptr;
//if parent is not full add to it.
if(T->count<2*d){
//passing middle element of array to parent to add i.e. a[d]
T->key[T->count]=a[d];
T->count++;
//sorting of parent node
sort_parent(T);
int i=0;
for(i=0;i<T->count;i++){
if(T->key[i]==a[d])
break;//giving the index where the a[d] is added in parent node
}
Btree*C1;
C1=new(Btree);
Btree *C2;
C2=new(Btree);
new_tree(C1);
new_tree(C2);
//adding elements before middle element into C1
fill_n(C1,a,0,d);
//adding elements after middle element into C2
fill_n(C2,a,d+1,2*d+1);
//assigning the ptr left to key of parent as C1 and right as C2
T->ptr[i]=C1;
T->ptr[i+1]=C2;
C1->pptr=T;
C2->pptr=T;
}
else{
//add here the parent spliting
}
}
//for sorting of leaf node
void sort(Btree *&T){
for(int i=0;i<T->count-1;i++){
for(int j=i+1;j<T->count;j++){
if(T->key[i]>T->key[j])
{
int x=T->key[i];
T->key[i]=T->key[j];
T->key[j]=x;
}
}
}
}
//for adding into B-Tree
void add_simple(Btree*&T,int x){
//if leaf is not full
if(T->count<2*d){
T->key[T->count]=x;
T->count++;
sort(T);
}
else{
//node spliting if leaf is full
split(T,x);
}
}
//for finding place for adding into B-Tree
void add(Btree *&B,int x){
//if leaf node
if(B->ptr[0]==NULL)
add_simple(B,x);
else{
//search upto appropriate leaf node
int i=0;
while(i<2*d&&x>B->key[i]&&B->key[i]!=-1)
i++;
cout<<i<<endl;
//recursion
add(B->ptr[i],x);
}
}
int main(){
Btree *B;
B=new(Btree);
new_tree(B);
add(B,6);//1
add(B,3);//2
add(B,9);//3
add(B,4);//4
add(B,8);//5
add(B,7);//6
//for checking purpose
cout<<B->key[0]<<endl;
cout<<B->key[1]<<endl;
cout<<B->ptr[0]->key[0]<<endl;
cout<<B->ptr[1]->key[0]<<endl;
//problem is here according to algorithm it should give 9 but
//if you check B->ptr[2] is NULL
//remove the comment from next statement to check
// cout<<B->ptr[2]->key[0]<<endl;
return 0;
}