二叉查找树与AVL树

/**
 * 创建一棵二叉查找树
 *
 * @date 2021/10/23
 **/
public class BinarySearchTree<AnyType> {

    private BinaryNode<AnyType> root;
    // 比较器
    private Comparator cmp;

    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 带比较器的构造方法
     *
     * @param c 构造器传入的比较器
     */
    public BinarySearchTree(Comparator<? super AnyType> c) {
        root = null;
        cmp = c;
    }

    // 进行比较
    private int myCompare(AnyType lhs, AnyType rhs) {
        if (cmp != null) {
            // 如果传入了比较器，则使用传入的比较器进行比较
            return cmp.compare(lhs, rhs);
        } else {
            // 如果没用，则强制转为Compareable, 如果报错，说明不可转，则也应该直接抛出异常
            return ((Comparable) lhs).compareTo(rhs);
        }
    }

    public void makeEmpty() {
        this.root = null;
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    public boolean contains(AnyType x) {
        return contains(x, root);
    }

    public AnyType findMax() {
        if (isEmpty()) {
            throw new BufferUnderflowException();
        } else {
            return findMax(root).element;
        }
    }

    public AnyType findMin() {
        if (isEmpty()) {
            throw new BufferUnderflowException();
        } else {
            return findMin(root).element;
        }
    }

    public void insert(AnyType x) {
        root = insert(x, root);
    }

    public void remove(AnyType x) {
        root = remove(x, root);
    }

    public void printTree() {
        // todo
    }

    /**
     * 递归判断树中是否包含项为x节点
     *
     * @param x 需要查找的数据x
     * @param t 二叉查找树的根节点
     * @return 如果树存在元素x返回true，否则返回false
     */
    public boolean contains(AnyType x, BinaryNode<AnyType> t) {
        // 如果节点为null，终止递归，该递归是尾递归(可以使用尾递归的原因是该递归很明显栈深为O(logN))
        if (t == null) {
            return false;
        }
        // 查找的元素与根节点比较
        int compareResult = myCompare(x, t.element);
        // 如果x比根节点小，则继续找左子树
        if (compareResult < 0) {
            return contains(x, t.left);
        } else if (compareResult > 0) {
            // 如果x比根节点大，则继续找右子树
            return contains(x, t.right);
        } else {
            // x等于根节点，返回true，跳出递归
            return true;
        }
    }

    // 递归查询二叉查找树的最小的元素
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            // 尾递归的出口，最深的左子节点即为最小元素，尾递归可以改为如下while循环
            return t;
        }
        return findMin(t.left);
    }

    // 非递归查询二叉查找树的最大的元素
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }

    /**
     * 将元素插入二叉查找树 （注意，该二叉查找树不是平衡的，该例都是插入到叶子结点后(不需要平衡)），建议手画理解
     *
     * @param x 要插入的元素x
     * @param t 该二叉查找树的根节点，用来确定是哪一棵树
     * @return t：插入的二叉树的根节点
     */
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        // 递归出栈条件：如果递归结果的根节点为null，则说明可以此处插入
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }
        int compareResult = myCompare(x, t.element);
        if (compareResult < 0) {
            // 此处说明递归：如果x比root小，则root.left 作为新的root进行递归调用，记作rootL，进入递归后，如果为null
            // 则说明此处为插入点，返回一个new BinaryNode(出栈条件)，跳出底层递归，此时t.left进行接收，从而实现插入
            // 注意此处的左侧的t.left的t，是由insert递归传入的，可以是上面说的rootL，t.left实际上确定了。t的left指针指向哪一个节点
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else {
            // 如果要插入的元素与二叉查找树的某个元素相同(可以将相同的元素保留在另一个结果当中)

        }
        // 此处的情况是，当t != null才能走到这里，每一层递归，返回的是root,用于上述的t.left或t.right
        // 递归到最后返回到第一次的时候，则为初始传入的t的根节点
        return t;
    }

    /**
     * 从二叉查找树中删除元素x(注意：该二叉查找树不是平衡的，对于删除的节点只有一个，则直接移动这唯一的一个节点上去)
     * 对于有两个子节点的，该例x节点删除后，移动上去的都是x节点的右子树的最小的节点(该节点不可能有左子树))，然后递归的删除移动上去的节点
     *
     * @param x 要删除的节点x
     * @param t 二叉查找树的根节点
     * @return t 二叉查找树的根节点
     */
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return t;
        }
        int compareResult = myCompare(x, t.element);
        if (compareResult < 0) {
            t.left = remove(x, t.left);
        } else if (compareResult > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            // 找到了要删除的元素，要删除的元素有两个子节点
            // 找到该节点作为root的子树的最小的节点的值，赋给该节点(用最小的元素替换删除的节点)
            t.element = findMin(t.right).element;
            // 该节点的右子树也要删除刚刚最小的元素(刚刚替换上去的元素)
            t.right = remove(t.element, t.right);
        } else {
            // 只有一个子节点或没有子节点的情况，直接将子节点移动到删除的节点上去(两个子节点为null则为null)
            t = t.left != null ? t.left : t.right;
        }
        // 递归最终会返回传入的根节点
        return t;
    }

    private static class BinaryNode<AnyType> {

        public AnyType element;
        public BinaryNode<AnyType> left;
        public BinaryNode<AnyType> right;

        /**
         * 构造一个节点，同时知名左子节点与右子节点
         *
         * @param element 当前节点存储的元素
         * @param left    左子节点
         * @param right   右子节点
         */
        public BinaryNode(AnyType element, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

        /**
         * 构造一个只有节点，无左子节点的，无右子节点的数据
         *
         * @param element 当前节点存储的数据
         */
        public BinaryNode(AnyType element) {
            this.element = element;
            this.left = null;
            this.right = null;
        }
    }
}

public class AvlTree<AnyType extends Comparable<AnyType>> {

    // 允许的最大高度差(超过该该高度，树会失去平衡)
    private static final int ALLOWED_IMBALANCE = 1;

    // 根节点
    private AvlNode<AnyType> root;

    public AvlNode<AnyType> getRoot() {
        return root;
    }

    public AvlTree() {
        this.root = null;
    }

    public void insert(AnyType x) {
        root = insert(x, root);
    }

    public void remove(AnyType x) {
        root = remove(x, root);
    }

    /**
     * 计算节点的高度，空树的高度定义为-1，叶子节点的高度定义为0
     * @param t 节点
     * @return 节点的高度
     */
    private int height(AvlNode<AnyType> t) {
        return t == null ? -1 : t.height;
    }
    // 供外部调用获取高度
    public int height() {
        return height(root);
    }

    /**
     * 插入节点x
     * @param x 要插入的值x
     * @param t 插入的tree，这里一般是root节点
     * @return
     */
    private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> t) {
        if (t == null) {
            return new AvlNode<>(x, null, null);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            // 
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else {
            // 添加的节点已经存在
        }
        return balance(t);
    }

    /**
     * 平衡Avl树
     * @param t 树的根节点t
     * @return 平衡后的跟节点t
     */
    private AvlNode<AnyType> balance(AvlNode<AnyType> t) {
        if (t == null) {
            return t;
        }
        // 如果左子树的高度大于右子树超过1，则说明左边失去平和，需要右旋
        if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {
            // 如果左子树的左子树的高度 大于等于 左子树右子树的高度（左左情况，单右旋即可）
            if (height(t.left.left) >= height(t.left.right)) {
                t = rotateWithLeftChild(t);
            } else {
                // 否则，为左右情况(root的左子树 - 右子树> 1， 并且root.left.left < root.left.right)。
                // 需要(左)右双旋转
                t = doubleWithLeftChild(t);
            }
        } else {
            // 与上面相反
            if (height(t.right) - height(t.left) > ALLOWED_IMBALANCE) {
                if (height(t.right.right) >= height(t.right.left)) {
                    t = rotateWithRightChild(t);
                } else {
                    t = doubleWithRightChild(t);
                }
            }
        }
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

    /**
     * 向右单旋转 （左开弓(<) 变为右开弓形(>)）
     * @param k2 树根节点
     * @return 平衡后的根节点
     */
    private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2) {
        // 记录k2的左节点 k1
        AvlNode<AnyType> k1 = k2.left;
        // 将k2的左节点设置为k1的右节点(原本k2的左节点的右节点)
        k2.left = k1.right;
        // k2变为k1的右节点
        k1.right = k2;
        // k2的高度与k1的高度变化，需要重新计算
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height) + 1;
        return k1;
    }

    /**
     * 向(左)右双旋转(先左旋root的左子树，再右旋root)
     * @param root 树根节点
     * @return 平衡后的根节点
     */
    private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> root) {
        root.left = rotateWithRightChild(root.left);
        return rotateWithLeftChild(root);
    }

    /**
     * 向左单旋(与向左旋转相反)
     * @param root 根节点
     * @return 平衡后的根节点
     */
    private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> root) {
        AvlNode<AnyType> k1 = root.right;
        root.right = k1.left;
        k1.left = root;
        root.height = Math.max(height(root.left), height(root.right)) + 1;
        k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
        return k1;
    }

    /**
     * 从Avl树中删除节点t
     * @param x 要删除的节点x
     * @param t 根节点t
     * @return 删除节点后x的根节点(删除后需要重新平衡）
     */
    private AvlNode<AnyType> remove(AnyType x, AvlNode<AnyType> t) {
        if (t == null) {
            return null;
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = remove(x, t.left);
        } else if (compareResult > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) {
            // x=t 并且t的左右子节点不为空
            // 将root节点的值设置为右子树最小值，然后删除右子树的最小值
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);
        } else {
            // x=t 并且t的左右子节点 至少右一个为空
            t = t.left != null ? t.left : t.right;
        }
        return balance(t);
    }

    /**
     * 在root节点的所有子树中查找最小的节点
     * @param root
     * @return 找到的最小的节点
     */
    public AvlNode<AnyType> findMin(AvlNode<AnyType> root) {
        if (root != null) {
            while (root.left != null) {
                root = root.left;
            }
        }
        return root;
    }

    /**
     * 向(右)左双旋转(先右旋root的右子树，再左旋root)
     * @param root 树根节点
     * @return 平衡后的根节点
     */
    private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> root) {
        root.right = rotateWithLeftChild(root.right);
        return rotateWithRightChild(root);
    }

    private static class AvlNode<AnyType> {
        // 节点存储的值
        public AnyType element;
        // 左子节点
        public AvlNode<AnyType> left;
        // 右子节点
        public AvlNode<AnyType> right;
        // AVL树的高度
        public int height;

        public AvlNode(AnyType theElement) {
            this.element = theElement;
            this.left = null;
            this.right = null;
        }

        public AvlNode(AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt) {
            this.element = theElement;
            this.left = lt;
            this.right = rt;
            // 叶子节点的高度为0，空树的高度为-1
            this.height = 0;
        }  
    }
}

// 前序遍历(根，左右)，测试用
    public void preOrderPrint(AvlNode<AnyType> node){
        if(node != null) {
            System.out.print(node.element + "->");
            preOrderPrint(node.left);
            preOrderPrint(node.right);
        }
    }

    // 中序遍历(左根右)，测试用
    public void inOrderPrint(AvlNode<AnyType> node){
        if(node != null) {
            inOrderPrint(node.left);
            System.out.println(root.element + "->");
            inOrderPrint(root.right);
        }
    }

    // 后序遍历(左右根)，测试用
    public void postOrderPrint(AvlNode<AnyType> node){
        if(node != null) {
            postOrderPrint(node.left);
            postOrderPrint(root.right);
            System.out.println(root.element + "->");
        }
    }