b-tree (not binary tree) implementation help

This is a discussion on b-tree (not binary tree) implementation help within the C++ Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Unregistered
    Guest

    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.

  2. #2
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    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

  3. #3
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    Forgot one thing.
    You may wish to set size to a value in the constructor function.

  4. #4
    Unregistered
    Guest
    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)

  5. #5
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    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];
            }
            */

  6. #6

  7. #7
    Unregistered
    Guest
    > 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.

  8. #8
    Registered User
    Join Date
    Dec 2001
    Posts
    194
    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

  9. #9
    Unregistered
    Guest
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21