#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( ) ;
} |
C++ program to implement Binary Search Tree(BST) and its Operations
C++ program to implement AVL Tree & its Operations
C++ program to implement Queue using Formula Based Representation
C++ program for creation and traversal of a Binary Tree
C++ program to implement Hash Table
C++ program to implement Queue using Linked Representation
C++ program to implement the Queue ADT using a single linked list
plz show comments wid lines so that it becomes clear n easy to undrstand…..
thnk u…
plz add comments to this code asap………i’m in great need of this code for my project…….
and i’m not getting any help from anywhere else for implementing btrees.
thank you
plz rply to my msgs……its really important for me.
looking tough….i read several times but i didn’t understood….please specify comment lines….thanku
very nice ! ! ! ! ! !
your program was really nice,and I want to change it into B+tree.can you help me?
not working
not working with Microsoft visual c++.. any procedure ?? pls help ..
what is the purpose of the search function ? Where is it being used?
It helped
Thank you
its nice!!!!!!!!!!!!!!!!!!!!!
itz awsme……………..thanku
reduce the length of code and make it simple so that human beings can understand.
y this is kolaveri kolaveri Mr.ranjith
Thank you so much !!
A few helpful edits:
One of the lines in merge is incorrect- you set temp2′s child final pointer equal to the roots child 0, which is itself. This leads to an infinite loop when trying to print or delete etc.
The corrected version is below:
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 -> temp1[0] ; // <– this line is the changed line
Also, I dont understand why your leftshift rightshift and merge all use the root instead of a passed node. Maybe this works, but I found that I had to pass in the node I was currently working on instead of using the root. My full edited rightshift, leftshift, and merge functions are below.
template
void BTree::leftshift( int k, BTreeNode * t){
BTreeNode * temp;
temp = t -> ptr[k-1];
temp->totalKeys++;
temp->keys[temp->totalKeys] = t -> keys[k];
temp->ptr[temp->totalKeys] = t -> ptr[k] -> ptr[0];
temp= t->ptr[k];
t->keys[k] = temp -> keys[1];
temp->ptr[0] = temp-> ptr[1];
temp->totalKeys–;
for (int i=1; i totalKeys; i++){
temp->keys[i] = temp->keys[i+1];
temp->ptr[i] = temp->ptr[i+1];
}
}
template
void BTree::rightshift( int i, BTreeNode * t) {
BTreeNode *temp, *temp2;
temp = t -> ptr[i];
temp2 = t -> ptr[i-1];
for (int j=temp->totalKeys; j >0; j–){
temp->keys[j+1] = temp->keys[j];
temp->ptr[j+1] = temp->ptr[j];
}
temp->ptr[1] = temp-> ptr[0];
temp->totalKeys++;
temp->keys[1] = t->keys[i];
t->keys[i] = temp2 -> keys[temp2->totalKeys];
t->ptr[i]->ptr[0] = temp2 -> ptr[temp2->totalKeys];
temp2->totalKeys–;
}
template
void BTree::merge(int i, BTreeNode * t){
BTreeNode *temp1, *temp2;
temp1 = t -> ptr[i];
temp2 = t ->ptr[i-1];
temp2 -> totalKeys++;
temp2 ->keys[temp2->totalKeys] = t->keys[i];
temp2 ->ptr[temp2->totalKeys] = temp1->ptr[0];
for (int j = 1; j totalKeys; j++ ) {
temp2 -> totalKeys++;
temp2-> keys[temp2->totalKeys] = temp1 -> keys[j];
temp2-> ptr[temp2->totalKeys] = temp1 -> ptr[j];
}
for (int j = i; j totalKeys; j++ ) {
t-> keys[j] = t -> keys[j+1];
t-> ptr[j] = t -> ptr[j+1];
}
t->totalKeys–;
delete temp1;
}
plz send the program with short code…nt lengthy one…
Hello,
Nice program but too long to get into my head. Looks like you copied this from another site. Write a short program ASAP, else I’m gonna kick your ass.
I need c# code of this!!does anybody have it???
asdasd.