Quantcast

Jump to content

» «
Photo

Binary tree Insertion pointer to pointer?

2 replies to this topic
Swoorup
  • Swoorup

    innovator

  • Members
  • Joined: 28 Oct 2008

#1

Posted 24 December 2011 - 04:16 PM

I have been studying this for two hours but I don't just get why a pointer to pointer is used for the second parameter? Could not it do with only *leaf? The cprogramming site mentions that it is done so in order to allow memory allocation for root node also but could it do with only a single pointer?

Here's the code that account what I have said:

CODE
insert(int key, struct node *leaf)
{
   if( leaf == 0 )
   {
       leaf = malloc( sizeof( struct node ) );
       leaf->key_value = key;
       
       leaf->left = 0;    
       leaf->right = 0;  
   }
   else if(key < leaf->key_value)
   {
       insert( key, leaf->left );
   }
   else if(key > leaf->key_value)
   {
       insert( key, leaf->right );
   }
}


And the actual code:
CODE
insert(int key, struct node **leaf)
{
   if( *leaf == 0 )
   {
       *leaf = (struct node*) malloc( sizeof( struct node ) );
       (*leaf)->key_value = key;
       /* initialize the children to null */
       (*leaf)->left = 0;    
       (*leaf)->right = 0;  
   }
   else if(key < (*leaf)->key_value)
   {
       insert( key, &(*leaf)->left );
   }
   else if(key > (*leaf)->key_value)
   {
       insert( key, &(*leaf)->right );
   }
}


Can anyone explain it to me,why is it so?

K^2
  • K^2

    Vidi Vici Veni

  • Moderator
  • Joined: 14 Apr 2004
  • United-States

#2

Posted 24 December 2011 - 06:44 PM

Lets look at the first code block you posted. Suppose with this definition of insert(), I call the following:

CODE
node *root=0; //Empty tree.
insert(42, root);


The variable root is located at some address, say Address1. At Address1 the value of root is stored, which is 0. In other words *(Address1)=0. Now you make the call. The value from variable root is passed to the function along with the key. The key is stored in variable key, the value from root is stored in variable leaf. Variable leaf is also located somewhere in memory for duration of the call. (Specifically, in the stack, but that's details.) Lets say, leaf is located at Address2. You pass to it the value from root, so effectively you do *(Address2)=*(Address1).

Next, function checks the variable leaf, sees that it is zero, and proceeds to allocate space. You call malloc, and lets say it returns Address3. You set it to leaf. Effectively, *(Address2)=Address3. Then you do other stuff and return from function. So now *(Address2) holds the address to new root node, but *(Address1) was never changed. It is still zero. So after the function exits, root still holds 0. Null pointer, and therefore, useless. The tree was created and lost.


Now lets look at second definition. Call changes only slightly.

CODE
node *root=0;
insert(42, &root);


But what happens on the inside? Instead of setting leaf to value of root, you set it to address of root. (The variable itself, not where it points to.) In other words *(Address2)=Address1. Now *leaf=malloc() effectively becomes *(*(Address2)) = Address3. But *(Address2) is same as Address1, so this line is equivalent to *(Address1)=Address3. The rest of the program flows pretty much the same, but after the function returns, root is set to Address3, which is the actual address of the root of your tree.



There are other ways to do all this. For example, you can use return value. Consider the following code.

CODE
node *insert(int key, node *leaf)
{
   if(!leaf)
   {
      leaf=malloc(sizeof(node));
      leaf->key_value=key;
      leaf->left=0;
      leaf->right=0;
      return leaf;
   }
   if(key<leaf->key_value)
   {
      leaf->left=insert(key, leaf->left);
      return leaf;
   }
   leaf->right=insert(key, leaf->right);
   return leaf;
}


And you'd make the call like this.

CODE
node *root=0;
root=insert(42, root);


In terms of efficiency, there is not much difference. Note that I omitted else statements, because code execution never gets past return statements. Sometimes you want to keep the else blocks for clarity, though. This might actually be one of these, but meh.

businesslogoart
  • businesslogoart

    Player Hater

  • BUSTED!
  • Joined: 11 Jan 2012

#3

Posted 11 January 2012 - 12:24 PM Edited by Seddo, 11 January 2012 - 11:46 PM.

Good Info, Thanks a lot for this it has helped me a great deal keep it up .




1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users