•Algorithm
Perform
search for value X
If X
is a leaf, delete X
Else //
must delete internal node
a)
Replace with largest value Y on left subtree
OR
smallest value Z on right subtree
b)
Delete
replacement value (Y or Z) from subtree
–O( log(n) ) operation for balanced
tree
–Deletions may unbalance tree
Example Deletion (Leaf)
Related post : Binary Search Tree (BST)
Related post : SEE C PRogram for BST
Related post : selection sort
C Program : ALL operation on BST
// all operation on Binary Search Tree
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
struct node *lc;
struct node *rc;
char data;
};
typedef struct node node; //typedef
void insert(node **,char);
void inorder(node *);
void preorder(node *);
void postorder(node *);
void search(node **,node **,node **,char,int *);
void del(node **,char);
void main()
{
node *root;
root=NULL;
int i,k;
char c;
printf("\n NO of element u wan't to insert :");
scanf("%d",&k);
getchar(); // use to take enter as input in to buffer to prevent it as input in next char input
for(i=0;i<k;i++)
{
printf("\n insert %dth charactor element :",i+1);
scanf("%c",&c);
getchar();
insert(&root,c);
}
/*----------------------------operation--------------------------*/
while(1)
{
printf("\n\n\n 1 for deletion :");
printf("\n 2 for traversal :");
printf("\n any other no to exit\n");
printf("\n\n enter ur choice :");
scanf("%d",&k);
getchar();
switch(k)
{
case 1:
printf("\n enter character u wan't to delete : ");
scanf("%c",&c);
getchar();
del(&root,c);
break;
case 2:
/*------------------------------------traversal-------------------------------*/
printf("\n inorder traversal :\n");
inorder(root);
printf("\n preorder traversal :\n");
preorder(root);
printf("\n postorder traversal :\n");
postorder(root);
/*-----------------------End of traversal-------------------------------*/
break;
default :
exit(0);
break;
}
}
/*---------------------------end of operation--------------------------------*/
}// end of main
/*------------------------------funtion definations--------------------------*/
void insert(node **tr,char c)
{
if(*tr==NULL) // tree is empty so insert as first node
{
*tr=(node *)malloc(sizeof(node));
(*tr)->data=c;
(*tr)->rc=NULL;
(*tr)->lc=NULL;
}
else
{
if(c <(*tr)->data)
{
insert(&(*tr)->lc,c);
}
else
insert(&(*tr)->rc,c);
}
}
void inorder(node *tr)
{
if(tr!=NULL)
{
inorder(tr->lc);
printf(" %c ",tr->data);
inorder(tr->rc);
}
}
void preorder(node *tr)
{
if(tr!=NULL)
{
printf(" %c ",tr->data);
preorder(tr->lc);
preorder(tr->rc);
}
}
void postorder(node *tr)
{
if(tr !=NULL)
{
postorder(tr->lc);
postorder(tr->rc);
printf(" %c ",tr->data);
}
}
void del(node **root,char ch)
{
int found;
node *par=NULL,*rnode=NULL,*rnode_succ=NULL; //rnode=requre node(node to be delete)
if(*root==NULL) // rnode_succ=inorder successor of "rnode"
{
printf("\n list is empty :");
return;
}
/*call search funtion to find node to be delete*/
search(root,&par,&rnode,ch,&found);
if(found == 0) // requre node not found
{
printf("\nthis character is not found in list:");
return;
}
/*case A=>if node to be delete have to child */
if(rnode->lc!=NULL && rnode->rc!=NULL)
{
/*now find out inorder succesor of rnode .It replace rnode after deletion*/
par=rnode;
rnode_succ = rnode->rc;
while(rnode_succ->lc != NULL)
{
par=rnode_succ;
rnode_succ=rnode_succ->lc;
}//search for inorder succesoso complete
rnode->data=rnode_succ->data;// assigning volue of rnode_succ to rnode
rnode=rnode_succ; //confusing point...
/* because rnode_succ may have right child.. now we delete
rnode_succ .for that
we assign new "rnode" & "par" which will deleted according to
condition they satisfy in further conditions of deletion !*/
}
/*case_B_1=if node has to delete has only one child that is right*/
if(rnode->lc==NULL && rnode->rc!=NULL)
{
if(par->lc==rnode)
par->lc=rnode->rc;
else
par->rc=rnode->rc;
free(rnode); // free memory space
return;
}
/*case_B_2=if node to deleted have only one child that is right child*/
if(rnode->lc!=NULL && rnode->rc==NULL)
{
if(par->lc==rnode)
par->lc=rnode->lc;
else
par->rc=rnode->rc;
free(rnode); // free memory space of node deleted
return;
}
/*case C=> if node to be delete is leaf node i.e have no child*/
if(rnode->lc==NULL && rnode->rc==NULL)
{
if(par->lc==rnode)
par->lc=NULL;
else
par->rc=NULL;
free(rnode);// free memory space
return;
}
}
void search(node **root,node **par,node **rnode,char ch,int *f)
{
*f=0;
node *q=NULL;
q=*root;
while(q!=NULL)
{
/*if node t be deleted is found*/
if(q->data == ch)
{
*f = 1;
*rnode=q;
//printf(" jhbjdvfv= %d",*f);
return;
}
//printf("data find - %c\n",q->data);
*par=q;
if(q->data > ch)
{
q=q->lc;
}
else
q=q->rc;
}
}
OUTPUT :
No comments:
Post a Comment
THANKS FOR UR GREAT COMMENT