BINARY TREE OPERATIONS

// Precondition  Delete must be called with T  =  root
 
procedure Delete(Tree T, item x)   
   if  T  =  NULL  $\rightarrow$    return   fi
   if  x  =  root->elem  $\rightarrow$  
      place  :=  root
      if  place->right  =  NULL  $\rightarrow$   // No right subtree  
         root   :=  place->left  
      fi 
   | x $\neq$ root->elem  
      (parent, place)  :=  parent_search(T, x) 
      if parent  =  NULL $\rightarrow$    return   fi
      if  place->right  =  NULL  $\rightarrow$   // No right subtree 
         if  x  <  parent-> elem   $\rightarrow$  
            parent-> left  :=  place-> left
         | x  >  parent-> elem   $\rightarrow$  
            parent-> right  :=  place-> left
         fi 
      fi 
   fi
   next  :=  place->right
   if   next  =  NULL $\rightarrow$ 
      delete place 
   | next->left  =  NULL $\rightarrow$    // Right subtree has no left subtree 
      place->elem  :=  next->elem 
      place->right  :=  next->right 
      delete next 
   | next->left $\neq$ NULL $\rightarrow$ 
      place->elem  :=  del_min(next)
   fi 
end  Delete  

 
// Precondition T  $\neq$  NULL and T->left  $\neq$  NULL
 
function del_min(Tree T) returns item  
   do  T->left->left  $\neq$  NULL  $\rightarrow$ 
      T  :=  T->left 
   od
   val  :=  T->left->elem
   ptr  :=  T->left
   T->left  :=  T->left->right
   delete ptr
   return val 
end  del_min 
 
 




// Precondition T  $\neq$  NULL and T->elem   $\neq$   x
 
function parent_search(Tree T, item x) returns (Tree, Tree)  
   if  x  <  T->elem  and  T->left  $\neq$  NULL  $\rightarrow$ 
      if  x  =  T->left->elem  $\rightarrow$  
         return   (T, T->left) 
      | x  $\neq$  T->left->elem  $\rightarrow$  
         return   parent_search(T->left, x)
      fi 
   | x  >  T->elem  and  T->right  $\neq$  NULL  $\rightarrow$  
      if  x  =  T->right->elem  $\rightarrow$  
         return   (T, T->right) 
      | x  $\neq$  T->right->elem  $\rightarrow$  
         return   parent_search(T->right, x)
      fi 
   fi
   return  (NULL, NULL) 
end  parent_search