BinarySearchTree

public class Node {

    private Node left;

    private Node right;

    private Node parent;

    private Integer value;

    /**
     *   value       list 
     */
    private List list = new ArrayList();

    @Override
    public String toString() {
        return "Node{" +
                (this.getLeft() == null ? "" : "left=" + this.getLeft().getValue()) +
                (this.getRight() == null ? "" : ",right=" + this.getRight().getValue()) +
                (this.getParent() == null ? "" : ",parent=" + this.getParent().getValue()) +
                ", value=" + this.getValue() +
                (this.getList().size() == 0 ? "" : ",list=" + this.getList()) +
                '}';
    }
}

/**
 * BST
 * RI(Represent Invariant):
 *   X     ，  left(X).value < X.value and right(X).value > X.value
 * @author haofan.whf
 * @version $Id: BinarySearchTree.java, v 0.1 2018 12 09    11:13 haofan.whf Exp $
 */
public class BinarySearchTree {

    /**
     *        value   Node
     * T(N) = O(h)
     * h     (    lgN，  BST     ，      (      )      )
     * @param value
     * @return
     */
    public Node query(Node root, int value){
        if(root.getValue() < value){
            if(root.getRight() != null){
                return query(root.getRight(), value);
            }else{
                return null;
            }
        }else if(root.getValue() > value){
            if(root.getLeft() != null){
                return query(root.getLeft(), value);
            }else{
                return null;
            }
        }else{
            return root;
        }
    }

    /**
     *          
     *         ,           list 
     * T(N) = O(h)     ，   query
     * @param value
     * @return
     */
    public void insert(Node root, int value){
        if(root.getValue() == null){
            root.setValue(value);
            doAfterInsert(root);
            return;
        }
        if(root.getValue() < value){
            //           
            if(root.getRight() == null){
                //     ,              
                Node n = createNode();
                n.setParent(root);
                n.setValue(value);
                root.setRight(n);
                doAfterInsert(n);
            }else{
                insert(root.getRight(), value);
            }
        }else if(root.getValue() > value){
            if(root.getLeft() == null){
                Node n = createNode();
                n.setParent(root);
                n.setValue(value);
                root.setLeft(n);
                doAfterInsert(n);
            }else{
                insert(root.getLeft(), value);
            }
        }else{
            root.getList().add(value);
        }
    }

    public Node createNode(){
        return new Node();
    }

    /**
     * @param node     Node
     */
    public void doAfterInsert(Node node){

    }

    /**
     *      (  value root   )
     * T(N) = O(h)
     * @return
     */
    public Node findSuccessor(Node root, int value){
        Node node = query(root, value);
        if(node == null){
            throw new RuntimeException("can not found node=" + node);
        }
        return findSuccessor(node);
    }

    /**
     *      (         node    , node rightSubTree     ,  rightSubTree     node.value     parent)
     * T(N) = O(h)
     * @return
     */
    public Node findSuccessor(Node node){
        if(node.getRight() != null){
            return query(node, findMin(node.getRight()));
        }else{
            int value = node.getValue();
            boolean foundSuccessor = false;
            while(node.getParent() != null){
                if(node.getParent().getValue() > value){
                    foundSuccessor = true;
                    break;
                }
                node = node.getParent();
            }
            return foundSuccessor ? node : null;
        }
    }

    /**
     *     
     *        list          
     *                 
     * T(N) = O(h)
     * @param root
     * @param value
     * @return
     */
    public void delete(Node root, int value){
        Node node = query(root, value);
        if(node == null){
            return;
        }
        int leftOrRight = leftOrRight(node);
        if(node.getRight() == null && node.getLeft() == null){
            //    ,      
            doBeforeDelete(node);
            if(leftOrRight == -1){
                node.getParent().setLeft(null);
            }else if(leftOrRight == 1){
                node.getParent().setRight(null);
            }else{
                //      ,           
                root = null;
            }
        }else if(node.getRight() == null && node.getLeft() != null){
            //     
            doBeforeDelete(node);
            node.getLeft().setParent(node.getParent());
            if(leftOrRight == -1){
                node.getParent().setLeft(node.getLeft());
            }else if(leftOrRight == 1){
                node.getParent().setRight(node.getLeft());
            }else{
                //      
                node.getLeft().setParent(null);
                root = node.getLeft();
            }
        }else if(node.getRight() != null && node.getLeft() == null){
            //     
            doBeforeDelete(node);
            node.getRight().setParent(node.getParent());
            if(leftOrRight == -1){
                node.getParent().setLeft(node.getRight());
            }else if(leftOrRight == 1){
                node.getParent().setRight(node.getRight());
            }else{
                //      
                node.getRight().setParent(null);
                root = node.getRight();
            }
        }else{
            Node successor = findSuccessor(node);
            swap(successor, node);
            //  node     successor   
            //        ,       ,       
            delete(successor, successor.getValue());
        }
    }

    /**
     * @param node       Node
     */
    public void doBeforeDelete(Node node){

    }

    /**
     *     node   (      ,         )
     * @param node1
     * @param node2
     */
    public void swap(Node node1, Node node2){
        int value1 = node1.getValue();
        List list1 = node1.getList();
        int value2 = node2.getValue();
        List list2 = node2.getList();
        node1.setValue(value2);
        node2.setValue(value1);
        node1.setList(list2);
        node2.setList(list1);
    }

    /**
     *     node  parent  /   
     * @param node
     * @return
     */
    public int leftOrRight(Node node){
        if(node.getParent() == null){
            //    
            return 0;
        }else{
            if(node.getParent().getLeft() != null
                    && node.getParent().getLeft().getValue() ==  node.getValue()){
                //   
                return -1;
            }else if(node.getParent().getRight() != null
                    && node.getParent().getRight().getValue() ==  node.getValue()){
                //   
                return 1;
            }else {
                throw new RuntimeException("impossible!");
            }
        }

    }

    /**
     *      ,         
     * T(N) = O(h)
     * @param root
     * @return
     */
    public int findMax(Node root){
        if(root.getRight() != null){
            return findMax(root.getRight());
        }else{
            return root.getValue();
        }
    }

    /**
     *      ,         
     * T(N) = O(h)
     * @param root
     * @return
     */
    public int findMin(Node root){
        if(root.getLeft() != null){
            return findMin(root.getLeft());
        }else{
            return root.getValue();
        }
    }

    /**
     *  BST                    
     * T(N) = O(N)
     *                         
     * @param root
     */
    public void checkRI(Node root){
        if(root == null){
            return;
        }
        if(root.getRight() != null){
            if(root.getValue() > root.getRight().getValue()){
                System.err.println(root);
                throw new RuntimeException("it's not a bst");
            }
        }
        if(root.getLeft() != null){
            if(root.getValue() < root.getLeft().getValue()){
                System.err.println(root);
                throw new RuntimeException("it's not a bst");
            }
        }
        checkRI(root.getRight());
        checkRI(root.getLeft());

    }

public class BSTTest {


    @Test
    public void bstNormal(){
        BinarySearchTree bst = new BinarySearchTree();
        int[] array = new int[]{3,5,6,4,2};
        Node root = new Node();

        for (int i = 0; i < array.length; i++) {
            bst.insert(root, array[i]);
        }

        bst.checkRI(root);

        Assert.assertTrue(bst.query(root, 6).getValue() == 6);
        Assert.assertTrue(bst.findMax(root) == 6);
        Assert.assertTrue(bst.findMin(root) == 2);
        Assert.assertTrue(bst.findSuccessor(root, 5).getValue() == 6);
        Assert.assertTrue(bst.findSuccessor(root, 6) == null);

        int[] insertArray = randomArray(100);
        root = new Node();
        for (int i = 0; i < insertArray.length; i++) {
            bst.insert(root, insertArray[i]);
            bst.checkRI(root);
        }

        int[] deleteArray = randomArray(50);
        for (int i = 0; i < deleteArray.length; i++) {
            bst.delete(root, deleteArray[i]);
            bst.checkRI(root);
        }
    }

    private static int[] randomArray(int size){
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size);
        }
        return array;
    }
}