CMPT 225: Binary Search Trees

A Binary Search Tree (BST) is a binary tree T with nodes labelled 
by keys from some ordered set, and which satisfies the following 
BST Ordering Invariant:
For any two nodes u and v of T, 
 
 If u is in the left sub-tree of v, then key(u) <= key(v);
 If u is in the right sub-tree of v, then key(u) > key(v).




Search(t){
   // Returns true iff target key t occurs in T
   // root denotes the root of T
   return Search(root,t)
}

Search(v,t){
   // Returns true iff target key t occurs in the sub-tree rooted at v
   if( t = key(v) ){
      return true
   }else if( t < key(v) AND left(v) exists ){
      return Search( left(v), t )
   }else if( t > key(v) AND right(v) exists ){
      return Search( right(v), t)
   }else{
      return false 
   }
}


Insert(k){
  Insert(root,k)
}

Insert(v,k){
   // Inserts key k into the sub-tree rooted at v.

   if( k <= key(v) ){
      if( left(v) exists ){
         Insert( left(v), k )
      }else{
         make a new node u with key(u) = k
         install u as left(v)
      }
   }else{
      if( right(v) exists ){
         Insert( right(v), k )
      }else{
         make a new node u with key(u) = k
         install u as right(v)
      }
   }
}


Remove(k){
   // Remove key k from T

   Execute Search(k)
   v = the node with key(v) = k

   if( v is a leaf ){ // Case 1
      delete v
   }else if ( v has one child c ){ // Case 2
      replace v with the sub-tree rooted at c
   }else{ // Case 3 - v has two children
      u = pred(v) // the last node in-order traversal visits before v

      if( u is a leaf ){ // Case 3a
         replace v with u
      }else{ // Case 3b 
         set key(v) = key(u) // replace the k with its predecessor
         w = left(u) 
         replace u with the sub-tree rooted at w
      }
   }

pred(v){// Iterative 
  // return the predecessor of v
  // we assume that v has a left child
  u = left(v)
  while( u has a right child ){
     u = right(u)
  }
  return u
}  
   
pred(v){// Recursive
  // return the predecessor of v
  // we assume that v has a left child
  return right-most(left(v))
}

right-most(u){
  if( u has a right child ){
     return right-most(right(u))
  }else{
     return u 
  }
}