Friday, 1 November 2013

Search & Delete operation on Binary search tree {BST}

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
*Observation
O( log(n) ) operation for balanced tree

Deletions may unbalance tree

Example Deletion (Leaf)
Delete ( 25 )




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 :

YOU may like these

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets