interface TreeVisitor {
    Object visitEmpty();
    Object visitBuild(Object data, 
		     Tree left, 
		     Tree right);
}

interface TreeVisitorI {
    Object visitEmpty(Empty it);
    Object visitBuild(Build it,Object data, 
		     Tree left, 
		     Tree right);
}

class RemoveVisitor implements TreeVisitorI {
    Comparable x;
    RemoveVisitor(Comparable x) {this.x = x;}

    public Object visitEmpty(Empty it){
	return it;
    }

    public Object visitBuild(Build it, Object data, Tree left, Tree right) {
	int cmp = x.compareTo(data);
	if (cmp < 0) {
	    it.setLeft((Tree)left.accept(this));
	    return it;
	} else if (cmp > 0) {
	    it.setRight((Tree)right.accept(this));
	    return it;
	} else /* cmp == 0 */ if (left instanceof Empty) {
	    return right;
	} else if (right instanceof Empty) {
	    return left;
	} else {
	    RemoveMaxVisitor v = new RemoveMaxVisitor();
	    Tree left1 = (Tree)left.accept(v);
	    it.setLeft((Tree)left.accept(v));
	    it.setData(v.getResult());
	    return it;
	}
    }
}

class RemoveMaxVisitor implements TreeVisitorI {
    Comparable themax;
    
    RemoveMaxVisitor() {themax=null;}

    public Object getResult() {return themax;}

    public Object visitEmpty(Empty it){
	return it;
    }

    public Object visitBuild(Build it, Object data, Tree left, Tree right) {
	if (right instanceof Empty)
	    {
		themax = (Comparable)data;
		return left;
	    }
	else {
	    it.setRight((Tree)right.accept(this));
	    return it;
	}
    }
}


class InsertVisitor implements TreeVisitor {
    Comparable x;
    InsertVisitor(Comparable x) {this.x = x;}

    public Object visitEmpty(){
	return new Build(x, new Empty(), new Empty());
    }

    public Object visitBuild(Object data, Tree left, Tree right) {
	int cmp = x.compareTo(data);
	if (cmp == 0)
	    return new Build(x, left, right);
	else if (cmp < 0)
	    return new Build(data,(Tree)left.accept(this),right);
	else 
	    return new Build(data,left,(Tree)right.accept(this));
    }
}


class InsertVisitorI implements TreeVisitorI {
    Comparable x;
    InsertVisitorI(Comparable x) {this.x = x;}

    public Object visitEmpty(Empty it){
	return new Build(x, new Empty(), new Empty());
    }

    public Object visitBuild(Build it, Object data, Tree left, Tree right) {
	int cmp = x.compareTo(data);
	if (cmp == 0)
	    {it.setData(x);}
	else if (cmp < 0)
	    it.setLeft((Tree)left.accept(this));
	else 
	    it.setRight((Tree)right.accept(this));
	return it;
    }
}

class FindVisitor implements TreeVisitor {
    Comparable x;

    FindVisitor(Comparable x) {this.x = x;}

    public Object visitEmpty() {
	return Boolean.FALSE;
    }

    public Object visitBuild(Object data, Tree left, Tree right) {
	int cmp = x.compareTo(data);
	if (cmp == 0)
	    return Boolean.TRUE;
	else if (cmp < 0)
	    return (Boolean)left.accept(this);
	else 
	    return (Boolean)right.accept(this);
    }
}


class ToStringVisitor implements TreeVisitor {
    
    public Object visitEmpty() {
	return "L()";
    }

    public Object visitBuild(Object data, Tree left, Tree right) {
	return "N(" + data + ", " + 
	    (String)left.accept(this) + ", " +
	    (String)right.accept(this) + ")";
    }
}

abstract class Tree {
    public abstract Boolean enthaltenBST1(Comparable x);
    public Boolean enthaltenBST2(Comparable x) {
	if (this instanceof Empty) 
	    return Boolean.FALSE;
	else /* this instanceof Build */ {
	    Build node = (Build)this;
	    int cmp = x.compareTo(node.data);
	    if (cmp == 0) return Boolean.TRUE;
	    else if (cmp < 0) return node.left.enthaltenBST2(x);
	    else return node.right.enthaltenBST2(x);
	}
    }
    public String toString() {
	return (String)accept(new ToStringVisitor());
    }
    
    public static void main(String[] args) {
	Tree t = new Build("C", new Build("B", new Empty(), new Empty()), 
			  new Build("E", new Build("D", new Empty(), new Empty()),
				   new Empty()));
	System.out.println(t);
	Tree t1 = (Tree)t.accept(new InsertVisitorI("G"));
	System.out.println(t1);
	System.out.println(t1.accept(new RemoveVisitor("E")));
    }
    
    public abstract Object accept(TreeVisitor v);
    public abstract Object accept(TreeVisitorI v);
}

class Empty extends Tree {

    Empty() {};

    public Object accept(TreeVisitor v) {
	return v.visitEmpty();
    }
    public Object accept(TreeVisitorI v) {
	return v.visitEmpty(this);
    }
    public Boolean enthaltenBST1(Comparable x) {
	return Boolean.FALSE;
    }
}

class Build extends Tree {

    Object data;
    Tree left;
    Tree right;

    Build(Object data, Tree left, Tree right){
	this.data = data;this.left = left;this.right=right;
    }

    public Boolean enthaltenBST1(Comparable x) {
	int cmp = x.compareTo(data);
	if (cmp == 0) return Boolean.TRUE;
	else if (cmp < 0) return left.enthaltenBST1(x);
	else return right.enthaltenBST1(x);
	
    }
    
    public Object accept(TreeVisitor v) {
	return v.visitBuild(data, left, right);
    }
    public Object accept(TreeVisitorI v) {
	return v.visitBuild(this, data, left, right);
    }
    public void setData(Object data) {
	this.data=data;
    }
    public void setLeft(Tree left) {this.left = left;}
    public void setRight(Tree right) {this.right = right;}
}


class AVL_Entry implements Comparable {
    Comparable data;
    int bf;
    public int compareTo(Object x) {
        return data.compareTo(x);
    } 
}


class MapEntry implements Comparable {
    Comparable key;
    Object value;
    public int compareTo(Object x) {
	return key.compareTo(((MapEntry)x).key);
    }
}