B-Tree потерять данные на вставке

Question

Я пытаюсь реализовать 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: 

Answer 1

Нашли проблему: Вкладыш работал нормально. Только я забыл установить статус «f» (полный) при установке чего-то на data2. Это привело к тому, что функция печати печатала неправильные вещи