Bツリーを実装しようとしています。6番目の要素を挿入すると、新しく作成された2つのノードを除くすべてが失われ、葉とそれらの中間値が分割されます。
これが私のコードです：
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
int data2;
char status; //n not full, f full
struct node* left;
struct node* middle;
struct node* right;
};
typedef struct node NODE;
struct returnPackage { //used when a node is split
int value;
NODE* newNode1;
NODE* newNode2;
};
typedef struct returnPackage RTNPKG;
// Prototypes
NODE* createNode(int);
void gap(int);
void printNode(NODE*, int);
void printTree(NODE*);
RTNPKG* insert(NODE*, int);
// End of Prototypes
NODE* createNode(int value){
NODE* ptr = (NODE*) malloc(sizeof(NODE));
ptr->data = value;
ptr->status = 'n';
ptr->left = NULL;
ptr->middle = NULL;
ptr->right = NULL;
return ptr;
}
void gap(int level){
int i;
for(i = 1; i <=level; i++){
printf("│ ");
}
}
void printNode(NODE* t, int indent){
if(t == NULL){
return;
}
if (t->left == NULL){ //leaf
if(t->status == 'f'){
gap(indent);
printf("[%-2d, %-2d]\n", t->data, t->data2);
} else {
gap(indent);
printf("[%-2d|--]\n", t->data);
}
} else if(t->status == 'f'){
gap(indent), printf("┌\n");
printNode(t->left, indent + 1);
gap(indent), printf("├%d>\n", t->data);
printNode(t->middle, indent + 1);
gap(indent), printf("├%-2d>\n", t->data2);
printNode(t->right, indent + 1);
gap(indent), printf("└\n");
} else {
gap(indent), printf("┌\n");
printNode(t->left, indent + 1);
gap(indent), printf("├%-2d>\n", t->data);
printNode(t->middle, indent + 1);
gap(indent), printf("└\n");
}
}
void printTree(NODE* root){ //good? NOPE FUCKING BAD
if(root == NULL){
printf("Empty tree\n");
}
printNode(root, 0);
printf("\n");
}
RTNPKG* insert(NODE* t, int value){
printf("beginning of insert\n");
if(t->left == NULL){ //Leaf
printf("leaf\n"); //DEBUG
if(t->status == 'n' && t->data != value){ // there is room each value only ONCE
printf("leaf room\n"); //DEBUG
if(t->data < value){
t->data2 = value;
} else { // swap them
int temp = t->data;
t->data = value;
t->data2 = temp;
}
t->status = 'f';
return NULL; //nothing to do on parent
} else { // no room, determine middle value and return that
printf("leaf no room before bubble\n"); //DEBUG
if(value != t->data && value != t->data2){ //each value only ONCE
int a[3] = {t->data, t->data2, value};
if(a[0]>a[1]){
int temp = a[0];
a[0] = a[1];
a[1] = temp;
}
if(a[1]>a[2]){
int temp = a[1];
a[1] = a[2];
a[2] = temp;
}
if(a[0]>a[1]){
int temp = a[0];
a[0] = a[1];
a[1] = temp;
}
printf("leaf no room %i %i %i\n", a[0], a[1], a[2]); //DEBUG
//create the 2 new nodes resulting of the split
NODE* newNode1 = createNode(a[0]);
NODE* newNode2 = createNode(a[2]);
//prepare the returnpkg
RTNPKG* pkg = (RTNPKG*) malloc(sizeof(RTNPKG));
pkg->value = a[1];
pkg->newNode1 = newNode1;
pkg->newNode2 = newNode2;
return pkg;
}
return NULL; //value already exists. Upper nodes will just do nothing
}
} else { //no leaf, pass the value down
printf("no leaf\n"); //DEBUG
if(t->status == 'n'){ //only one data item, compare only to that
printf("no leaf space\n"); //DEBUG
RTNPKG* pkg;
if(t->data < value){
pkg = insert(t->middle, value);
if(pkg != NULL){ // if package is NULL we don't need to do anything, see above
// NOTE that we have room for sure, since status is n
printf("got %i back from middle\n", pkg->value); //DEBUG
printf("newNode1 value: %i newNode2 value: %i", pkg->newNode1->data, pkg->newNode2->data) //DEBUG
t->middle = pkg->newNode1;
t->right = pkg->newNode2;
t->data2 = pkg->value;
//clean memory
free(pkg);
}
return NULL;
} else {
pkg = insert(t->left, value);
if(pkg != NULL){ // if package is NULL we don't need to do anything, see above
// NOTE that we have room for sure, since status is n
printf("got %i back from left\n", pkg->value); //DEBUG
t->left = pkg->newNode1;
t->right = t->middle;
t->middle = pkg->newNode2;
t->data2 = t->data;
t->data = pkg->value;
//clean memory
free(pkg);
}
return NULL;
}
} else { // if something comes back we will NOT have room for it.
printf("no leaf no space\n"); //DEBUG
if(t->data < value){
if(t->data2 < value){
RTNPKG* pkg = insert(t->right, value);
if(pkg != NULL){
printf("no space got %i back from right\n", pkg->value); //DEBUG
//left node
NODE* newNode1 = createNode(t->data);
newNode1->left = t->left;
newNode1->middle = t->middle;
//right node
NODE* newNode2 = createNode(pkg->value);
newNode2->left = pkg->newNode1;
newNode2->middle = pkg->newNode2;
free(pkg); //not needed anymore
RTNPKG* rpkg = (RTNPKG*) malloc(sizeof(RTNPKG));
rpkg->value = t->data2;
rpkg->newNode1 = newNode1;
rpkg->newNode2 = newNode2;
return rpkg;
}
} else {
RTNPKG* pkg = insert(t->middle, value);
if(pkg != NULL){
printf("no space got %i back from middle\n", pkg->value); //DEBUG
//create the 2 new nodes resulting of the split
NODE* newNode1 = createNode(t->data);
newNode1->left = t->left;
newNode1->middle = pkg->newNode1;
NODE* newNode2 = createNode(t->data2);
newNode2->middle = t->right;
newNode2->left = pkg->newNode2;
//prepare the returnpkg
RTNPKG* rpkg = (RTNPKG*) malloc(sizeof(RTNPKG));
rpkg->value = pkg->value;
rpkg->newNode1 = newNode1;
rpkg->newNode2 = newNode2;
return rpkg;
}
}
} else {
RTNPKG* pkg = insert(t->left, value);
if(pkg != NULL){
printf("no space got %i back from left\n", pkg->value); //DEBUG
//left node
NODE* newNode1 = createNode(pkg->value);
newNode1->left = pkg->newNode1;
newNode1->middle = pkg->newNode2;
//right node
NODE* newNode2 = createNode(t->data2);
newNode2->left = t->middle;
newNode2->middle = t->right;
free(pkg); //not needed anymore
RTNPKG* rpkg = (RTNPKG*) malloc(sizeof(RTNPKG));
rpkg->value = t->data;
rpkg->newNode1 = newNode1;
rpkg->newNode2 = newNode2;
return rpkg;
}
}
}
}
}
void main(){
NODE* root = NULL;
int value;
while(1){
printf("Give me a value to insert in the tree:");
while (scanf("%d", &value) != 1)
{
while (getchar() != '\n');
printf ("Try again: ");
}
printf("Got: %d\n", value);
if(root != NULL){
RTNPKG* pkg = insert(root, value);
if(pkg != NULL){
printf("got %i back root\n", pkg->value); //DEBUG
root = createNode(pkg->value);
root->left = pkg->newNode1;
root->middle = pkg->newNode2;
}
} else {
root = createNode(value);
}
printTree(root);
}
}
これが私に与える出力です。11 を挿入すると、1、10、11 しかなく、50 と 100 が失われることがわかります。ツリーは次のようになります。
10 50
/ | \
1 11 100
これは出力です：
Give me a value to insert in the tree:10
Got: 10
beginning of insert
no leaf
no leaf space
beginning of insert
leaf
leaf room
┌
│ [1 , 10]
├50>
│ [100|--]
└
Give me a value to insert in the tree:11
Got: 11
beginning of insert
no leaf
no leaf space
beginning of insert
leaf
leaf no room before bubble
leaf no room 1 10 11
got 10 back from left
┌
│ [1 |--]
├10>
│ [11|--]
└
Give me a value to insert in the tree: