Prog-9

#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." << endl ;

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<<"1 - 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";

}

}

}