## Monday, 21 October 2013

### Search & Deletion in Binary search Tree ( BST )

In previous discussion we discus about Binary search tree Now we have to do some basic operation on binary search tree.

#### Searching a element : it is not a tough job in BST .follow simple algorithm

>> compare root node data with require data if equal search complete otherwise if less that root node move to left else move to right child.
follow this steps for all nodes until NULL encounter it is condition for unsuccessful search.

#### Delete a element : It is slightly tough . first search node position & its parent node. location.than deletion process starts : :

There are four type of cases encounter :

>> node to be delete have no child (i.e leaf node ) = you can delete it directly .just like delete last element of one way link list.

>> node to be delete have one left child . = also simple just like delete first node in One way link list .

>>  node to be delete have one right child = similar as above.

>> Node to be delete have two child = than find its inorder successor than replace node value by of its inorder successor . than delete that inorder successor.

To read it with more detail Download : Binary search tree complete .

#### C PRogram :

`````` // 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()
{
int i,k;
char c;
node *root;
root=NULL;
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)
{
node *q=NULL;
q=*root;
*f=0;
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 :

1. Thanks bro .. thanks very much for this

2. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in Data Science with Python , kindly contact us http://www.maxmunus.com/contact
MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
Sangita Mohanty
MaxMunus
E-mail: sangita@maxmunus.com
Skype id: training_maxmunus
Ph:(0) 9738075708 / 080 - 41103383
http://www.maxmunus.com/

3. I am jovial you take pride in what you write. It makes you stand way out from many other writers that can not push high-quality content like you. Binary Today

4. I found that site very usefull and this survey is very cirious, I ' ve never seen a blog that demand a survey for this actions, very curious... recover money lost to binary options

THANKS FOR UR GREAT COMMENT

Blogger Widgets