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.