# The Tree

Printable View

• 03-06-2003
vasanth
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
• 03-06-2003
ober
Algorithm or code question, I still don't think this is a GD question.
• 03-06-2003
Govtcheez
Thou shalt not posteth code in GD.
• 03-06-2003
vasanth
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