Thread: b-tree (not binary tree) implementation help

http://213.105.253.100/~ice/b-tree.cpp

Thats what i've got so far. I'm having problems with the splitting of the nodes and promoting the keys (the split_node function).

Thanks for any help.

Hi there. I was doing some debugging and noticed that the child pointers were not null, but we being set to 0xcdcdcdcdc when they were created.
You need to create a constructor for the node, so it will set all pointers to NULL when you create nodes using the new keyword.
TO do that change your code to this.

Code:

typedef struct _node{

    string key[M];
     _node *children[M+1];
     _node *parent;
    int size;
	_node()
	{
		parent = NULL;
		for(int i=0 ; i< M+1 ; i++)
		{
			children[i] = NULL;
		}
	}

} node;

;
The program now runs without any memory errors. I changed nothing else in the code.
This is the output i get.
0:p 1: 2: 3: 4:


Taking a quick glance at the rest of the code I saw this

Code:

// FIXME: this is no good, hides the problem
// but doesn't fix it
//while (root->parent->parent != NULL)
//root->parent = root->parent->parent;

You could try changing that to

Code:

if( root->parent != NULL )
{
 while( root->parent->parent != NULL)
 root->parent = root->parent->parent;
}

That will make sure that root->parent points to valid memoy before attempting to compare that memory to NULL
Changing that code did not affect the output in anyway, but I am not sure what output you are expecting, post if you need
anymore help
I take it this is for a college or ap comp sci course? what is it, I'm just curious

Forgot one thing.
You may wish to set size to a value in the constructor function.

Thanks for replying. The problem with variable initialisation i fixed (i hope) a little while after posting.

The program now mostly works except in the case of the root node being full. I don't know if you could provide some pseduocode to show how to best handle that?

The latest updates are available at the same ip address as above.

The output i get is (also some debugging info):

0:c 1:f 2:j 3:s 4:v
child: 0:a 1:b 2: 3: 4:
child: 0:d 1:e 2: 3: 4:
child: 0:g 1:h 2:i 3: 4:
child: 0:k 1:m 2:n 3 4
child: 0:t 1:u 2: 3: 4:
child: 0:w 1:x 2:z 3: 4:

which is correct up until adding another key (root node full problem)

Yes this is for a uni assignment (software engineering)

Here are a few errors i found in your code
1) Inside the print tree function you are looping for M+1, you only want to go up to M, so change that

void
print_tree(node *root)
{
print_node(root);

for (int i = 0; i < M+1; i++) {
if (root->children[i] != NULL)
print_tree(root->children[i]);
}
}

2) Inside this block of code is the problem, I think
Inside the for loop you add children to the newly created nodes, but for the second one you are using 3+1 and i think you mean 3+i
And why are you decreasing the parent pointer using --?
Then after adding all those nodes to root->parent->parent->children[0] you overwrite it with the line
root->parent->parent->children[0] = root->parent->children[0];??
you do the same thing for children[1]

Also i think there is a problem with looping for MIDDLE_KEY times
M is 5, so middle key is 5/2 = 2 in C++ math. and not 2.5
So you are looping only twice, first i is 0, then i is 1. So you only read 4 keys, and not all 5
I would loop for M times, and if i < MIDDLE_KEY work on children[0] other wise work on children[1]

Also what is the point of having 5 children if you only ever use the first 2?

Code:

    if (root->parent) {
        cout << "PROMOTE KEY" << endl;
        int pos;
        // move middle key up to parent function
        // update pointers
       
        /* HOW TO HANDLE FACT ROOT NODE COULD BE FULL ????
        // root node is full
        if (root->parent->size == M) {
            root->parent->parent = create_node();
            add_key(root->parent->parent, root->parent->key[MIDDLE_KEY]);
            
            root->parent->parent->children[0] = create_node();
            root->parent->parent->children[1] = create_node();

            for (int i = 0; i < MIDDLE_KEY; i++) {
                add_key(root->parent->parent->children[0],
                                                root->parent->key[i]);
                root->parent->key[i] = "";
                root->parent--;

                add_key(root->parent->parent->children[1],
                                                root->parent->key[3+i]);
                root->parent->key[3+1] = "";
                root->parent--;
            }
               
            
            root->parent->parent->children[0] = root->parent->children[0];
            root->parent->parent->children[1] = root->parent->children[1];
        }
        */

http://www.semaphorecorp.com/btp/algo.html
http://www.dcc.uchile.cl/~rbaeza/han...42.data.c.html
http://www.dcc.uchile.cl/~rbaeza/han...342.ins.c.html

Here is what i found doing some searching on google.com

> 1) Inside the print tree function you are looping
> for M+1, you only want to go up to M, so change
> that

From my understanding of b-tree's, each node has M+1 children (pointers) so that loop would be correct.

> Inside the for loop you add children to the newly
> created nodes, but for the second one you are
> using 3+1 and i think you mean 3+i

yeah, fixed that, thanks

> And why are you decreasing the parent pointer
> using --?

The loop is copying over first two keys and the last two keys from the parent node into the newly created nodes. The parent size has to be decrementated otherwise it'll break later on when the size of the parent node isn't reflected properly.

> Then after adding all those nodes to
> root->parent->parent->children[0] you
> overwrite it with the line
> root->parent->parent->children[0] =
> root->parent->children[0];??

Yeah that code is a mess, it was a first (poor) attempt at fixing the "root node is full" problem.

> I would loop for M times, and if i < MIDDLE_KEY
> work on children[0] other wise work on
> children[1]

In the loop the first two keys are copied to the left node (0) and the last two keys are copied to the right node (1). The middle key doesn't need to be copied because it gets promoted later on, so the loop only needs to run twice.

> Also what is the point of having 5 children if you
> only ever use the first 2?

All the pointers are updated later on in the "if (root->parent)" code block.

Sorry for my previous reply, i was a little tired when looking at that code.
I believe i found your problems.
First) I downloaded the source code, and when running it, my computer would crash during the printing.
I know you have a create node function which sets all the vars to default values, but somewhere a node is not getting set to the default values.

I change the struct code to this

Code:

typedef struct _node {
    string key[M];
    struct _node *children[M+1];
    struct _node *parent;
    int size;
	_node()
	{
		int i;
		for( i=0 ; i<M ; i++)
		{
			key[i]="";
			children[i]=NULL;
		}
		children[M]=NULL;
		parent = NULL;
		size=0;
	}
} node;

Next problem:
I asked why you were decreasing the root->parent pointer inside the block of code that deals with the full root node.
You had root->parent--; and you meant
root->parent->size--;
That is in the commented out area.

Just to be double safe i added a few if's to check for null in the printing routines

Code:

void
print_tree(node *root)
{
	if( root != NULL)
	{
		print_node(root);

		for (int i = 0; i < (M+1); i++) {
			if (root->children[i] != NULL)
				print_tree(root->children[i]);
		}
	}
}

void
print_node(node *root)
{
	if( root != NULL)
	{
	    if (root->parent != NULL)
		    cout << "child: ";

	    for (int i = 0; i < M; i++) {
	     cout << i << ":" << root->key[i] << " ";
	    }
		cout << endl;
	}
}

Now when running i got this as output
child: 0: 1:n 2:j 3:s 4:
child: 0:a 1:b 2: 3: 4:
child: 0:k 1:m 2: 3: 4:
child: 0:o 1:p 2:q 3: 4:
child: 0: 1: 2:n 3: 4:
child: 0:k 1:m 2: 3: 4:
child: 0:o 1:p 2:q 3: 4:
child: 0:t 1:u 2: 3: 4:
child: 0:w 1:x 2:z 3: 4:
Press any key to continue

That output looks is a total mess and different to what i get (equally as wrong though), it'll probably be better to scrap the current code and start again.

Thanks for all your help.