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.

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

Are you allowed to use classes?

– Casey
Jun 27 '14 at 18:13

@Casey - have a look at the last line: I must add that while I can use basic input/output from C++, I need to use C-style structs.

– haneefmubarak
Jun 27 '14 at 18:18

Technically yes, but I know close to nothing about OOP. I mean, I can read code and understand, but I somehow lack the knowledge to write OOP Code. If you have a solution that uses classes, I'll be happy to read it.

– Pedro
Jun 27 '14 at 18:19

@haneefmubarak It's ok, but thanks for noting!

– Pedro
Jun 27 '14 at 18:21

Yep! No problem.

– haneefmubarak
Jun 27 '14 at 18:21

add a comment |

    #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);

    }

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

Are you allowed to use classes?

– Casey
Jun 27 '14 at 18:13

@Casey - have a look at the last line: I must add that while I can use basic input/output from C++, I need to use C-style structs.

– haneefmubarak
Jun 27 '14 at 18:18

Technically yes, but I know close to nothing about OOP. I mean, I can read code and understand, but I somehow lack the knowledge to write OOP Code. If you have a solution that uses classes, I'll be happy to read it.

– Pedro
Jun 27 '14 at 18:19

@haneefmubarak It's ok, but thanks for noting!

– Pedro
Jun 27 '14 at 18:21

Yep! No problem.

– haneefmubarak
Jun 27 '14 at 18:21

add a comment |

    #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);

    }

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

    #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);

    }

c++ c algorithm data-structures b-tree

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

edited Nov 20 '18 at 2:11

Cœur

18k9108147

edited Nov 20 '18 at 2:11

Cœur

18k9108147

edited Nov 20 '18 at 2:11

Cœur

18k9108147

asked Jun 27 '14 at 17:55

Pedro

1881219

asked Jun 27 '14 at 17:55

Pedro

1881219

asked Jun 27 '14 at 17:55

Pedro

1881219

Are you allowed to use classes?

– Casey
Jun 27 '14 at 18:13

@Casey - have a look at the last line: I must add that while I can use basic input/output from C++, I need to use C-style structs.

– haneefmubarak
Jun 27 '14 at 18:18

Technically yes, but I know close to nothing about OOP. I mean, I can read code and understand, but I somehow lack the knowledge to write OOP Code. If you have a solution that uses classes, I'll be happy to read it.

– Pedro
Jun 27 '14 at 18:19

@haneefmubarak It's ok, but thanks for noting!

– Pedro
Jun 27 '14 at 18:21

Yep! No problem.

– haneefmubarak
Jun 27 '14 at 18:21

add a comment |

Are you allowed to use classes?

– Casey
Jun 27 '14 at 18:13

@Casey - have a look at the last line: I must add that while I can use basic input/output from C++, I need to use C-style structs.

– haneefmubarak
Jun 27 '14 at 18:18

Technically yes, but I know close to nothing about OOP. I mean, I can read code and understand, but I somehow lack the knowledge to write OOP Code. If you have a solution that uses classes, I'll be happy to read it.

– Pedro
Jun 27 '14 at 18:19

@haneefmubarak It's ok, but thanks for noting!

– Pedro
Jun 27 '14 at 18:21

Yep! No problem.

– haneefmubarak
Jun 27 '14 at 18:21

Are you allowed to use classes?

– Casey
Jun 27 '14 at 18:13

@Casey - have a look at the last line: I must add that while I can use basic input/output from C++, I need to use C-style structs.

– haneefmubarak
Jun 27 '14 at 18:18

Technically yes, but I know close to nothing about OOP. I mean, I can read code and understand, but I somehow lack the knowledge to write OOP Code. If you have a solution that uses classes, I'll be happy to read it.

– Pedro
Jun 27 '14 at 18:19

@haneefmubarak It's ok, but thanks for noting!

– Pedro
Jun 27 '14 at 18:21

Yep! No problem.

– haneefmubarak
Jun 27 '14 at 18:21

add a comment |

1 Answer
1

active

oldest

votes

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.

answered Jun 27 '14 at 18:55

user207421

261k25210353

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

|
show 1 more comment

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f24458092%2fb-tree-node-splitting-techniques%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

answered Jun 27 '14 at 18:55

user207421

261k25210353

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

|
show 1 more comment

answered Jun 27 '14 at 18:55

user207421

261k25210353

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

|
show 1 more comment

answered Jun 27 '14 at 18:55

user207421

261k25210353

answered Jun 27 '14 at 18:55

user207421

261k25210353

answered Jun 27 '14 at 18:55

user207421

261k25210353

answered Jun 27 '14 at 18:55

user207421

261k25210353

answered Jun 27 '14 at 18:55

user207421

261k25210353

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

|
show 1 more comment

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

Could you be more clear about the part of 'make the parent now point to the two children, via a copy of the first key in each of them'? Noted about the node creation

– Pedro
Jun 27 '14 at 18:58

You've already done half of it, in the last two lines, but you need to adjust the corresponding keys.

– user207421
Jun 27 '14 at 19:08

Let me sit on it for a moment...

– Pedro
Jun 27 '14 at 19:11

Do you mean to adjust the key count? I think I've adjusted the keys on the first 4 lines

– Pedro
Jun 27 '14 at 19:14

You've set the child keys in the first few lines, but you've clobbered the parent keys instead of setting them to child1's first key and child2's first key, or whatever it is you're supposed to do: it depends whether you're building a B-tree or a B+-tree.

– user207421
Jun 27 '14 at 19:19

|
show 1 more comment

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Cfrgtkky