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).


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

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

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

insert(k,v){
   // Inserts key k into the sub-tree rooted at v.
   // This version does not assume that k is new.
   if( k < key(v) ){
      if( left(v) exists ){
         insert( k, left(v) )
      }else{
         make a new node u with key(u) = k
         install u as left(v)
      }
   }else if( k > key(v){
      if( right(v) exists ){
         insert( k, right(v) )
      }else{
         make a new node u with key(u) = k
         install u as right(v)
      }
   }else if(k == key(v)){
      // do nothing if we are implementing a set ADT;
      // if we are storing a multi-set, increment the multiplicity for k.
   }
}

insert(v,k){
   // Alternate insert, which assumes key k is not already in the tree.
   find(k,root)
   let v be the leaf where the find(k,root) search terminated.
   if( k < key(v) ){
      make a new node u with key(u) = k
      install u as left(v)
   }else{
      make a new node u with key(u) = k
      install u as right(v)
   }
}

Remove(k){
   // Remove key k from T
   // Assumes that k is in fact in T
   find(k,root)
   let v be the node with key(v) = k, found by the find(k,root) search
   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 = succ(v) // find the first node an in-order traversal of T visits after v
      set key(v) = key(u) // replace the key k with its predecessor
      if( u is a leaf ){
         delete node u
      }else{ // u is not a leaf
         replace u with it's right sub-tree 
      }
   }
}

succ(v){// Iterative 
  // return the successor of node v
  // i.e., the node that an in-order traversal would visit immediately after visiting v
  // we assume that v has a right child
  u = right(v)
  while( u has a left child ){
     u = left(u)
  }
  return u
}  
   
succ(v){// Recursive
  // return the successor of v
  // we assume that v has a right child
  return left-most(right(v))
}

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