title: Inserting a node to the B-Tree
body: <p>I am trying to implement an insert method for a BTree.  My BTree class holds a pointer to a root BNode.  The insert method has both an internal and external method.  The internal one doesnt yet recurse, but I am having trouble having the root passed in hold its value for the second insertion.  I think it might be a scoping issue, but I'm not sure exactly what it is.  In main I tried to insert 2 values to test the method, but it seems that in the second insertion it still thinks that root == null and overwrites the first key value.  Does anyone who why this might occur?</p>
  
  <p>Here are my functions:</p>
  
  <pre><code>    template&lt;typename T, int M&gt;
      class BTree{
      private:
  
  
          returnStatus _insert( BNode&lt;T, M&gt;* r, const T&amp; val, BNode&lt;T, M&gt;*&amp; dptr, T&amp; dkv );
          returnStatus shuffle_insert( BNode&lt;T, M&gt;* r, const T&amp; val );
          returnStatus split_insert( BNode&lt;T, M&gt;* r, const T&amp; val, BNode&lt;T, M&gt;*&amp; dptr, T&amp; dkv );
          bool isNodeLeaf( BNode&lt;T, M&gt;* node );
          int _getNodeIndex( BNode&lt;T, M&gt;* r, const T&amp; val );
  
          returnStatus _find( BNode&lt;T, M&gt;* r, const T&amp; val );
          returnStatus _remove( BNode&lt;T, M&gt;* r, const T&amp; val, BNode&lt;T, M&gt;* &amp; dptr, T&amp; dkv );
          void _traverse( BNode&lt;T, M&gt;* r );
  
      public:
          BNode&lt;T, M&gt;* root;
          int size;
  
          BTree();
          void insert( const T&amp; val );
          returnStatus find( const T&amp; val );
          void remove( const T&amp; val );
          void traverse();
          ~BTree();
  
      };
      template&lt;typename T, int M&gt;
      BTree&lt;T, M&gt;::BTree()
      {
      root = NULL;
      size = 0;
          }
          template&lt;typename T, int M&gt;
      returnStatus BTree&lt;T, M&gt;::_insert( BNode&lt;T, M&gt;* r, const T&amp; val, BNode&lt;T, M&gt;*&amp; dptr, T&amp; dkv )
      {
      if( r == NULL ){
          dptr = NULL;
          dkv = val;
          r = new BNode&lt;T, M&gt;;
          r-&gt;keys[0] = val;
          size++; 
          r-&gt;keyCount++;
  
          return unsuccessful;
      }else{
          returnStatus contains = find(val);
  
          if( contains == duplicate ){
              return duplicate;
          }else{
  
              if( r-&gt;keyCount &lt; M-1 ){
                  returnStatus hold = shuffle_insert(r, val);
                  return hold;
              }else{
                  cout&lt;&lt;"need to split"&lt;&lt;endl;
                  //split_insert
              }
          }
      }
  }
  template&lt;typename T, int M&gt;
  returnStatus BTree&lt;T, M&gt;::shuffle_insert( BNode&lt;T, M&gt;* r, const T&amp; val )
  {
      if(r-&gt;keyCount == M-1 ) return unsuccessful;
  
      int index = _getNodeIndex(r, val);
  
      for(int i = r-&gt;keyCount; i&gt;index; i--){
          r-&gt;keys[i+1] = r-&gt;keys[i];
      }
      r-&gt;keys[index] = val;
      r-&gt;keyCount++;
  }
  template&lt;typename T, int M&gt;
  returnStatus BTree&lt;T, M&gt;::split_insert( BNode&lt;T, M&gt;* r, const T&amp; val, BNode&lt;T, M&gt;*&amp; dptr, T&amp; dkv )
  {
  
  
  
  }
  template&lt;typename T, int M&gt;
  bool BTree&lt;T, M&gt;::isNodeLeaf( BNode&lt;T, M&gt;* node )
  {
      for( int i = 0; i&lt; M-1; i++ ){
          if( node-&gt;ptr[i] != NULL ){
              return false;
          }
      }
      return true;
  }
  template&lt;typename T, int M&gt;
  returnStatus BTree&lt;T, M&gt;::_find( BNode&lt;T, M&gt;* r, const T&amp; val )
  {
      for( int i = 0; i&lt;M; i++ ){
          if( r-&gt;ptr[i] != NULL ){
              _find( r-&gt;ptr[i], val);
          }
      }
      for( int i =0; i&lt;r-&gt;keyCount; i++ ){
          if( r-&gt;keys[i] == val ) return duplicate;
      }
      return unsuccessful;
  }
  template&lt;typename T, int M&gt;
  int BTree&lt;T, M&gt;::_getNodeIndex( BNode&lt;T, M&gt;* r, const T&amp; val )
  {
      for( int i = 0; i &lt; r-&gt;keyCount; i++){
          if( val &lt; r-&gt;keys[i] ){
              return i;
          }
      }
      return -1;
  }
  
      template&lt;typename T, int M&gt;
  void BTree&lt;T, M&gt;::insert( const T&amp; val )
  {
      int set = 0;
      BNode&lt;T, M&gt;* myNode = new BNode&lt;T, M&gt;();                        //May not be correct way to instantiate Reference to pointer
      returnStatus status = _insert( root, val, myNode, set);
  
      if( status == successful ){
          return;
      }else if( status == unsuccessful ){
  
  
      }else if( status == duplicate ){
          cout&lt;&lt;val&lt;&lt;" has already been inserted."&lt;&lt;endl;
      }
  
  }
  template&lt;typename T, int M&gt;
  returnStatus BTree&lt;T, M&gt;::find( const T&amp; val )
  {
      returnStatus stat = _find(root, val);
      return stat;
  }
  template&lt;typename T, int M&gt;
  void BTree&lt;T, M&gt;::remove( const T&amp; val )
  {
  
  }
  template&lt;typename T, int M&gt;
  void BTree&lt;T, M&gt;::traverse()
  {
      _traverse(root);
  }
  template&lt;typename T, int M&gt;
  BTree&lt;T, M&gt;::~BTree()
  {
  
  
  
  }
  </code></pre>