/**
 * Unbalanced search tree implementation.
 * 
 * @author Gerth Stølting Brodal
 */

public class SearchTree<Element extends Comparable>
{
    /**
     * The root of the binary search tree; null if empty search treeJ
     */
    private Node<Element> root;

    /**
     * Constructor creating an empty binary tree
     */    
    public SearchTree() {
        root = null;
    };

    /**
     * Return if the red black is empty
     */    
    public boolean isEmpty() {
        return root == null;
    };

    /**
     * Simple pretty print of a binary tree
     */
    private void print() {
        System.out.println("Search tree:");
        print_subtree(root, 0);        
    }
        
    /** 
     * Recursive pretty print subtree rooted at x with indentation
     */
    private void print_subtree(Node<Element> x, int indent) {
        if (x != null) {
            print_subtree(x.getRight(), indent + 1);
            for (int i=0; i < indent; i++) System.out.print("   "); 
            System.out.println(x.getElement());
            print_subtree(x.getLeft(), indent + 1);
        }
    };
    
    /**
     * Print inorder traversal of subtree rooted at x
     */
    private void inorderTreeWalk(Node<Element> x) {
        if (x != null) {
            inorderTreeWalk(x.getLeft());
            System.out.print(x.getElement() + " ");
            inorderTreeWalk(x.getRight());
        }
    };
    
    /**
     * Print preorder traversal of subtree rooted at x
     */
    private void preorderTreeWalk(Node<Element> x) {
        if (x != null) {
            System.out.print(x.getElement() + " ");
            preorderTreeWalk(x.getLeft());
            preorderTreeWalk(x.getRight());
        }
    };

    /**
     * Print postorder traversal of subtree rooted at x
     */
    private void postorderTreeWalk(Node<Element> x) {
        if (x != null) {
            postorderTreeWalk(x.getLeft());
            postorderTreeWalk(x.getRight());
            System.out.print(x.getElement() + " ");
        }
    };

    /**
     * Find and return element in search tree equal to k, otherwise null is returned
     */
    public Element search(Element k) {
        // Node<Element> x = recursiveTreeSearch(root, k);
        Node<Element> x = iterativeTreeSearch(root, k);
        if (x == null) return null;
        return x.getElement();        
    }
    
    /**
     * Find node in subtree rooted at x with element equal to k, otherwise null is returned
     */
    private Node<Element> recursiveTreeSearch(Node<Element> x, Element k) {
        if (x == null || x.getElement().compareTo(k) == 0) 
            return x;
        if (x.getElement().compareTo(k) > 0)
            return recursiveTreeSearch(x.getLeft(), k);
        return recursiveTreeSearch(x.getRight(), k);
    }
    
    /**
     * Find node in subtree rooted at x with element equal to k, otherwise null is returned
     */
    private Node<Element> iterativeTreeSearch(Node<Element> x, Element k) {
        while (x != null && x.getElement().compareTo(k) != 0) 
            if (x.getElement().compareTo(k) > 0)
                x = x.getLeft();
            else 
                x = x.getRight();
        return x;
    }

    /**
     * Find minimum element in search tree, returns null if empty search tree
     */
    public Element minimum() {
        if (root == null) return null;
        return treeMinimum(root).getElement();
    }
        
    /**
     * Find node with minimum element in non-empty subtree rooted at node x
     */
    private Node<Element> treeMinimum(Node<Element> x) {
        while (x.getLeft() != null)
            x = x.getLeft();
        return x;       
    }
    
    /**
     * Find maximum element in search tree, returns null if empty search tree
     */
    public Element maximum() {
        if (root == null) return null;
        return treeMaximum(root).getElement();
    }
     
    /**
     * Find node with maximum element in non-empty subtree rooted at node x
     */
    private Node<Element> treeMaximum(Node<Element> x) {
        while (x.getRight() != null)
            x = x.getRight();
        return x;       
    }
    
    /**
     * Return successor node to node x; 
     * returns null if x is node with maximum element in search tree
     */    
    private Node<Element> treeSuccessor(Node<Element> x) {
        if (x.getRight() != null)
            return treeMinimum(x.getRight());
        Node<Element> y = x.getParent();
        while (y != null && x == y.getRight()) {
            x = y;
            y = y.getParent();
        }
        return y;
    }
   
    /**
     * Compute depth of seach tree
     */    
    public int depth() {
        return depth(root);
    };
    
    /**
     * Compute depth of subtree rooted at node x
     */    
    private int depth(Node<Element> x) {
        if (x == null) {
            return 0;
        }
        return 1 + Math.max(depth(x.getLeft()), depth(x.getRight()));
    };
    
    /**
     * Insert element e into search tree 
     * (always creates a new node, also if e is already in the tree)
     */    
    public void insert(Element k) {
        Node<Element> x = new Node<Element>(k);
        if (root == null) {
            root = x;
        } else {
            Node<Element> v = root;  // v is current node during top-down search
            while (true) {
                if (v.getElement().compareTo(k) < 0) {
                    if (v.getRight() != null) {
                        v = v.getRight();
                    } else {
                        v.setRight(x);
                        return;
                    }
                } else {
                    if (v.getLeft() != null) {
                        v = v.getLeft();
                    } else {
                        v.setLeft(x);
                        return;
                    }
                } 
            }
        }
    };

    /**
     * Delete one node with element k from search tree
     * (does not change the search tree, if k is not in the search tree)
     */
    public void delete(Element k) {
        if (root != null) {
            Node<Element> z = iterativeTreeSearch(root, k);
            if (z != null) {
                if (z.getRight() == null) { // only left child
                    Node<Element> y = z.getLeft();
                    z.setLeft(null);
                    if (z == root) { // z is root
                        root = y;
                    } else {
                        Node <Element> p = z.getParent();
                        if (p.getLeft() == z) // z is left child of p
                            p.setLeft(y);
                        else // z is right child of p
                            p.setRight(y);                        
                    }
                } else { // z has right child
                    Node<Element> y = treeMinimum(z.getRight());
                    if (y.getParent() != z)
                        y.getParent().setLeft(y.getRight());
                    else
                        z.setRight(y.getRight());
                    z.setElement(y.getElement());
                }
            }
        }
    }

    /**
     * Validate if the search tree is valid
     *   (1) left and right children point to the correct parent,
     *   (2) search tree keys appear in inorder
     */
    public void validate() {
        if (root != null) {
            assert root.getParent() == null;
            validate_references(root);
        }
        validate_inorder(root, null);
    }
    
    /**
     * Traverse subtree rooted at node x and verify all pointers have are set properly
     */
    private void validate_references(Node<Element> x) {
        // System.out.println("validating references " + x.getElement());
        if (x == null) return;
        Node<Element> left = x.getLeft();
        Node<Element> right = x.getRight();
        if (left != null) {
            assert left != x;
            assert left.getParent() == x;
            validate_references(left);
        }
        if (right != null) {
            assert right != x;
            assert right.getParent() == x;
            validate_references(right);
        }     
    }
    
    /**
     * Validate search tree satisfies inorder; returns last key verified
     */
    private Element validate_inorder(Node<Element> x, Element last) {
        if (x == null) return last;
        last = validate_inorder(x.getLeft(), last);
        Element e = x.getElement();
        // System.out.println("Validating inorder " + e);
        assert e != null;
        assert last == null || e.compareTo(last) >= 0;
        return validate_inorder(x.getRight(), e);
    }
    
    /**
     * Test all the methods of the class
     */
    public static void test() {
        SearchTree<Integer> T = new SearchTree<Integer>();
        for (int i=0; i<10; i++) 
            T.insert((int)(1 + Math.random() * 100));
        T.print();
        
        System.out.print("Inorder tree walk: ");
        T.inorderTreeWalk(T.root);
        System.out.println();
        
        System.out.print("Preorder tree walk: ");
        T.preorderTreeWalk(T.root);
        System.out.println();
        
        System.out.print("Postorder tree walk: ");
        T.postorderTreeWalk(T.root);
        System.out.println();
        
        System.out.println("Depth = " + T.depth());
        for (int k=40; k<50; k++)
            System.out.println("Search(" + k + "): " + T.search(k));
        
        System.out.println("Minimum: " + T.minimum());
        System.out.println("Maximum: " + T.maximum());
        System.out.println("3rd smallest: " + T.treeSuccessor(T.treeSuccessor(T.treeMinimum(T.root))).getElement());
        
        Integer d = T.root.getElement();
        System.out.println("Deleting root element " + d);
        T.delete(d);
        T.print();
        
        System.out.println("Sorting random numbers: ");
        T = new SearchTree<Integer>();
        for (int i=0; i<100; i++) {
            T.insert((int)(1 + Math.random() * 1000));
            T.validate();
        }
        while (! T.isEmpty()) {
            Integer k = T.minimum();
            T.delete(k);
            System.out.print(k + " ");
            T.validate();
        }
        System.out.println();

        System.out.print("Stress test...");
        for (int i=0; i<10000; i++) {
            T.insert((int)(1 + Math.random() * 1000));
            T.validate();
        }
        while (! T.isEmpty()) {
            T.delete((int)(1 + Math.random() * 1000));
            T.validate();
        }
        System.out.println("done");
    }
}