BinarySearchTree

节点数据结构

public class Node {

    private Node left;

    private Node right;

    private Node parent;

    private Integer value;

    /**
     * 相同value的节点将挂在该list上
     */
    private List<Integer> list = new ArrayList<Integer>();

    @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()) +
                '}';
    }
}

BinarySearchTree api

/**
 * 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<Integer> list1 = node1.getList();
        int value2 = node2.getValue();
        List<Integer> 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;
    }
}

BST的优点在于无论什么操作时间复杂度都是O(h)
类BST结构的优势在于可以在节点中存储一些信息来优化某些操作，比如
MaxMinBinarySearchTree