B-tree, pointer to a pointer issue

[salah_saleh]

I was reading a book and i faced an issue here

39   template< typename NODETYPE >
40   void Tree< NODETYPE >::insertNode( const NODETYPE &value )
41   {
42      insertNodeHelper( &rootPtr, value );
43   } // end function insertNode
44
45   // utility function called by insertNode; receives a pointer
46   // to a pointer so that the function can modify pointer's value
47   template< typename NODETYPE >
48   void Tree< NODETYPE >::insertNodeHelper(
49      TreeNode< NODETYPE > **ptr, const NODETYPE &value )
50   {
51      // subtree is empty; create new TreeNode containing value
52      if ( *ptr == 0 )
53         *ptr = new TreeNode< NODETYPE >( value );
54      else // subtree is not empty
55      {
56         // data to insert is less than data in current node
57         if ( value < ( *ptr )->data )
58            insertNodeHelper( &( ( *ptr )->leftPtr ), value );
59         else
60         {
61            // data to insert is greater than data in current node
62            if ( value > ( *ptr )->data )
63               insertNodeHelper( &( ( *ptr )->rightPtr ), value );
64            else // duplicate data value ignored
65               cout << value << " dup" << endl;
66         } // end else
67      } // end else
68   } // end function insertNodeHelper

why in line 49 there is a pointer to a pointer, why couldn't I simply make a simple pointer and pass the rootptr directly?, as every time we make ( (*ptr) -> rightptr ) we could substite it with ptr->rightptr directly.

[mike_2000_17]

It gives the reason why directly above the function definition:

45   // utility function called by insertNode; receives a pointer
46   // to a pointer [B]so that the function can modify pointer's value[/B]

If you simply pass the rootptr, any modification to the root-pointer with the function will not affect the rootptr variable in the caller's code (insertNode).

A more usual way to do this is using a reference instead:

47   template< typename NODETYPE >
48   void Tree< NODETYPE >::insertNodeHelper(
49      TreeNode< NODETYPE > *& ptr, const NODETYPE& value )
50   {
51      // subtree is empty; create new TreeNode containing value
52      if ( ptr == 0 )
53         ptr = new TreeNode< NODETYPE >( value );
54      else // subtree is not empty
55      {
56         // data to insert is less than data in current node
57         if ( value < ptr->data )
58            insertNodeHelper( &( ptr->leftPtr ), value );
59         else
60         {
61            // data to insert is greater than data in current node
62            if ( value > ptr->data )
63               insertNodeHelper( &( ptr->rightPtr ), value );
64            else // duplicate data value ignored
65               cout << value << " dup" << endl;
66         } // end else
67      } // end else
68   } // end function insertNodeHelper

It makes the syntax cleaner, and it is essentially equivalent to the pointer-to-pointer version.

[salah_saleh]

thank you, I got it :), and thank you for your suggestion it's very useful :)