[Data Structure]Map Implementation using BST

http://www.sanfoundry.com/java-program-implement-hash-tables-chaining-binary-trees/
1. Map
Map<K,V>
store key and value pair
key datatype is K
value datatype is V

2. BST
2.1 each node has at most two children
2.2 the value of the nodes on the left subtree is less than
2.3 the value of the nodes on the right subtree is greater than
each node stores a key and associate with a value
keys are fully ordered
3. Implementation
Map
variable: key,data, node[pair], node's left and right child
method: get(key), set(key,value)
get and set do binary search, when a key showed up we compare it with the root.
If less go left, it greater go right until we find the target

// the node class - clients will not interact with directly
public class BSTNode {

     public K key;
     public V value;
     public BSTNode left ,right; // children
     BSTNode(K k, V v){ // constructor
         key = k;
         value  =v;
     }

     // Lookup:
     public V lookup(K key, Comparator keycomp){
         // COMPARE from the root(this.key)
         int cmp = keycomp.compare(key, this.key);
         if ( cmp == 0 ){//equal, k == n.key
             return value;
         } else if ( cmp < 0 && left != null ) {// less than, k < n.key
             return left.lookup(key,keycomp);
         } else if ( cmp > 0 && right != null ) {//greater than, k > n.key
             return right.loopup(key, keycomp);
         } else
             return null; // key not present in tree

     }

     // Insert: 
     public V insert(K key, V value, Comparator keycomp){
         int cmp = keycomp.compare(key,this.key);
         if ( cmp == 0) {
             V old = this.value;
             this.value = value;
             return old;
         //} else if ( cmp < 0 && left != null ){
         } 
         else if ( cmp < 0) {
             if (left == null) 
             {
                left = new BSTNode (key,value);
                return null ;// old value
             } 
             else
             {
                return left.insert(key,value,keycomp);
             }       
         }   
         //} else if ( cmp > 0 && right != null  ) {
         else if ( cmp >0){
             if ( right == null)
             {
                 right = new BSTNode(key,value);
                 return null;// old value
             }
             else 
             {
                return right.insert(key, value, keycomp);
             }
         } 
         //else {
         //
         //} 
             
     }

     // Remove:
     public V remove(K key, Comparator keycomp){
        int cmp = keycomp.compare(key, this.key);
        if ( cmp == 0) {
             
        //} else if ( cmp < 0 && left != null ) {
        else if (  cmp < 0 ){
             
             // left.loopup(key, left.key);
        }
        //} else if ( cmp > 0 && right != null ) {
        else if ( cmp > 0 ){   
             
             // right.lookup(key, right.key);
        } else {


        }
     }

     // FindMinNode:


     // RemoveMinNode:


}
public class BST {

     private BSTNode root;
     private Comparator keyComp;

     public BST(Comparator keycomp){
            this.root = null; //empty tree
            this.keycomp = keycomp;
     }

     // Get: look up value associated with given key 
     // @parameter: K key
     // @return : V vlaue
     public V get(K key){
           // Tree is Empty
          if (root == null)
            return null;
          else
          {
              return root.lookup(key,keycomp);
          }
     }


     // Put: add or replace key, value pair
     // @return V previous value
     public V put(K key, V value){
          // Tree is Empty
          if (root ==null)
          {
              root = new BSTNode(key, value);
              return null; //NOTE: Previous value
          }
          else 
              return root.insert(key, value, keycomp);
     }


     // Remove: remove key (and its associated value)
     // @returns the value associated with the deleted key, or null if no such key exist
     public V remove(K key){
           // Tree is Empty
           if (root == null)
                  return null
           else
           {
                  V old = root.lookup(key, keycomp);
                  // No such node exist
                  if (old == null)
                        return null;
                  else
                  {
                        root = root.remove(key, keycomp);
                        return old;
                  }
             
           }    
     }
}