// binary search tree 

class AltBST implements SearchStructure {
    private BinaryNode t;
    private BinaryNode finger;   // a cursor into the data structure
    private BinaryNode previous; // previous is one step behind finger
    private int size;
    
    public AltBST() {
	t = null;
	size = 0;
    }
    
    public String toString() {
	return "Tree has " + size + " elements:" + t;
    }
    
    public int size() {
	return size;
    }
    
    public boolean search (Object o){ 
	finger = t;
	previous = null;
	return mySearch(o,t);
    }
    
    // helper method
    private boolean mySearch(Object o, BinaryNode t) {
	if (t == null) return false;
	// non-null tree
	int test = ((Comparable)t.getItem()).compareTo(o);
	if (test == 0) return true;
	// need to explore one of the subtrees
	// set up the cursors correctly
	previous = t;
	if (test < 0)
	    // explore right subtree
	    finger = t.getRight();
	else 
	    // explore left subtree
	    finger = t.getLeft();
	return mySearch(o,finger);
    }
    
    public void insert (Object o)  {
	if (t == null){ // empty tree
	    t = new BinaryNode(o);
	    size = size + 1;
	    return;
	}
	// non-empty tree:look for object first, setting up cursors
	boolean found = search(o);
	if (! found) {//previous points to last BinaryNode on path from root
	    // put o into a child of previous
	    int test = ((Comparable)previous.getItem()).compareTo(o);
	    if (test < 0)
		previous.setRight(new BinaryNode(o));
	    else  
		previous.setLeft(new BinaryNode(o));
	    size = size + 1;
	}
    }
    
    // returns maximum value in tree rooted at parameter t
    // if the maximum value is at root of t, t is not changed
    // otherwise, the maximum value is spliced out of the subtree rooted at t
    public Comparable extractMax(BinaryNode t) {
	if (t == null) return null;
	// set up cursors
	finger = t;
	previous = null;
	Comparable maxVal = myExtractMax(t);
	return maxVal;
    }
    
    //h elper method
    private Comparable myExtractMax(BinaryNode t){
	// assume t is non-null
	if (t.getRight() == null) {
	    // t is rightmost node
	    // splice out t
	    if (previous != null) 
		previous.setRight(finger.getLeft());
	    return (Comparable) (t.getItem());
	}
	else {
	    previous = finger;
	    finger = t.getRight();
	    return myExtractMax(finger);
	}
    }
    
    public void delete(Object o) {
	boolean found = search(o);
	if (! found) return;
	// check if left subtree of finger cell is null
	size = size - 1;
	if (finger.getLeft() == null) 
	    // if so, easy to short out finger cell
	    if (previous == null)
		// deleting root node of tree 
		t = finger.getRight(); 
	    else {
		// deleting some internal node of tree
		if (previous.getLeft() == finger)
		    // finger is to the left of previous
		    previous.setLeft(finger.getRight());
		else
		    // finger is to the right of previous
		    previous.setRight(finger.getRight());
	    }
	else {
	    // there is a non-trivial subtree to left of updatedCell
	    BinaryNode updatedCell = finger; // delete from this cell
	    BinaryNode leftSubtree = finger.getLeft();
	    if (leftSubtree.getRight() == null) { // root of leftSubtree has max
		// splice out root of leftSubtree
		finger.setItem(leftSubtree.getItem());
		finger.setLeft(leftSubtree.getLeft());
		return;
	    }
	    else {
		Comparable maxValue = extractMax(leftSubtree); 
		updatedCell.setItem(maxValue);
	    }
	}
    }
}

public class TestAltBST {
    
    public static void main(String[] args) {
	AltBST t = new AltBST();
	t.insert("Hillary");
	t.insert("Bill");
	t.insert("Monica");
	t.insert("Gennifer");
	t.insert("Ingrid");
	System.out.println(t);
	System.out.println(t.search("Bill"));
	System.out.println(t.search("Gennifer"));
	System.out.println(t.search("Monica"));
	t.delete("Hillary");
	System.out.println(t);
	System.out.println(t.search("Hillary"));
	t.delete("Bill");
	System.out.println(t);
	t.delete("Ingrid");
	System.out.println(t);
	t.delete("Monica");
	System.out.println(t);
	t.delete("Gennifer");
	System.out.println(t);
    }
}