File Structure ( FS ) Lab Program 9 ( 6th Semester Information Science)

This post was published long ago, when I was a student and an amateur blogger. The links might be outdated and content may not be useful anymore. Please read this content keeping its age in mind.

Program 9 : Write a C++ program to implement B-Tree for a given set of integers and its operations insert ( ) and search ( ). Display the tree.

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>

const int MAX = 4 ;
const int MIN = 2 ;

struct btnode
{
int count;
int value[MAX + 1];
btnode *child[MAX + 1];
};

class btree
{
private : btnode *root ;
public : btree( ) ;
void insert(int val) ;
int setval(int val, btnode *n, int *p, btnode **c);
static btnode *search (int val, btnode *root, int *pos);
static int searchnode(int val, btnode *n, int *pos);
void iskeypresent( int val) ;
void fillnode( int val, btnode *c, btnode *n, int k );
void split( int val, btnode *c, btnode *n, int k, int *y, btnode **newnode );
void clear( btnode *root, int k );
void copysucc( btnode *root, int i );
void merge( int k ) ;
void show( );
static void display( btnode *root );
static void deltree( btnode *root );
~btree( );
};

// initialises data member
btree :: btree( )
{
root=NULL;
}

// searches a key and checks whether it is present or not
void btree :: iskeypresent(int val)
{
int i ;
if( searchnode ( val, root, &i ) )
cout<< “Key found “<<endl;
else
cout<< “Key Not found “<<endl;
}

// inserts a value in the B-tree
void btree :: insert ( int val )
{
int i ;
btnode *c, *n ;
int flag ;
flag = setval( val, root, &i, &c ) ;
if( flag )
{
n = new btnode ;
n -> count = 1 ;
n -> value[1] = i ;
n -> child[0] = root ;
n -> child[1] = c ;
root = n ;
}
}

// sets the value in the node
int btree :: setval ( int val, btnode *n, int *p, btnode **c)
{
int k ;
if ( n == NULL )
{
*p = val ;
*c = NULL ;
return 1 ;
}
else
{
if( searchnode ( val, n, &k ) )
{
cout << endl << “Key value already exists”;
return 0 ;
}
if ( setval ( val, n -> child[k], p, c ) )
{
if ( n -> count < MAX )
{
fillnode ( *p, *c, n, k ) ;
return 0 ;
}
else
{
split ( *p, *c, n, k, p, c ) ;
return 1 ;
}
}
return(0);
}
}

// searches value in the node
btnode * btree :: search ( int val, btnode root, int *pos )
{
if ( root == NULL ) return NULL ;
else
{
if ( searchnode ( val, root, pos ) )
return root ;
else
return search ( val, root -> child[pos], pos ) ;
}
}

// searches for the node
int btree :: searchnode ( int val, btnode n, int *pos )
{
//this condition is used to decide the traversal
if ( val < n -> value[1] )
{
*pos = 0 ;
return 0 ;
}
else
{
*pos = n -> count ;
while ( ( val < n -> value[pos] ) && pos > 1 )
(pos)– ;
if ( val == n -> value[*pos] )
return 1 ;
else
return 0 ;
}
}

// adjusts the value of the node
void btree :: fillnode ( int val, btnode *c, btnode *n, int k )
{
int i ;
for ( i = n -> count ; i > k ; i– )
{
n -> value[i + 1] = n -> value[i] ;
n -> child[i + 1] = n -> child[i] ;
}
n -> value[k + 1] = val ;
n -> child[k + 1] = c ;
n -> count++ ;
}

// splits the node
void btree :: split ( int val, btnode *c, btnode *n, int k, int *y, btnode **newnode )
{
int i, mid ;
if ( k <= MIN )
mid = MIN ;
else
mid = MIN + 1 ;
*newnode = new btnode ;
for ( i = mid + 1 ; i <= MAX ; i++ )
{
( *newnode ) -> value[i – mid] = n -> value[i] ;
( *newnode ) -> child[i – mid] = n -> child[i] ;
}
( *newnode ) -> count = MAX – mid ;
n -> count = mid ;
if ( k <= MIN )
fillnode ( val, c, n, k ) ;
else
fillnode ( val, c, *newnode, k – mid ) ;
*y = n -> value[n -> count] ;
( *newnode ) -> child[0] = n -> child[n -> count] ;
n -> count– ;
}

// removes the value from the node and adjusts the values
void btree :: clear ( btnode *root, int k )
{
int i ;
for ( i = k + 1 ; i <= root -> count ; i++ )
{
root -> value[i – 1] = root -> value[i] ;
root -> child[i – 1] = root -> child[i] ;
}
root -> count– ;
}

// copies the successor of the value that is to be deleted
void btree :: copysucc ( btnode *root, int i )
{
btnode *temp = root -> child[i] ;
while ( temp -> child[0] )
temp = temp -> child[0] ;
root -> value[i] = temp -> value[1] ;
}

// merges two nodes
void btree :: merge ( int k )
{
btnode *temp1, *temp2 ;
temp1 = root -> child[k] ;
temp2 = root -> child[k – 1] ;
temp2 -> count++ ;
temp2 -> value[temp2 -> count] = root -> value[k] ;
temp2 -> child [temp2 -> count] = root -> child[0] ;
for ( int i = 1 ; i <= temp1 -> count ; i++ )
{
temp2 -> count++ ;
temp2 -> value[temp2 -> count] = temp1 -> value[i] ;
temp2 -> child[temp2 -> count] = temp1 -> child[i] ;
}
for ( i = k ; i < root -> count ; i++ )
{
root -> value[i] = root -> value[i + 1] ;
root -> child[i] = root -> child[i + 1] ;
}
root -> count– ;
delete temp1 ;
}

// calls display( )
void btree :: show( )
{
display ( root ) ;
}

// displays the B-tree
void btree :: display ( btnode *root )
{
if ( root != NULL )
{
for ( int i = 0 ; i < root -> count ; i++)
{
display ( root -> child[i] ) ;
cout << root -> value[i + 1] << “t”;
}
display ( root -> child [i] ) ;
}
}

// deallocates memory
void btree :: deltree ( btnode *root )
{
if ( root != NULL )
{
for ( int i = 0 ; i < root -> count ; i++)
{
deltree ( root -> child [i] ) ;
delete ( root -> child[i] ) ;
}
deltree ( root -> child[i] ) ;
delete ( root -> child[i] ) ;
}
}

btree :: ~btree( )
{
deltree ( root ) ;
}

void main( )
{
btree b ;
clrscr();
int num;
int choice=0;
while (choice!=4)
{
cout<<endl<<“l – Insert”<<endl;
cout<<“2 – Search”<<endl;
cout<<“3 – Display”<<endl;
cout<<“4 – Exit”<<endl;
cout<<“Enter your choice”<<endl;
cin>>choice;
switch(choice)
{
case 1:  cout<<“nEnter the elements to be inseretd into b tree n”;
cin>>num;
b.insert ( num ) ;
break;
case 2:  cout<<“nEnter the elements to be searched in b tree n”;
cin>>num;
b.iskeypresent ( num ) ;
break;
case 3:  b.show( ) ;
break;
case 4:  exit(0);
default: cout<<“nInvalid Option n”;
}
}
}