c 言語 B tree
C言語で B-treeを実装するプログラムを書きました。
まだtreeに挿入する関数しか書いておりませんが。。
まず空の根を作ってからそこにどんどん要素を挿入していくのですが、どうも要素が
挿入されていないように思えます。
どこがいけないのか分かる方いらっしゃいませんか？
よろしくお願いします。
#include <stdio.h>
#define T 10
struct b_tree{
int key[2*T-1];
struct b_tree *node[2*T];
int size;
int leaf;//この節点が葉であったら1とする
};
void BTreeCreate(void);
void BTreeSplitChild(struct b_tree x,int i,struct b_tree y);
void BTreeInsert(struct b_tree t,int k);
void BTreeInsertNonfull(struct b_tree x,int k);
void PrintBtree(struct b_tree x);
struct b_tree root;
int main (int argc, const char * argv[]) {
// insert code here...
/*int t;*/
char command;
int key;
BTreeCreate();
/*scanf("%d",&t);*/
while (1) {
scanf("%c %d",&command,&key);
if (command=='E') break;
if(command=='I') BTreeInsert(root,key);//木にkeyを挿入
}
PrintBtree(root); //木を表示
return 0;
}
void BTreeCreate(void){//空のB-木の生成
struct b_tree x;
x.leaf=1;
x.size=0;
root=x;
}
void BTreeSplitChild(struct b_tree x,int i,struct b_tree y){
/*B-木における節点の分割をする節点xのi番目の枝の先にある節点yが飽和であった
場合にyをyの中央値で分ける。yの中央値はxの新たなkeyとなりxの枝数は１つ増える*/
int j;
struct b_tree z;
z.leaf=y.leaf; //zが葉であるかどうかはyが葉であるかどうかに依る
z.size=T-1; //また新しくできるxの子zは最小数のkey(T-1)を持たせる
for (j=1; j<= T-1; j++) {
z.key[j]=y.key[j+1]; //yの中央値よりおおきい値(T-1個)をzに渡す
}
if(y.leaf==0){ //またyが個をもつ場合は枝もzに渡す
for (j=1; j<=T; j++)
z.node[j]=y.node[T+j];
}
y.size=T-1; //そしてyのサイズも中央値とzに渡した分小さくなる
for (j= x.size+1; j>=i+1; j--) { //xにyの中央値を渡すのでx枝の右半分を1つずつ右へずらす
x.node[j+1]=x.node[j];
}
x.node[i+1]=&z; //i+1番目の枝に新たな子zのポインタを与える
for (j=x.size; j>=i; j--) { //値も右へずらす
x.key[j+1]=x.key[j];
}
x.key[i]=y.key[T]; //xのi番目の値をyの中央値とする。
x.size=x.size+1; //xは1サイズup
}
void BTreeInsert(struct b_tree t,int k){
int Tsub=T; //条件部にTが使えなかったのでTsubに退避
struct b_tree r,s;
r=t;
if (r.size == Tsub) {
/*根が飽和だった場合を考える新たな親を必要とするため
それをsとする。するとsは葉ではなく、sizeは0,
そして元々の根rのポインタを与える*/
s.leaf=0;
s.size=0;
s.node[1]=&r;
root=s;
BTreeSplitChild(s,1,r);
BTreeInsertNonfull(r,k);
}
else {
BTreeInsertNonfull(r,k);
}
}
void BTreeInsertNonfull(struct b_tree x,int k){
/*未飽和の節点xにkを挿入しようと考える。*/
int i;
int Tsub=T;
if (x.leaf==1) {
/*もし、xが葉であれば大小関係を考えて挿入。その際他のkey
を右へ1つずつずらす。またxのサイズを1up*/
while (i>=1 && k<x.key[i]) {
x.key[i+1]=x.key[i];
i--;
}
x.key[i+1]=k;
x.size++;
}
else {
/*もしxが葉でなければどこの枝をたどればいいのか考える*/
while (i>=1 && k<x.key[i]) {
i--;
}
i++;
if ((*x.node[i]).size == 2*Tsub-1) {
/*たどる枝の先が飽和であった場合分割する*/
BTreeSplitChild(x, i, *x.node[i]);
if (k > x.key[i]) {
i++;
}
}
BTreeInsertNonfull(*x.node[i],k);//枝をたどる
}
}
void PrintBtree(struct b_tree x){
printf("abc");
printf("%d",x.leaf);//実行するとleafが1のままなので、数が挿入されていない？
int i,l;
if(x.leaf==1){
for (i=1; i<=x.size; i++) {
printf("%d def",x.key[i]);
}
if(l==0)printf("\n");
}else {
for (i=1; i<=x.size; i++) {
printf("%d ghi",x.key[i]);
}
if(l==0)printf("\n");
l++;
printf(" jkl");
for (i=1; i <= x.size+1; i++) {
PrintBtree(*x.node[i]);
}
}
printf("\n");
}
お礼
ありがとう御座いました。 難しいですね。 頑張って理解します。