CODEWITHSUNDEEP
c++calgorithmdata-structuresb-tree
Pedro
Pedro

Reputation: 331

B-Tree Node Splitting Techniques

I've stumbled upon a problem whilst doing my DSA (Data Structures and Algorithms) homework. I'm said to implement a B-Tree with Insertion and Search algorithms. As far as it goes, the search is working correctly, but I'm having trouble implementing the insertion function. Specifically the logic behind the B-Tree node-splitting algorithm. A pseudocode/C-style I could come up with is the following:

    #define D 2
    #define DD 2*D

    typedef btreenode* btree;
    typedef struct node
    {
        int keys[DD];  //D == 2 and DD == 2*D;
        btree pointers[DD+1];
        int index; //used to iterate throught the "keys" array
    }btreenode;

    void splitNode(btree* parent, btree* child1, btree* child2)
    {
        //Copies the content from the splitted node to the children
        (*child1)->key[0] = (*parent)->key[0];
        (*child1)->key[1] = (*parent)->key[1];
        (*child2)->key[0] = (*parent)->key[2];
        (*child2)->key[1] = (*parent)->key[3];
        (*child1)->index = 1;
        (*child2)->index = 1;
        //"Clears" the parent node from any data
        for(int i = 0; i<DD; i++) (*parent)->key[i] = -1;
        for(int i = 0; i<DD+1; i++) (*parent)->pointers[i] = NULL
        //Fixed the pointers to the children
        (*parent)->index = 0;
        //the line bellow was taken out for creating a new node  that didn't have to be there.
        //(*parent)->key[(*parent)->index] = newNode(); // The newNode() function allocs and inserts a the new key that I need to insert.
        (*parent)->pointers[index] = (*child1);
        (*parent)->pointers[index+1] = (*child2);
    }

I'm almost sure that I'm messing up something with the pointers, but I'm not sure what. Any help is appreciated. Maybe I need a little bit more study on the B-Tree subject? I must add that while I can use basic input/output from C++, I need to use C-style structs.

Upvotes: 0

Views: 1307

Answers (1)

user207421
user207421

Reputation: 310913

You don't need to create a new node here. You've apparently already created the two new child nodes. All you have to do here after populating the children is make the parent now point to the two children, via a copy of the first key in each of them, and adjust its key count to two. You don't need to set the parent keys to -1 either.

Upvotes: 1

Related Questions