I've been coding a B-Tree structure and only half of it works. Half the potential errors I need to go thru and review my code but some parts I can't comprehend why it won't work. I can't seem to insert data into an empty B-Tree set structure. It somewhat works when I change the data_count in the root node from 0 to some # <= the max # items in a node. When I run the program and try to insert into an empty set, I get an application error which terminates the program. I looked over the insert, loose_insert, and constructor functions and I think they are logically ok. Did I miss something?

Below is an excerpt of the source code:
Code:
//header/class specification file:
#ifndef MAIN_SAVITCH_SET_H
#define MAIN_SAVITCH_SET_H
#include <iomanip>
#include <iostream>
#include <cstdlib>   // Provides size_t
using namespace std;

namespace main_savitch_11
{
   typedef int Item;
     class set
   {
   public:
       // TYPEDEFS
          //typedef int ITEM;
          //typedef Item int;
       //typedef Item value_type;
       // CONSTRUCTORS and DESTRUCTOR
       set( );
       // MODIFICATION MEMBER FUNCTIONS
       bool insert(const Item& entry);
       // CONSTANT MEMBER FUNCTIONS
       bool empty( ) const { return (data_count == 0); }
       // SUGGESTED FUNCTION FOR DEBUGGING
       // MEMBER CONSTANTS
       enum { MINIMUM = 2 };
       enum { MAXIMUM = 4 };
       // MEMBER VARIABLES
       size_t data_count;
       Item data[MAXIMUM+1];
       size_t child_count;
       set *subset[MAXIMUM+2];
       // HELPER MEMBER FUNCTIONS  
       bool is_leaf( ) const { return (child_count == 0); }
   private:
       // HELPER MEMBER FUNCTIONS
       bool loose_insert(const Item& entry);
       void fix_excess(size_t i);
     void fix_root();
   };

// CONSTRUCTORS
set::set() { 
     //Set data & child counts to 0
     int i(0);
     data_count = 0;
     child_count = 0;
     //Set ROOT node to NULL
     for(i=0; i < MAXIMUM+1; ++i)
          data[i] = NULL;
     //Set subsets to NULL
     for(i=0; i < MAXIMUM+2; ++i)
          subset[i] = NULL;
}
bool set::insert(const Item& entry){ 
     if(!loose_insert(entry))
          return false;
     if(data_count > MAXIMUM)
          fix_root();
     return true;
}
// HELPER MEMBER FUNCTIONS (private)
bool set::loose_insert(const Item& entry){ 
     int i(0);//Step 1
     while((data[i] < entry) && (i < data_count)){i++;}
     if(data[i] == entry){//Step 2a
          return false;
     }else if(is_leaf()){//Step 2b
          size_t j(data_count-1);
          while(j >= i){ //or j < data_count-1 or j < data_count where j = i
               data[j+1] = data[j];
               j--;//or j++;
          }
          data[i] = entry;
          data_count++;
          return true;
     }else{//Step 2c
          bool insert_status;
          insert_status = subset[i]->loose_insert(entry);
          if(subset[i]->data_count > MAXIMUM)
               subset[i]->fix_excess(i); //fix excess at subset[i]?
          return insert_status;
     }
}
void set::fix_excess(size_t i){ 
     size_t middle = MINIMUM;//find middle node to go up to root
     set *new_node = new set;//allocate new node for splitting excess node**
     size_t noder(middle+1), m(data_count-1);
     int l(0);
     if((i == 0) && empty()){//Fix up excess entry at root
          //no need move subsets right 1
          subset[i+1] = new_node;//setup new node for splitting
          while(noder < MAXIMUM+1){//for copy data
               subset[i+1]->data[l] = subset[i]->data[noder];//***copy excess node data to new node
               subset[i+1]->data_count++;
               subset[i]->data[noder] = NULL;//set old data in subset[i] to NULL
               subset[i]->data_count--;
               l++;
               noder++;
          }
          noder = middle+1;
          l = 0;
          while(noder <= MAXIMUM+1){// for copy subset
               subset[i+1]->subset[l] = subset[i]->subset[noder];//***copy excess node data to new node
               subset[i+1]->child_count++;
               subset[i]->subset[noder] = NULL;//set old data in subset[i] to NULL
               subset[i]->child_count--;
               l++;
               noder++;
          }//no need move root data which is 0
          data[i] = subset[i]->data[middle];
          data_count++;
          subset[i]->data[middle] = NULL;//set subset data to NULL
          subset[i]->data_count--;
     }else{//Fix up all other excess entry cases
          size_t k(child_count-1);//move subsets past i, over 1
          while(k > i){
               subset[k+1] = subset[k];
               k--;
          }
          subset[i+1] = new_node;//setup new node for splitting
          while(noder < MAXIMUM+1){//for copy data
               subset[i+1]->data[l] = subset[i]->data[noder];//***copy excess node data to new node
               subset[i+1]->data_count++;
               subset[i]->data[noder] = NULL;//set old data in subset[i] to NULL
               subset[i]->data_count--;
               l++;
               noder++;
          }
          noder = middle+2;
          l = 0;
          while(noder < MAXIMUM+2){// for copy subset
               subset[i+1]->subset[l] = subset[i]->subset[noder];//***copy excess node data to new node
               subset[i+1]->child_count++;
               subset[i]->subset[noder] = NULL;//set old data in subset[i] to NULL
               subset[i]->child_count--;
               l++;
               noder++;
          }
          while(m >= i){//move data right 1 at node
               data[m+1] = data[m];
               m--;
          }
          data[i] = subset[i]->data[middle];
          data_count++;
          subset[i]->data[middle] = NULL;//set subset data to NULL
          subset[i]->data_count--;
     }
}
void set::fix_root(){
     int i(0);
     set *new_node = new set;//Allocate new node to copy ROOT & its subset
     if(data_count > MAXIMUM){//root w/ excess entry
          //Part 1:          
          new_node = this;//copy ROOT & its subset
          //Clear out ROOT
          for(i=0; i < data_count; ++i)
               data[i] = NULL;
          data_count = 0;
          //Clear out ROOT's subset - NOT DELETE PTRS
          for(i=0; i < child_count; ++i){
               if(subset[i] != NULL) subset[i] = NULL;}
          //Set subset to be the copy of ROOT
          child_count = 1;
          subset[0] = new_node;
          //Part 2:
          fix_excess(0);
     }else{//if((empty))//empty root
          new_node = subset[0];
          for(i = 0; i < subset[0]->data_count; i++){
               data[i] = subset[0]->data[i];
               data_count++;}
          for(i = 0; i < new_node->child_count; i++){
               subset[i] = new_node->subset[i];
               if(i) child_count++; }
          delete new_node;
     }
}
}
#endif

// in application file:
#include <iostream>
#include <cstdlib>   // Provides size_t
#include <iomanip>
#include "set.h"
using namespace std;
using namespace main_savitch_11;

int main() {
     
     set B_tree;
     int choice;
     int result;
     int in_data, del_data;
     size_t total;
     char more = 'y';
     do {

          cout << endl;
          cout << "main Menu\n";
          cout << "Select a numbered option from the menu below to begin\n";
          cout << "1 to INSERT a number into the set\n";
// some code here
          switch (choice) {
          case 1:                              
               cout << "Enter a number to insert and press return: ";
               cin >> in_data;
               result = B_tree.insert(in_data);
               if(!result) cout << "Sorry, the number is already in the set.\n";
               break;
//more code here
     return 0;
}
If you need the full source code for the application and implementation, for reviewing or test compiling, go here:

http://www.engr.sjsu.edu/daluu/cmpe1.../set_class.txt (the header .h file)
http://www.engr.sjsu.edu/daluu/cmpe1...set_driver.txt (the app .cpp file)

NOTE: Most of the comments are just for insight but not of much importance, i guess. I had to modify the code which was supposed to use a template class, etc. so it would compile in VC++ 6.0 for the time being.