c - B 树在插入时丢失数据

Question

我正在尝试实现 B 树。当插入第 6 个元素时，除了新创建的 2 个节点之外，我丢失了所有内容，导致叶子和它们的中间值 split 。

这是我的代码:

#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

发现问题:插入物工作得很好。只是我在 data2 上设置某些内容时忘记将状态设置为“f”(完整)。这导致打印功能打印错误的内容