#include <iostream.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 fillnode ( int val, btnode *c, btnode *n, int k ) ;
		void split ( int val, btnode *c, btnode *n,
				int k, int *y, btnode **newnode ) ;
		void del ( int val ) ;
		int delhelp ( int val, btnode *root ) ;
		void clear ( btnode *root, int k ) ;
		void copysucc ( btnode *root, int i ) ;
		void restore ( btnode *root, int i ) ;
		void rightshift ( int k ) ;
		void leftshift ( int k ) ;
		void merge ( int k ) ;
		void show( ) ;
		static void display ( btnode *root ) ;
		static void deltree ( btnode *root ) ;
		~btree( ) ;
} ;

btree :: btree( )
{
	root = NULL ;
}
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 ;
	}
}
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 ;
		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 ;
	}
}
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 ) ;
	}
}
int btree :: searchnode ( int val, btnode *n, int *pos )
{
	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 ;
	}
}
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++ ;
}
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-- ;
}
void btree :: del ( int val )
{
	btnode * temp ;

	if ( ! delhelp ( val, root ) )
		cout << endl << "Value " << val << " not found." ;
	else
	{
		if ( root -> count == 0 )
		{
			temp = root ;
			root = root -> child[0] ;
			delete temp ;
		}
	}
}
int btree :: delhelp ( int val, btnode *root )
{
	int i ;
	int flag ;

	if ( root == NULL )
		return 0 ;
	else
	{
		flag = searchnode ( val, root, &i ) ;
		if ( flag )
		{
			if ( root -> child[i - 1] )
			{
				copysucc ( root, i ) ;
				flag = delhelp ( root -> value[i], root -> child[i] ) ;
				if ( !flag )
					cout << endl << "Value " << val << " not found." ;
			}
			else
				clear ( root, i ) ;
		}
		else
			flag = delhelp ( val, root -> child[i] ) ;
		if ( root -> child[i] != NULL )
		{
			if ( root -> child[i] -> count < MIN )
				restore ( root, i ) ;
		}
		return flag ;
	}
}
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-- ;
}
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] ;
}
void btree :: restore ( btnode *root, int i )
{
	if ( i == 0 )
	{
		if ( root -> child [1] -> count > MIN )
			leftshift ( 1 ) ;
		else
			merge ( 1 ) ;
	}
	else
	{
		if ( i == root -> count )
		{
			if ( root -> child[i - 1] -> count > MIN )
				rightshift ( i ) ;
			else
				merge ( i ) ;
		}
		else
		{
			if ( root -> child[i - 1] -> count > MIN )
				rightshift ( i ) ;
			else
			{
				if ( root -> child[i + 1] -> count > MIN )
					leftshift ( i + 1 ) ;
				else
					merge ( i ) ;
			}
		}
	}
}
void btree :: rightshift ( int k )
{
	int i ;
	btnode *temp ;

	temp = root -> child[k] ;

	for ( i = temp -> count ; i > 0 ; i-- )
	{
		temp -> value[i + 1] = temp -> value[i] ;
		temp -> child[i + 1] = temp -> child[i] ;
	}

	temp -> child[1] = temp -> child[0] ;
	temp -> count++ ;
	temp -> value[1] = root -> value[k] ;
	temp = root -> child[k - 1] ;
	root -> value[k] = temp -> value[temp -> count] ;
	root -> child[k] -> child [0] = temp -> child[temp -> count] ;
	temp -> count-- ;
}
void btree :: leftshift ( int k )
{
	btnode *temp ;

	temp = root -> child[k - 1] ;
	temp -> count++ ;
	temp -> value[temp -> count] = root -> value[k] ;
	temp -> child[temp -> count] = root -> child[k] -> child[0] ;
	temp = root -> child[k] ;
	root -> value[k] = temp -> value[1] ;
	temp -> child[0] = temp -> child[1] ;
	temp -> count-- ;
	for ( int i = 1 ; i <= temp -> count ; i++ )
	{
		temp -> value[i] = temp -> value[i + 1] ;
		temp -> child[i] = temp -> child[i + 1] ;
	}
}
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 ;
}
void btree :: show( )
{
	display ( root ) ;
}
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] ) ;
	}
}
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 ;
	int arr[ ] = { 27, 42, 22, 47, 32, 2, 51, 40, 13 } ;
	int sz = sizeof ( arr ) / sizeof ( int ) ;
	for ( int i = 0 ; i < sz ; i++ )
		b.insert ( arr[i] ) ;
	cout << "B-tree of order 5:" << endl ;
	b.show( ) ;
	b.del ( 22 ) ;
	b.del ( 11 ) ;
	cout << "\n\nB-tree after deletion of values:" << endl ;
	b.show( ) ;
}