Following is code for delete() for a BST storing a generic type.
Your code will *not* use generics but will have two data fields
(key and value) which will both be of type String.

public class BST<T extends Comparable<T>>
{
   private BSTNode<T> root = null;
// stuff here
   public boolean delete(T n)
   {
      // finds and removes value n from tree
      // returns false is n is not in tree
      // This one gets ugly!
      BSTNode<T> nNode = search(n, root);  // first find the node
      if (nNode == null)                   // not in the tree
         return false;
      delete(nNode);                       // remove the node
      return true;
   }
   
   private void delete(BSTNode<T> n)
   {
      // removes a node from the tree, assumes n is not null
      if (n.getLeft() == null && (n.getRight() == null))
         // case where n is a leaf
         if (n == root)
            // n is the only node in tree
            root = null;     // empty the tree
         else    // unlink from parent
            if (n == n.getParent().getLeft())  // left child
               n.getParent().setLeft(null);    // unlink
            else // n is a right child
               n.getParent().setRight(null);   // unlink
      else  if (n.getLeft() == null)           // n has only a right child
      {
         if (n == root)   // deleting root a special case
         {
            // root pointer points to deleted node's child and link in
            n.getRight().setParent(null);
            root = n.getRight();
         }
         else             // n has a parent
         {
            // bypass n by pointing to its only child
            n.getRight().setParent(n.getParent());
            if (n == n.getParent().getLeft())         // n is a left child
               n.getParent().setLeft(n.getRight());   // bypass n
            else                                      // n is a right child
               n.getParent().setRight(n.getRight());
         }
      }
      else if (n.getRight() == null)         // n has only a left child
      {
         if (n == root)                      // deleting root a special case
         {
            // root pointer points to deleted node's child and link in
            n.getLeft().setParent(null);
            root = n.getLeft();
         }
         else   // n has a parent
         {
            // bypass n by pointing to its only child
            n.getLeft().setParent(n.getParent());
            if (n == n.getParent().getLeft())          // n is a left child
               n.getParent().setLeft(n.getLeft());     // bypass n
            else                                       // n is a right child
               n.getParent().setRight(n.getLeft());
         }
      }
      else     // n has two children, replace value at n with the largest
               // value in its left subtree tnen delete the redundant node
      {
         // find highest preceding value: once left then farthest right
         BSTNode<T> pred = n.getLeft();
         while (pred.getRight() != null)
            pred = pred.getRight();
         // move value from prev to n and remove prev
         n.setData(pred.getData());
         delete(pred);
      }
   }
// more stuff here   
}