Thread: The Tree

THough this algorithm is done by me using C++ i posted it here since it was an algorithm question and not a language one..


I have built a b-Tree.. the code is as below.. The B-Tee(not Binary tree) works fine when i enter the following numbers 20,40,10,30,15,35,7,26,18 but when i enter the next number 22, somehow the tree gets all screwed up..... I even worked out this in my book.. logically nothing wrog should happen it should insert fine..

The tree is of order 1(for building purpose)

till i enter 22 the following tree is built

Code:

                              |20|   |  |  
                              | ,  |   |  |    |
                               ,               '
                             ,                      '
                        ,                             '
                   |10|   |  |                       |35|   |  |  
                   |    |   |  |   |                   |    |   |  |   | 
                   ,             '                          '            '
                 ,                '                         '              '
                ,                    '                      '                  '
               |7  |   |  |       |15|18|  |         |26|30|  |    |40|  |  |

but after entering the next number 22 the tree is not stable.i.e it has the values placed in the wrong nodes... I am even making sure that if a split results in an overfull node the split continues...



my prog code is.. I know my prog style is bad.. But i am desperate to find the above mentioned bug in my code...

Code:

# include <iostream.h>
# include <conio.h>
# include <process.h>

# define SUCCESS 1
# define FAIL 0

class btree
	{
		private:
			struct tree
				{
				int val[3];
				struct btree::tree *node[4];
				struct btree::tree *parent;
				int num;
				};

			struct btree::tree *root;
			struct btree::tree *tins;



			btree::tree* init(btree::tree*);
			display(struct btree::tree*);
			put(int,btree::tree*);
			btree::tree* sort(btree::tree*);
			btree::tree* getnode(int,btree::tree*);
			btree::tree* getnode(int);
			duplicate(int,struct btree::tree*);
			dupe(int);



		public:
			btree();
			disp();
			insert(int);
			split(btree::tree*);



	};


btree::insert(int num)
{
if(dupe(num)==FAIL)
return FAIL;
tins=getnode(num);
put(num,tins);
tins=NULL;
return SUCCESS;
}

btree::disp()
{
return display(root);
}


btree::dupe(int num)
{
return duplicate(num,root);
}

btree::tree* btree::getnode(int num)
{
 return getnode(num,root);
}


btree::tree* btree::getnode(int num,btree::tree* temp)
{
for(int i=0;i<temp->num;i++)
{
if(temp->val[i]>num)
{
 if(temp->node[i]!=NULL)
 return getnode(num,temp->node[i]);
 else
 return temp;

}

}

if(temp->node[3]!=NULL)
return getnode(num,temp->node[3]);

return temp;
}


btree::tree* btree::sort(btree::tree *temp)
{
if(temp==NULL)
return FAIL;
int tn=0;
struct btree::tree *tt=NULL;

for(int i=0;i<temp->num;i++)
{
 for(int j=i+1;j<temp->num;j++)
 {
 if(temp->val[i]>temp->val[j])
 {
 tn=temp->val[i];
 tt=temp->node[i];

 temp->val[i]=temp->val[j];
 temp->node[i]=temp->node[j];

 temp->val[j]=tn;
 temp->node[j]=tt;
 tt=NULL;
 }

 }
}

return temp;
}

btree::split(btree::tree *temp)
{
temp=sort(temp);
if(temp->num<3)
return SUCCESS;

if(temp->parent==NULL)
{
struct btree::tree* thead=NULL;
struct btree::tree* tsplit=NULL;
thead=init(thead);
tsplit=init(tsplit);

thead->val[0]=temp->val[1];
thead->node[0]=temp;
thead->node[3]=tsplit;
thead->parent=NULL;
thead->num=1;
thead=sort(thead);
root=thead;


tsplit->val[0]=temp->val[2];
tsplit->node[0]=temp->node[2];
tsplit->num=1;

tsplit->node[3]=temp->node[3];
tsplit->parent=thead;

tsplit=sort(tsplit);

temp->val[1]=NULL;
temp->num--;

temp->val[2]=NULL;
temp->num--;

temp->node[3]=temp->node[1];
temp->node[1]=NULL;
temp->node[2]=NULL;
temp->parent=thead;


return SUCCESS;
}
else
{
temp=sort(temp);
struct btree::tree* tsplit=NULL;
tsplit=init(tsplit);

tsplit->val[0]=temp->val[2];
tsplit->num++;

if(temp->node[2]!=NULL)
tsplit->node[0]=temp->node[2];

tsplit->parent=temp->parent;

if(temp->node[3]!=NULL)
tsplit->node[3]=temp->node[3];

for(int i=0;i<4;i++)
{
 if(temp->parent->node[i]==temp)
 {
 temp->parent->node[i]=tsplit;
 break;
 }
}

temp->parent->val[temp->parent->num]=temp->val[1];
temp->parent->node[temp->parent->num]=temp;
temp->parent->num++;

sort(temp->parent);

temp->node[3]=temp->node[1];
temp->num=1;
temp->val[1]=NULL;
temp->val[2]=NULL;
temp->node[1]=NULL;
temp->node[2]=NULL;
sort(temp->parent);

if(tsplit->parent->num>2)
return split(temp->parent);


return SUCCESS;
}




}

btree::put(int num,btree::tree *temp)
{
if(temp->num<3)
{
temp->val[temp->num]=num;
temp->num++;
temp=sort(temp);

if(temp->num>=3)
split(temp);

return SUCCESS;
}
return FAIL;
}


btree::display(btree::tree *temp)
{
cout<<"\n";
for(int i=0;i<temp->num;i++)
{
 cout<<temp->val[i]<<" ";
}

for(i=0;i<4;i++)
{
if(temp->node[i]!=NULL)
display(temp->node[i]);
}


return SUCCESS;
}



btree::duplicate(int num,btree::tree *temp)
{

for(int i=0;i<3;i++)
{
 if(temp->val[i]==num)
 return FAIL;
}

for(i=0;i<4;i++)
{
if(temp->node[i]!=NULL)
{
if(duplicate(num,temp->node[i])==FAIL)
return FAIL;
}
}



return SUCCESS;
}



btree::btree()
{
root=NULL;
root=init(root);
}

btree::tree* btree::init(btree::tree* temp)
{
temp=new btree::tree;
temp->num=0;
temp->parent=NULL;
for(int i=0;i<4;i++)
{
temp->node[i]=NULL;
if(i<3)
temp->val[i]=NULL;
}

return temp;
}




/*
int main()
{
clrscr();
btree b;
b.disp();


return 0;
} */



int main()
{
int option=100;
btree b;
int num;
while(option!=3)
{
clrscr();
cout<<"\nM E N U";
cout<<"\n_______";
cout<<"\n\n\n1) Insert into B-Tree";
cout<<"\n\n2) Display B-Tree";
cout<<"\n\n3) Exit";
cout<<"\n\n\nOption > ";
cin>>option;
clrscr();
if(option==2)
{
b.disp();
getch();
}

if(option==1)
{
 cout<<"\nEnter the number to be inserted > ";
 cin>>num;
 if(b.insert(num)==FAIL)
 cout<<"\nDuplicate entry...";
 else
 cout<<"\nInserted...";
 getch();
}




}


return 0;
}

Thanx in advance

Algorithm or code question, I still don't think this is a GD question.

Well.. found the problem.. It was a silly problem where i did not update the parent pointer when a node split.. Now i am planing to generalize this class and make in an M orde B Tree..

Bye