/******************************************************
NAME : JABIR DAUD PATHAN
PROGRAM : IMPLEMENTATION OF A B-TREE
*******************************************************/
/*---------------<< Header File
>>------------------*/
#include
<iostream.h>
#include
<conio.h>
#define
MAX 5
class node;
struct pair
{
node *next;
int key;
};
/*----------<< Declaration of class node >>---------*/
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();
};
/*-------<<
Function defination for display >>---------*/
void node::display()
{
int i;
cout<<"(";
for(i=0;i<noofkeys;i++)
cout<<data[i].key<<"
";
cout<<")";
}
/*-------<<
Function defination for nextindex >>---------*/
node *node::nextindex(int x)
{
int i;
if(x<data[0].key)
return(first);
for(i=0;i<noofkeys ;i++)
if(x <= data[i].key)
return data[i-1].next;
return data[i-1].next;
}
/*-------<<
Function defination for leafnode >>---------*/
int node::leafnode()
{
if(data[0].next==NULL)
return 1;
return 0;
}
/*-------<<
Function defination for inserting node >>---------*/
void node::insertinanode(pair x)
{
int i;
for(i=noofkeys-1;i>=0 &&
data[i].key>x.key;i--)
data[i+1]=data[i];
data[i+1]=x;
noofkeys++;
}
/*-------<<
Function defination for splitanode >>---------*/
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;
}
/*----------<< Declaration of class Queue
>>---------*/
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;
}
};
/*----------<< Declaration of class btree
>>---------*/
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 Delete(int x);
};
/*-------<<
Function defination for search >>---------*/
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;
}
/*-------<<
Function defination for display tree >>---------*/
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;
}
}
/*-------<<
Function defination for insert >>---------*/
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);
}
}
}
}
}
/*-------<<
Function defination for Delete >>---------*/
void btree::Delete(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)
{
for(i=right->noofkeys-1;i>=0;i--)
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;
}
}
}
/*-----------<< Main Function Starts >>---------*/
void main()
{
int n,i,x,ch;
node *p;
clrscr();
cout<<"\nEnter the order of B
tree : ";
cin>>n;
btree b(n);
do
{
cout<<"\n\n\t----<<
MENU >>----";
cout<<"\n\t1.Insert";
cout<<"\n\t2.Search";
cout<<"\n\t3.Delete";
cout<<"\n\t4.Print";
cout<<"\n\t5.Quit";
cout<<"\n\t-------------------";
cout<<"\n\tEnter
your choice : ";
cin>>ch;
switch(ch)
{
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<<"\nFound
in the node : ";
p->display();
}
else
cout<<"\nNot
found";
break;
case 3:
cout<<"\nEnter a data : ";
cin>>x;
p=b.search(x);
if(p!=NULL)
{
b.Delete(x);
b.displaytree();
}
else
cout<<"\nNot
found";
break;
case 4:
b.displaytree();
break;
}
}while(ch!=5);
}
/*--------<< End Of Main Function >>------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
Enter
the order of B tree : 3
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 1
Tree
after insertion :
(1
)
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 32
Tree
after insertion :
(1
32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 8
Tree
after insertion :
(1
8 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 11
Tree
after insertion :
(11
)
(1
8 ) (32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 15
Tree
after insertion :
(11
)
(1
8 ) (15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice :1
Enter
a data : 5
Tree
after insertion :
(11
)
(1
5 8 ) (15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 1
Enter
a data : 4
Tree
after insertion :
(5
11 )
(1
4 ) (8 )
(15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 2
Enter
a data : 15
Found
in the node : (15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 3
Enter
a data : 8
(4
11 )
(1
) (5 )
(15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 4
(4
11 )
(1
) (5 )
(15 32 )
----<< MENU >>----
1.Insert
2.Search
3.Delete
4.Print
5.Quit
-------------------
Enter your choice : 5
No comments:
Post a Comment