RSS

Category Archives: C/C++

Binary Search Tree (BST)

Binary Search Tree (BST)

#include<stdio.h>
#include<process.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int info;
struct node *left;
struct node *right;
struct node *p;
};
node *root,*deep,*x;
int n,lr;
void insert();
void op();
void kl();
void in(struct node*);
void pre(struct node*);
void post(struct node*);
void main()
{
root=NULL;
op();
}
void op()
{
int f;
printf(“\npress 1 for enter element\npress 2 for left rotation\npress 3 for print preorder\n press 4 for exit”);
scanf(“%d”,&f);
switch(f)
{
case 1:kl();
break;
case 2:leftrotate();
break;
case 3:pre(root);
break;
case 4:exit(1);
default : op();
break;
}
}
void kl()
{
printf(“enter element”);
scanf(“%d”,&n);
if(root==NULL)
{
root=(node*)malloc(sizeof(node));
root->info=n;
root->left=NULL;
root->right=NULL;
root->p=NULL;
}
else
{
deep=root;
insert();
}
op();
}
void insert()
{
node *ptr,*rtf;
ptr=(node*)malloc(sizeof(node));
ptr->info=n;
if(n<deep->info)
{
while(deep->left!=NULL)
{
rtf=deep->left;
if(rtf->info<ptr->info)
break;
deep=deep->left;
}
if(deep->left==NULL)
{
ptr->left=NULL;
ptr->right=NULL;
deep->left=ptr;
}
else if(rtf->info<ptr->info)
{
deep=deep->left;
insert();
}
}
else if(n>deep->info)
{
while(deep->right!=NULL)
{
rtf=deep->right;
if(rtf->info>ptr->info)
break;
deep=deep->right;
}
if(deep->right==NULL)
{
ptr->left=NULL;
ptr->right=NULL;
deep->right=ptr;
ptr->p=deep;}
else if(rtf->info>ptr->info)
{
deep=deep->right;
insert();
}
}
op();
}
void pre(struct node *root)
{
if(root!=NULL)
{
printf(“%d\t”,root->info);
pre(root->left);
pre(root->right);
}
}
Advertisements
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

AVL Trees

Program for insertion in AVL tree


#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
#include<process.h>
#include<malloc.h>

typedef enum { FALSE,TRUE } bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
bool ht_inc;
};

struct node *insert (int , struct node *);
struct node* search(struct node *,int);

main()
{

int info ;
int choice;
struct node *root = (struct node *)malloc(sizeof(struct node));
root = NULL;

while(1)
{
printf(“1.Insert\n”);
printf(“2.Display\n”);
printf(“3.Quit\n”);
printf(“Enter your choice : “);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“Enter the value to be inserted : “);
scanf(“%d”, &info);
if( search(root,info) == NULL )
root = insert(info, root);
else
printf(“Duplicate value ignored\n”);
break;
case 2:
if(root==NULL)
{
printf(“Tree is empty\n”);
continue;
}
printf(“Tree is :\n”);
display(root, 1);
printf(“\n\n”);
printf(“Inorder Traversal is: “);
inorder(root);
printf(“\n”);
break;
case 3:
exit(1);
default:
printf(“Wrong choice\n”);
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
if(info < ptr->info)
ptr=search(ptr->lchild,info);
else if( info > ptr->info)
ptr=search(ptr->rchild,info);
return(ptr);
}/*End of search()*/

struct node *insert (int info, struct node *pptr, int *ht_inc)
{
struct node *aptr;
struct node *bptr;

if(pptr==NULL)
{
pptr = (struct node *) malloc(sizeof(struct node));
pptr->info = info;
pptr->lchild = NULL;
pptr->rchild = NULL;
pptr->balance = 0;
*ht_inc = TRUE;
return (pptr);
}

if(info < pptr->info)
{
pptr->lchild = insert(info, pptr->lchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case -1: /* Right heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = 1;
break;
case 1: /* Left heavy */
aptr = pptr->lchild;
if(aptr->balance == 1)
{
printf(“Left to Left Rotation\n”);
pptr->lchild= aptr->rchild;
aptr->rchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf(“Left to right rotation\n”);
bptr = aptr->rchild;
aptr->rchild = bptr->lchild;
bptr->lchild = aptr;
pptr->lchild = bptr->rchild;
bptr->rchild = pptr;

if(bptr->balance == 1 )
pptr->balance = -1;
else
pptr->balance = 0;
if(bptr->balance == -1)
aptr->balance = 1;
else
aptr->balance = 0;
bptr->balance=0;
pptr=bptr;
}
*ht_inc = FALSE;
}/*End of switch */
}/*End of if */
}/*End of if*/

if(info > pptr->info)
{
pptr->rchild = insert(info, pptr->rchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case 1: /* Left heavy */
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0: /* Balanced */
pptr->balance = -1;
break;
case -1: /* Right heavy */
aptr = pptr->rchild;
if(aptr->balance == -1)
{
printf(“Right to Right Rotation\n”);
pptr->rchild= aptr->lchild;
aptr->lchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf(“Right to Left Rotation\n”);
bptr = aptr->lchild;
aptr->lchild = bptr->rchild;
bptr->rchild = aptr;
pptr->rchild = bptr->lchild;
bptr->lchild = pptr;

if(bptr->balance == -1)
pptr->balance = 1;
else
pptr->balance = 0;
if(bptr->balance == 1)
aptr->balance = -1;
else
aptr->balance = 0;
bptr->balance=0;
pptr = bptr;
}/*End of else*/
*ht_inc = FALSE;
}/*End of switch */
}/*End of if*/
}/*End of if*/

return(pptr);
}/*End of insert()*/

void display(struct node *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf(“\n”);
for (i = 0; i < level; i++)
printf(” “);
printf(“%d”, ptr->info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display()*/

void inorder(struct node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf(“%d “,ptr->info);
inorder(ptr->rchild);
}
}/*End of inorder()*/
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

B-Tree of Degree 3

Program which maintains a B-tree of degree 3.


#include <iostream.h>
#include <stdlib.h>
#include <alloc.h>
const int MAX = 5 ;
const int MIN = 3 ;
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( ) ;
} ;

// initialises data member
btree :: btree( )
{root = NULL ;
}
// 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 ;
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 )
{
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 ;

mid=MIN;
*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– ;
}

// deletes value from the node
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 ;
}
}
}
// helper function for del( )
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 ;
}
}
// 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] ;
}
// adjusts the node
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 ) ;
}
}
}
}
// adjusts the values and children while shifting the value from parent to right child
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– ;
}
// adjusts the values and children while shifting the value from parent to left child
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] ;
}
}
// 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 ;
int n,m;
while(1)
{
cout<<“\nwhat u want\ninsertion\n2-deletion\n3-display”;
cin>>n;
if(n==1)
{cout<<“\nenter the no to insert”;
cin>>m;
b.insert(m);
}
if(n==2)
{cout<<“enter the no to delete:”;
cin>>m;
b.del(m);
}
if(n==3)
b.show();

}


}
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Priority Queue

C++ code for implementing Priority Queue:

 

#include<iostream.h>
#include<conio.h>
int i=0,n=0,l,r,heapsize,smallest,temp,j,B[100],C[100],k;

int parent(int i)
{int x;
if(i%2==0)
x=i%2;
else
x=(i-1)/2;
return x;
}

void minpriority(int A[],int i)
{

l=2*i;//left of i
r=1+l;//right of i
if(l<=heapsize && A[l]<A[i])
smallest=l;
else
smallest=i;
if(r<=heapsize && A[r]<A[smallest])
smallest=r;
if(smallest!=i)
{
temp=A[i];
A[i]=A[smallest];
A[smallest]=temp;
minpriority(A,smallest);
}
}


void buildminpriority(int A[])
{
heapsize=n-1;
for(i=n-1;i>=0;i–)
minpriority(A,i);
}

void decreasekey(int A[],int i,int key)
{
if(key>A[i])
cout<<“New key is greater than current key, hence no decreasing.”<<endl;
else
{A[i]=key;
while(i>=0 && A[parent(i)]>A[i])
{temp=A[i];
A[i]=A[parent(i)];
A[parent(i)]=temp;
i=parent(i);}
}
}


void insert(int A[],int key)
{

A[heapsize]=10000;
decreasekey(A,heapsize,key);
}


void extractmin(int A[],int i)
{int min;
if(heapsize<0)
cout<<“Heap Underflow”<<endl;
else
{min=A[0];
A[0]=A[heapsize];
heapsize=heapsize-1;
minpriority(A,0);
cout<<“Value of Minimum is:”<<min<<endl;
}}









void main()
{

cout<<“Enter the size of the array”<<endl;
cin>>n;

cout<<“Enter the values”<<endl;
for(j=0;j<n;j++)
{cin>>B[j];
}

cout<<“Enter the key”<<endl;
cin>>k;
cout<<“Values of priority queue initially:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;


buildminpriority(B);
cout<<“Values of priority queue after building:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;



extractmin(B,i);
cout<<“Values of priority queue after extracting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




decreasekey(C,i,k);
cout<<“Values of priority queue after decreasing key:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;




insert(B,k);
cout<<“Values of priority queue after inserting:”<<endl;
for(j=0;j<n;j++)
cout<<B[j]<<” “;
cout<<endl;
}//end main

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Building Max Heap

Code for Max Heap… Shows the use of MaxHeapify:

#include<iostream.h>
#include<math.h>
int size;
void maxheapify(int a[],int i,int size)
{
int l,r,largest,temp;
l=2*i;
r=(2*i+1);
if((l<=size) && (a[l]>a[i]))
largest=l;
else
largest=i;
if((r<=size) && (a[r]>a[largest]))
largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,largest,size);
}
};
void buildmaxheap(int a[],int size)
{
int i;
for(i=floor(size/2);i>=1;i–)
{
maxheapify(a,i,size);
}
}
int extract_max(int*a,int size)
{
int max;
max=a[1];
a[1]=a[size];
size–;
maxheapify(a,1,size);
return(max);
}
void main()
{
int p,k,i,max,a[20],temp;
cout<<“How many no u want 2 enter\n”;
cin>>size;
cout<<“Enter no\n”;
for(i=1;i<=size;i++)
{
cin>>a[i];
}
buildmaxheap(a,size);
cout<<“Enter the value of k\n”;
cin>>k;
if(k>size)
cout<<“The value entered is greater than heap size\n”;
else
{
for(i=0;i<k;i++)
{
max=extract_max(a,size);
}
cout<<“The kth largest element is:-    “<<max;
}
}
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Merge Sort

C Program for implementing merge-sort

#include<conio.h>
#include<stdio.h>
#define MAX 5

int a[MAX],i;
void meage_sort(int a[],int,int);
void split(int a[],int,int,int,int);
void main()
{
clrscr();
for (int i=0;i<MAX;i++)
{
printf(“\n enter %d element “,i+1);
scanf(“%d”,&a[i]);
}
meage_sort(a,0,MAX-1);
printf(“\n UR DATA AFTER SORTING\n “);
for(i=0;i<MAX;i++)
{
printf(“%d->”,a[i]);
}
getch();
}

void meage_sort(int a[],int lower, int upper)
{
int mid;

if(lower<upper)
{
mid=(lower+upper)/2;
meage_sort(a,lower,mid);
meage_sort(a,mid+1,upper);
split(a,lower,mid,mid+1,upper);
}
}
void split(int a[],int low1,int up1,int low2,int up2)
{
int p,q,j,n;
int temp[MAX];
p=low1;
q=low2;
n=0;
while((p<=up1) && (q<=up2))
temp[n++]=(a[p] < a[q] ? a[p++]:a[q++]);
while(p<=up1)
temp[n++]=a[p++];
while(q<=up2)
temp[n++]=a[q++];

for(q=low1,n=0 ;q<=up1 ;q++,n++)
a[q]=temp[n];
for(q=low2,j=n ;q<=up2 ;q++,j++)
a[q]=temp[j];
}

 

 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Insertion/Deletion in B tree

Program of insertion and deletion in B tree

 

#include
#include
#define M 5

struct node{
int n; /* n < M No. of keys in node will always less than order of B
tree */
int keys[M-1]; /*array of keys*/
struct node *p[M]; /* (n+1 pointers will be in use) */
}*root=NULL;

enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };

void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);

int main()
{
int key;
int choice;
printf(“Creation of B tree for node %d\n”,M);
while(1)
{
printf(“1.Insert\n”);
printf(“2.Delete\n”);
printf(“3.Search\n”);
printf(“4.Display\n”);
printf(“5.Quit\n”);
printf(“Enter your choice : “);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“Enter the key : “);
scanf(“%d”,&key);
insert(key);
break;
case 2:
printf(“Enter the key : “);
scanf(“%d”,&key);
DelNode(key);
break;
case 3:
printf(“Enter the key : “);
scanf(“%d”,&key);
search(key);
break;
case 4:
printf(“Btree is :\n”);
display(root,0);
break;
case 5:
exit(1);
default:
printf(“Wrong choice\n”);
break;
}/*End of switch*/
}/*End of while*/
return 0;
}/*End of main()*/

void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf(“Key already available\n”);
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/

enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node
**newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M – 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i–)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is
last*/
if (pos == M – 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted
is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i–)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M – 1)/2;
(*upKey) = ptr->keys[splitPos];

(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n – 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/

void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(” “);
for (i=0; i < ptr->n; i++)
printf(“%d “,ptr->keys[i]);
printf(“\n”);
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/

void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf(“Search path:\n”);
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(” %d”,ptr->keys[i]);
printf(“\n”);
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf(“Key %d found in position %d of last dispalyed
node\n”,key,i);
return;
}
ptr = ptr->p[pos];
}
printf(“Key %d is not available\n”,key);
}/*End of search()*/

int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/

void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf(“Key %d is not available\n”,key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/

enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;

if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M – 1)/2;/*Minimum number of keys*/

pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return –ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */

if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey – 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;

if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos – 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i–)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[–lptr->n];
return Success;
}/*End of if */
if (posn > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n–;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */

if(pos == n)
pivot = pos-1;
else
pivot = pos;

lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return –ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/

 

 

 
Leave a comment

Posted by on March 8, 2011 in C/C++