-
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.
-
Thou shalt not posteth code in GD.
-
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
