import java.io.*;

class Table4 implements Table
{
// Table class, data stored in ordered trees

 Cell tree;

 public boolean delete(String key)
 {
  if(tree!=null)
     if(tree.left==null&&tree.right==null)
        {
         if(tree.item.equalKey(key))
            {
             tree=null;
             return true;
            }
         else
            return false;
        }
     else
        return delete(key,tree);
  else
     return false;
 }

 private static boolean delete(String key,Cell t)
 {
  if(t.item.lessThan(key))
     if(t.right==null)
        return false;
     else if(t.right.left==null&&t.right.right==null)
         if(t.right.item.equalKey(key))
            {
             t.right=null;
             return true;
            }
         else
            return false;
     else
        return delete(key,t.right);
  else if(!t.item.equalKey(key))
     if(t.left==null)
        return false;
     else if(t.left.left==null&&t.left.right==null)
        if(t.left.item.equalKey(key))
           {
            t.left=null;
            return true;
           }
        else
           return false;
    else
       return delete(key,t.left);
  else
     {
      if(t.left==null)
         {
          t.item=t.right.item;
          t.left=t.right.left;
          t.right=t.right.right;
         }
      else if(t.left.right==null)
         {
          t.item=t.left.item;
          t.left=t.left.left;
         }
      else
         t.item = removeRightmost(t.left);
      return true;
     }
 }

 private static KeyObject removeRightmost(Cell t)
 {
  if(t.right.right==null)
     {
      KeyObject rightmost = t.right.item;
      t.right = t.right.left;
      return rightmost;
     }
  else
     return removeRightmost(t.right);
 }

 public void add(KeyObject obj)
 {
  if(tree==null)
     tree = new Cell(obj,null,null);
  else
     add(obj,tree);
 }

 private static void add(KeyObject obj,Cell t)
 {
  if(t.item.lessThan(obj))
     if(t.right==null)
        t.right = new Cell(obj,null,null);
     else
        add(obj,t.right);
  else
     if(t.left==null)
        t.left = new Cell(obj,null,null);
     else
        add(obj,t.left);
 }

 public KeyObject retrieve(String key)
 {
  return retrieve(key,tree);
 }

 private static KeyObject retrieve(String key,Cell t)
 {
  if(t==null)
     return null;
  else if(t.item.equalKey(key))
     return t.item;
  else if(t.item.lessThan(key))
     return retrieve(key,t.right);
  else
     return retrieve(key,t.left);
 }

 public void print(PrintStream out)
 {
  print(out,tree);
 }

 private void print(PrintStream out,Cell tree)
 {
  if(tree!=null)
     {
      out.println(tree.item);
      print(out,tree.left);
      print(out,tree.right);
     }
 }

 public void orderedPrint(PrintStream out)
 {
  orderedPrint(out,tree);
 }
 
 private void orderedPrint(PrintStream out,Cell tree)
 {
  if(tree!=null)
     {
      orderedPrint(out,tree.left);
      out.println(tree.item);
      orderedPrint(out,tree.right);
     }
 }

 private static class Cell
 {
  KeyObject item;
  Cell left,right;
  
  Cell(KeyObject n,Cell l,Cell r)
  {
   item=n;
   left=l;
   right=r;
  }
 }
}