BTREE IMPLEMENTATION

BTREE IMPLEMENTATION (C++ CODE):

#include<iostream.h>
#include<conio.h>
#define max 5

class node;
struct pair
 {
  node *next;
  int key;
 };

class node
{
 public:
 int noofkeys;
 pair data[max];
 node *father;
 node *first;
 node();
 int leafnode();
 void insertinanode(pair x);
 pair splitanode(pair x);
 node *nextindex(int x);
 void display();
};

void node::display()
{
 cout<<"(";
 for(int i=0;i<noofkeys;i++)
 cout<<data[i].key<<" ";
 cout<<")";
}

node *node::nextindex(int x)
{
 if(x<data[0].key)
 return(first);
 for(int i=0;i<noofkeys;i++)
 if(x<=data[i].key)
 return data[i-1].next;
 return data[i-1].next;
}

int node::leafnode()
{
 if(data[0].next==NULL)
 return 1;
 return 0;
}

void node::insertinanode(pair x)
{
 for(int i=noofkeys-1;i>=0&&data[i].key>x.key;i--)
 data[i+1]=data[i];
 data[i+1]=x;
 noofkeys++;
}

pair node::splitanode(pair x)
{
 node *t;
 pair mypair;
 int i,j,centre;
 centre=(noofkeys-1)/2;
 t=new node;
 if(x.key>data[centre].key)
 {
  for(i=centre+1,j=0;i<=noofkeys;i++,j++)
  t->data[j]=data[i];
  t->noofkeys=noofkeys-centre-1;
  noofkeys=noofkeys-t->noofkeys;
  t->insertinanode(x);
  t->first=t->data[0].next;
  t->father=father;
  mypair.key=t->data[0].key;
  mypair.next=t;
  for(i=1;i<t->noofkeys;i++)
  t->data[i-1]=t->data[i];
  t->noofkeys--;
 }
 else
 {
  for(i=centre,j=0;i<noofkeys;i++,j++)
  t->data[j]=data[i];
  t->noofkeys=noofkeys-centre;
  noofkeys=noofkeys-t->noofkeys;
  insertinanode(x);
  t->father=father;
  mypair.key=t->data[0].key;
  mypair.next=t;
  for(i=1;i<t->noofkeys;i++)
  t->data[i-1]=t->data[i];
  t->noofkeys--;
 }
 return(mypair);
}

node::node()
{
 for(int i=0;i<=max;i++)
 data[i].next=NULL;
 noofkeys=0;
 father=NULL;
 first=NULL;
}

class q
{
 node *data[60];
 int r,f;
 public:
 q()
 {
  r=f=0;
 }
 int empty()
 {
  if(r==f)
  return 1;
  else
  return 0;
 }
 node *deque()
 {
  return data[f++];
 }
 void enque(node *x)
 {
  data[r++]=x;
 }
 void makeempty()
 {
  r=f=0;
 }
};

class btree
{
 int mkeys;
 node *root;
 public:
 btree(int n)
 {
  mkeys=n;
  root=NULL;
 }
 void insert(int x);
 void displaytree();
 node *search(int x);
 void delet(int x);
};

node *btree::search(int x)
{
 node *p;
 int i;
 p=root;
 while(p!=NULL)
 {
  for(i=0;i<p->noofkeys;i++)
  if(x==p->data[i].key)
  return(p);
  p=p->nextindex(x);
 }
 return NULL;
}

void btree::displaytree()
{
 q q1,q2;
 node *p;
 q1.enque(root);
 while(!q1.empty())
 {
  q2.makeempty();
  cout<<"\n";
  while(!q1.empty())
  {
   p=q1.deque();
   p->display();
   cout<<" ";
   if(!p->leafnode())
   {
    q2.enque(p->first);
    for(int i=0;i<p->noofkeys;i++)
    q2.enque(p->data[i].next);
   }
  }
  q1=q2;
 }
}

void btree::insert(int x)
{
 int index;
 pair mypair;
 node *p,*q;
 mypair.key=x;
 mypair.next=NULL;
 if(root==NULL)
 {
  root=new node;
  root->insertinanode(mypair);
 }
 else
 {
  p=root;
  while(!(p->leafnode()))
  p=p->nextindex(x);
  if(p->noofkeys<mkeys)
  p->insertinanode(mypair);
  else
  {
   mypair=p->splitanode(mypair);
   while(1)
   {
    if(p==root)
    {
     q=new node;
     q->data[0]=mypair;
     q->first=root;
     q->father=NULL;
     q->noofkeys=1;
     root=q;
     q->first->father=q;
     q->data[0].next->father=q;
     return;
    }
    else
    {
     p=p->father;
     if(p->noofkeys<mkeys)
     {
      p->insertinanode(mypair);
      return;
     }
     else
     mypair=p->splitanode(mypair);
    }
   }
  }
 }
}

void btree::delet(int x)
{
 node *left,*right;
 pair *centre;
 node *p,*q;
 int i,j,centreindex;
 p=search(x);
 for(i=0;p->data[i].key!=x;i++)
 if(!p->leafnode())
 {
  q=p->data[i].next;
  while(!q->leafnode())
  q=q->first;
  p->data[i].key=q->data[0].key;
  p=q;
  x=q->data[0].key;
  i=0;
 }
 for(i=i+1;i<p->noofkeys;i++)
 p->data[i-1]=p->data[i];
 p->noofkeys--;
 while(1)
 {
  if(p->noofkeys>=mkeys/2)
  return;
  if(p==root)
  if(p->noofkeys>0)
  return;
  else
  {
   root=p->first;
   return;
  }
  q=p->father;
  if(q->first==p||q->data[0].next==p)
  {
   left=q->first;
   right=q->data[0].next;
   centre=&(q->data[0]);
   centreindex=0;
  }
  else
  {
   for(i=1;i<q->noofkeys;i++)
   if(q->data[i].next==p)
   break;
   left=q->data[i-1].next;
   right=q->data[i].next;
   centre=&(q->data[i]);
   centreindex=i;
  }
  if(left->noofkeys>mkeys/2)
 {
  right->data[i+1]=right->data[i];
  right->noofkeys++;
  right->data[0].key=centre->key;
  centre->key=left->data[left->noofkeys-1].key;
  left->noofkeys--;
  return;
 }
 else
 if(right->noofkeys>mkeys/2)
 {
  left->data[left->noofkeys].key=centre->key;
  left->noofkeys++;
  centre->key=right->data[0].key;
  for(i=1;i<right->noofkeys;i++)
  right->data[i-1]=right->data[i];
  right->noofkeys--;
  return;
 }
 else
 {
  left->data[left->noofkeys].key=centre->key;
  left->noofkeys++;
  for(j=0;j<right->noofkeys;j++)
  left->data[left->noofkeys+j]=right->data[j];
  left->noofkeys+=right->noofkeys;
  for(i=centreindex+1;i<q->noofkeys;i++)
  q->data[i-1]=q->data[i];
  q->noofkeys--;
  p=q;
 }
}
}

void main()
{
 int i,n,x,op;
 node *p;
 clrscr();
 cout<<"\nEnter number of keys in the node:";
 cin>>n;
 btree b(n);
 do
 {
  cout<<"\n*****MENU*****";
  cout<<"\n1.Insert \n2.Search \n3.Delete \n4.Display \n5.Quit";
  cout<<"\nEnter your choice:";
  cin>>op;
  switch(op)
  {
   case 1:
   cout<<"\nEnter a data:";
   cin>>x;
   b.insert(x);
   cout<<"\nTree after insertion:";
   b.displaytree();
   break;

   case 2:
   cout<<"\nEnter a data:";
   cin>>x;
   p=b.search(x);
   if(p!=NULL)
   {
    cout<<"Found in the node!";
    p->display();
   }
   else
   cout<<"\nElement not found!";
   break;

   case 3:
   cout<<"\nEnter a data:";
   cin>>x;
   p=b.search(x);
   if(p!=NULL)
   {
    b.delet(x);
    b.displaytree();
   }
   else
   cout<<"\nNot found!";
   break;

   case 4:
   b.displaytree();
   break;
  }
 }while(op!=5);
}