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");
}
補足
Tacosan様 回答ありがとうございます 返信おそくなり申し訳ありません。 また説明が不十分で失礼いたしました。 wordに入っている『要素』とは、図でいうところのサンプルとIDのことです。 同じ要素が出現、とは遠く離れたところでもよいです。 IDのindentの値とは、もっとも子ノードのIDのindentの値のことです。 indentが低いとは、値として小さいのほうです。 そのwordlistとは、indentが値として小さい値を持つwordの親のwordlistのことです。 先に出てきたところにくっつけたいとは、後ろにあるものを切り取って前のwordlistに移動するです。前のwordlistとは先に出現した要素のwordlistに移動したいと思っています もとのデータはxmlファイルでして、それをツリーノードに変換しています。