1. ## 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* tsplit=NULL;
tsplit=init(tsplit);

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

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

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;

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;
}```