B-Tree using Class
Write a C++ Program to implement B-Tree using Class. Here’s a Simple Program to implement B-Tree using Class using Linked Lists in C++ Programming Language.
What is Class and Objects in C++?
- The classes are the most important feature of C++ that leads to Object Oriented programming.
- Class is a user defined data type, which holds its own data members and member functions, which can be accessed and used by creating instance of that class.
- The variables inside class definition are called as data members and the functions are called member functions.
- Class is just a blue print, which declares and defines characteristics and behavior, namely data members and member functions respectively. And all objects of this class will share these characteristics and behavior.
- Objects are instances of class, which holds the data variables declared in class and the member functions work on these class objects.
- Each object has different data variables. Objects are initialized using special class functions called Constructors.
Below is the source code for Program to implement B-Tree using Class using Linked Lists which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* C++ Program to implement B-Tree using Class using Linked Lists */
#include <iostream>
#include <stdlib.h>
using namespace std;
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 ( int 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 )
{
int i=0;
if ( root != NULL )
{
for ( 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 )
{
int i=0;
if ( root != NULL )
{
for (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 ) ;
}
int 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( ) ;
cout<<"\n";
return 0;
}
OUTPUT : :
/* C++ Program to implement B-Tree using Class using Linked Lists */ B-tree of order 5: 2 13 22 27 32 40 42 47 51 Value 11 not found. B-tree after deletion of values: 2 13 27 32 40 42 47 51 Process returned 0
Above is the source code and output for C++ Program to implement B-Tree using Class using Linked Lists which is successfully compiled and run on Windows System to produce desired output.
If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach upto you in the short interval.
Thanks for reading the post….