/*
 * Burton Rosenberg
 * June 2004
 */

class Tree {

    Node root = null ;
    boolean interpretIntegers = true ;

    class Node {
       Node lc ;
       Node rc ;
       Key key ;
       int count ;
       int rep ;

       Node() { }
       Node(Key key) { this.key = key ; }
    }

    class NodePair {
       Node node ;
       Node parent ;

       NodePair( Node parent, Node node ) {
          this.parent = parent ;
          this.node = node ;
       }
    }

    Node getRoot() { 
       return root ; }

    void clear() { 
       root = null ; } 

    void insert(int key_i) {
       insert( new Key(key_i) ) ;
    }

    void insert(String key_s) {
       insert( new Key(key_s) ) ;
    }

    void insert(Key key) {

      if (root==null) {
         root = new Node(key) ;
         return ;
      }
      // root != null
      Node n = root ;
      Node pn = null ; // pn means previous-n
      while ( n!=null ) {
         pn = n ;
         int cr = key.compareTo(n.key, interpretIntegers) ;
         if ( cr==0 ) {
            n.rep++ ;
            return ;
         }
         if ( cr<0 ) n = n.lc ;
         else n = n.rc ;
      }
      Node nn = new Node(key) ; // nn means new-n
      if ( key.compareTo(pn.key, interpretIntegers)<0 ) pn.lc = nn ;
      else pn.rc = nn ;
    }

    int computeCount() {
        return computeCountAux(root) ;
    }

    int computeCountAux(Node n) {
       if ( n==null ) return 0 ;
       int cl = computeCountAux( n.lc ) ;
       int cr = computeCountAux( n.rc ) ;
       n.count = cl + cr + 1 ;
       return n.count ;
    }

    NodePair find( NodePair np, Key key ) {

    // ASSERT: np.parent is parent of np.node
    // Returns: if node with key found, a reference
    //          to np is returned, and np is updated:
    //          np.node is the node found and np.parent
    //          is its parent.
    //          if node not found, return null.
    // Note: we begin search with np.node, not np.parent!

       while ( np.node!=null ) {
          int c =  key.compareTo( np.node.key, interpretIntegers ) ;
          if ( c==0 ) return np ;
          np.parent = np.node ;
          if ( c<0 ) {
             np.node = np.node.lc ;
          }
          else {
             np.node = np.node.rc ;
          }
       }
       if ( np.node==null ) return null ;
       return np ;
    }

    NodePair walkLeftThenRightmost(NodePair np) {
       np.parent = np.node ;
       np.node = np.node.lc ;
       while ( np.node.rc!=null ) {
          np.parent = np.node ;
          np.node = np.node.rc ;
       }
       return np ;
    }
    
    void delete( int key_i ) {
       delete( new Key(key_i) ) ;
    }

    void delete( String key_s ) {
       delete( new Key(key_s) ) ;
    }

    void delete( Key key ) {
       if ( key.key_s.length()==0 ) return ;
       if ( root==null ) return ;
   
       // make dummy node, to unify code for case delete root
       Node dummy = new Node() ;
       dummy.lc = root ;
       NodePair np = new NodePair( dummy, root ) ;

       np = find( np, key ) ;
       if ( np==null ) return ; // node not found
       do {
         boolean isLeftChild = (np.parent.lc==np.node) ;
         Node onlyChild = isOnlyChild(np.node) ;
         if ( onlyChild==null && np.node.lc!=null ) {
            // CASE: two children
            Node nt = np.node ;
            np = walkLeftThenRightmost(np) ;
            // swap
            nt.key = np.node.key ;
            nt.rep = np.node.rep ;
            // and delete np by running this code again
            continue ;
         }
         else {
            // CASE: zero children or one child
            // one or zero children. if one child, onlyChild is that child
            if ( isLeftChild ) np.parent.lc = onlyChild ;
            else np.parent.rc = onlyChild ;
         }
         break ;
       } while (true) ;
       root = dummy.lc ;
    }

    Node isOnlyChild(Node n) {
       if ( n.rc==null ) return n.lc ;
       if ( n.lc==null ) return n.rc ;
       return null ;
    }
       
    void printSimple() {
       printSimpleAux(root,0) ;
    }

    void printSimpleAux(Node n, int d ) {
        if ( n==null ) return ;
        for ( int i=0; i<d; i++ ) System.out.print("  ") ;
        System.out.println(n.key.key_s) ;
        printSimpleAux( n.lc, d+1 ) ;
        printSimpleAux( n.rc, d+1 ) ;
    }

}