9-8（拓展） Self-printable B+ Tree
分数 35
作者 魏宝刚
单位 浙江大学
In this project, you are supposed to implement a B+ tree of order 3, with the following operations: initialize, insert (with splitting) and search. The B+ tree should be able to print out itself.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive number N (≤10
4
), the number of integer keys to be inserted. Then a line of the N positive integer keys follows. All the numbers in a line are separated by spaces.
Output Specification:
For each test case, insert the keys into an initially empty B+ tree of order 3 according to the given order. Print in a line Key X is duplicated where X already exists when being inserted. After all the insertions, print out the B+ tree in a top-down lever-order format as shown by the samples.
Sample Input 1:
6
7 8 9 10 7 4
Sample Output 1:
Key 7 is duplicated
[9]
[4,7,8][9,10]
Sample Input 2:
10
3 1 4 5 9 2 6 8 7 0
Sample Output 2:
[6]
[2,4][8]
[0,1][2,3][4,5][6,7][8,9]
Sample Input 3:
3
1 2 3
Sample Output 3:
[1,2,3]
n取最大值的测试点一直过不去，请问是哪里出了问题
#include
using namespace std;
typedef struct B_Tree
{
int key[4];//存储关键值
int chl[5],pa;//存储孩子和父节点
int num;//存储该节点中的关键值数
int id;//存储该节点的编号
int next,last;//若该节点是叶节点，则存储由叶节点组成的链表中自己所在位置的前一个节点的编号和后一个节点的编号
} B;
B b[200001];
int m=1;//标记目前b数组存储到了哪里
int le=0;//存储叶节点链表表头的编号
void print_b(int k)//输出
{
queuev;//存储编号
v.push(k);
int k2=b[k].num+1,k1=1,k3=0;//k1存储目前正在输出的这行有多少个节点，k2存储目前输出的这行的孩子总数，k3负责计算目前输出的这行的孩子的孩子总数
//cout << k1 << ' ' << k2 << ' ' << k3 << endl;
while(b[v.front()].num)
{
int t=v.front();
v.pop();
k1--;
bool flag=false;
cout << '[' << b[t].key[0];
v.push(b[t].chl[0]);
k3+=b[b[t].chl[0]].num+1;
for(int i=1; i',' << b[t].key[i];
v.push(b[t].chl[i]);
k3+=b[b[t].chl[i]].num+1;
}
if(b[t].num)
{
v.push(b[t].chl[b[t].num]);
k3+=b[b[t].chl[b[t].num]].num+1;
}
if(!k1)
{
k1=k2;
k2=k3;
k3=0;
flag=true;
}
cout << ']';
//cout << k1 << ' ' << k2 << ' ' << k3;
if(flag)cout << endl;
}
}
void cut_ro(int k)//若非叶节点的关键值数量达到3
{
if(b[k].pa==-1)//该节点为根节点
{
b[m].pa=b[m+1].pa=k;
b[m].key[0]=b[k].key[0];
b[m].chl[0]=b[k].chl[0];
b[m].chl[1]=b[k].chl[1];
b[b[k].chl[0]].pa=b[b[k].chl[1]].pa=m;
b[m+1].key[0]=b[k].key[2];
b[m+1].chl[0]=b[k].chl[2];
b[m+1].chl[1]=b[k].chl[3];
b[b[k].chl[2]].pa=b[b[k].chl[3]].pa=m+1;
b[k].key[0]=b[k].key[1];
b[k].chl[0]=m;
b[k].chl[1]=m+1;
//b[m].pa=b[m+1].pa=head.id;
b[m].num=b[m+1].num=1;
b[k].num=1;
m+=2;
return;
}
b[m].num=1;
b[k].num=1;
b[m].key[0]=b[k].key[2];
b[m].chl[1]=b[k].chl[3];
b[m].chl[0]=b[k].chl[2];
b[b[k].chl[2]].pa=b[b[k].chl[3]].pa=m;
b[m].pa=b[k].pa;
int i;
int h=b[k].pa;
for(i=0; ib[k].key[1])break;
}
for(int j=b[h].num; j>i; j--)b[h].key[j]=b[h].key[j-1];
b[h].key[i]=b[k].key[1];
b[h].num++;
for(int j=b[h].num; j>i+1; j--)b[h].chl[j]=b[h].chl[j-1];
b[h].chl[i+1]=m;
m++;
if(b[h].num==3)cut_ro(h);
}
void cut_le(int k)//若叶节点的关键值数达到4
{
if(b[k].pa==-1)//若该节点为根节点，则继续让该节点为根节点，b[m],b[m+1]两个节点为该节点分裂后的两个节点
{
b[m].pa=b[m+1].pa=b[k].id;
b[m].key[0]=b[k].key[0];
b[m].key[1]=b[k].key[1];
b[m+1].key[0]=b[k].key[2];
b[m+1].key[1]=b[k].key[3];
b[m].chl[0]=b[k].chl[0];
b[m].chl[1]=b[k].chl[1];
b[m].chl[2]=b[k].chl[2];
b[b[k].chl[0]].pa=b[b[k].chl[1]].pa=b[b[k].chl[2]].pa=m;
b[m+1].chl[0]=b[k].chl[3];
b[m+1].chl[1]=b[k].chl[4];
b[m+1].chl[2]=m+2;
b[m+2].pa=b[b[k].chl[3]].pa=b[b[k].chl[4]].pa=m+1;
b[k].num=1;
b[k].key[0]=b[k].key[2];
b[k].chl[0]=m;
b[k].chl[1]=m+1;
b[m].num=b[m+1].num=2;
if(k==le)le=m;
b[m].last=b[k].last;
b[m+1].last=m;
b[m].next=m+1;
b[m+1].next=b[k].next;
//print_b(head.id);
//cout << b[m]
m+=3;
return;
}
//令b[m]为该节点分裂后的后半部分
b[m].num=2;
b[k].num=2;
b[m].key[0]=b[k].key[2];
b[m].key[1]=b[k].key[3];
b[m].chl[0]=b[k].chl[3];
b[m].chl[1]=b[k].chl[4];
b[m+1].pa=b[b[k].chl[3]].pa=b[b[k].chl[4]].pa=m;
b[m].chl[2]=m+1;
b[m].pa=b[k].pa;
b[m].last=k;
b[m].next=b[k].next;
b[k].next=m;
int h=b[k].pa;
//cout << h << endl;
int i;
for(i=0; ib[k].key[2])break;
}
//cout << '#' << endl;
//print_b(h);
for(int j=b[h].num; j>i; j--)b[h].key[j]=b[h].key[j-1];
b[h].key[i]=b[k].key[2];
//cout << '@';
//for(int i=0;i1;i++)cout << b[h].key[i] << ' ';
//cout << endl;
b[h].num++;
for(int j=b[h].num; j>i+1; j--)b[h].chl[j]=b[h].chl[j-1];
b[h].chl[i+1]=m;
m++;
if(b[h].num==3)cut_ro(h);
}
void insert_b(int k,int x)//将x插入该节点
{
if(b[k].num==0)//只有在插入输入的第一个值时，才会有这种情况，直接插入即可
{
b[k].key[0]=x;
//cout << b[k].num << endl;
b[k].num+=1;
b[k].chl[0]=m;
b[k].chl[1]=m+1;
//cout << b[k].num << endl;
//cout << b[m].pa << endl;
b[m].pa=k;
//cout << b[m].num << endl;
b[m+1].pa=k;
//cout << b[m+1].num << endl;
m+=2;
//cout << m << endl;
//return;
}
else
{
//cout << x << endl;
int i;
for(i=0; ix)break;
}
//cout << i << endl;
for(int j=b[k].num; j>i; j--)b[k].key[j]=b[k].key[j-1];
b[k].key[i]=x;
b[m].num=0;
b[m].pa=k;
b[k].num++;
b[k].chl[b[k].num]=m;
m++;
//cout << m << endl;
//cout << b[k].num << ' ' << x << endl;
if(b[k].num==4)cut_le(k);
}
}
bool find_b(int k,int x)//查找x是否出现过，并查找x可插入的节点或其出现的位置
{
// if(b[k].num==0)
// {
// if(b[k].pa==-1)
// {
// insert_b(k,x);
// }
// else
// {
// //cout << x << ' ' << b[k].pa << endl;
// insert_b(b[k].pa,x);
// }
// //cout << '#' << endl;
// //print_b(0);
// return false;
// }
// for(int i=0; ix)
// {
// //cout << b[k].key[i] << ' ' << x << endl;
// return find_b(b[k].chl[i],x);
// }
// }
// //cout << b[k].chl[b[k].num] << endl;
// return find_b(b[k].chl[b[k].num],x);
int i;
for(i=le;;)//i表示叶节点编号
{
for(int j=0;jx)
{
if(j||b[i].last==-1)insert_b(i,x);//应尽量靠左插入，所以只有当该节点是叶节点链表的表头或者与x进行比较的值并不是该节点的第一个时才能将x插入该节点
else insert_b(b[i].last,x);
//print_b(0);
//cout << '#' << endl;
return false;
}
else if(b[i].key[j]==x)//若x已经输入过了则返回true
{
return true;
}
}
if(b[i].next==-1)break;
i=b[i].next;
}
insert_b(i,x);//若一直没有找到x并且也没有比x大的值则将x插入叶节点链表的表尾节点
//print_b(0);
//cout << '#' << endl;
return false;
}
int main()
{
int n;
cin >> n;
for(int i=0; i<200000; i++)//初始化
{
b[i].id=i;
b[i].pa=-1;
b[i].num=0;
b[i].next=b[i].last=-1;
}
for(int i=0; i> x;
if(find_b(0,x))
{
cout << "Key " << x << " is duplicated" << endl;
}
}
if(n)print_b(0);
return 0;
}
```