public class AvlTree<E> {
    /**
     * 外部保存根節(jié)點的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 自定義比較器
     */
    private Comparator<? super E> cmp;


    /**
     * 樹節(jié)點的數(shù)量
     */
    private int size;

    /**
     * 內(nèi)部節(jié)點對象
     *
     * @param <E> 數(shù)據(jù)類型
     */
    public static class BinaryTreeNode<E> {

        //數(shù)據(jù)域
        E data;
        //左子節(jié)點
        BinaryTreeNode<E> left;
        //右子節(jié)點
        BinaryTreeNode<E> right;
        //節(jié)點高度 從0開始,從下往上;null節(jié)點高度返回-1
        int height;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }

    }

    /**
     * 指定比較器
     *
     * @param cmp 比較器
     */
    public AvlTree(Comparator<? super E> cmp) {
        this.cmp = cmp;
    }

    /**
     * 空構(gòu)造器
     */
    public AvlTree() {
    }

    /**
     * 是否是空樹
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回節(jié)點數(shù)
     *
     * @return 節(jié)點數(shù)
     */
    public int size() {
        return size;
    }


    /**
     * 對元素進行比較大小的方法,如果傳遞了自定義比較器,則使用自定義比較器,否則則需要數(shù)據(jù)類型實現(xiàn)Comparable接口
     *
     * @param e1 被比較的第一個對象
     * @param e2 被比較的第二個對象
     * @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
     */
    private int compare(E e1, E e2) {
        if (cmp != null) {
            return cmp.compare(e1, e2);
        } else {
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }


    /**
     * 保存遍歷出來的節(jié)點數(shù)據(jù)
     */
    List<BinaryTreeNode<E>> str = new ArrayList<>();

    /**
     * 中序遍歷,提供給外部使用的api
     *
     * @return 遍歷的數(shù)據(jù)
     */
    public String toInorderTraversalString() {

        //如果是空樹,直接返回空
        if (isEmpty()) {
            return null;
        }
        //從根節(jié)點開始遞歸
        inorderTraversal(root);
        //獲取遍歷結(jié)果
        String s = str.toString();
        str.clear();
        return s;
    }

    /**
     * 中序遍歷 內(nèi)部使用的遞歸遍歷方法,借用了棧的結(jié)構(gòu)
     *
     * @param root 節(jié)點,從根節(jié)點開始
     */
    private void inorderTraversal(BinaryTreeNode<E> root) {

        BinaryTreeNode<E> left = getLeft(root);
        if (left != null) {
            //如果左子節(jié)點不為null,則繼續(xù)遞歸遍歷該左子節(jié)點
            inorderTraversal(left);
        }
        //添加數(shù)據(jù)節(jié)點
        str.add(root);
        //獲取節(jié)點的右子節(jié)點
        BinaryTreeNode<E> right = getRight(root);
        if (right != null) {
            //如果右子節(jié)點不為null,則繼續(xù)遞歸遍歷該右子節(jié)點
            inorderTraversal(right);
        }
    }

    /**
     * 獲取左子節(jié)點
     *
     * @param parent 父節(jié)點引用
     * @return 左子節(jié)點或者null--表示沒有左子節(jié)點
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 獲取右子節(jié)點
     *
     * @param parent 父節(jié)點引用
     * @return 右子節(jié)點或者null--表示沒有右子節(jié)點
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }

    /**
     * 獲取根節(jié)點
     *
     * @return 根節(jié)點 ;或者null--表示空樹
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    /**
     * 獲取height
     *
     * @param node 節(jié)點
     * @return 高度或者-1 表示節(jié)點為null
     */
    private int getHeight(BinaryTreeNode<E> node) {
        return node == null ? -1 : node.height;
    }

}

    /**
     * 查找,開放給外部使用的api
     * @param e 要查找的元素
     * @return false 不存在 true 存在
     */
    public boolean contains(E e) {
        return contains(e, root);
    }

    /**
     * 查找,內(nèi)部調(diào)用的方法,從根節(jié)點開始查找
     *
     * @param e    要查找的元素
     * @param root 節(jié)點
     * @return false 不存在 true 存在
     */
    private boolean contains(E e, BinaryTreeNode<E> root) {
        /*null校驗*/
        if (root == null) {
            return false;
        }
        /*調(diào)用比較的方法*/
        int i = compare(e, root.data);
        /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
        if (i > 0) {
            return contains(e, root.right);
            /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
        } else if (i < 0) {
            return contains(e, root.left);
        } else {
            /*如果等于0，則說明e=root.date 即查詢成功*/
            return true;
        }
    }

    /**
     * 保存是否平衡的標(biāo)志
     */
    private boolean balance = true;

    /**
     * 檢查是否是平衡二叉樹的方法,當(dāng)然也可以debug看,如果你不嫌麻煩……
     *
     * @return true 是 ；false 否
     */
    public boolean checkBalance() {
        checkBalance(root);
        boolean balanceNow=balance;
        balance=true;
        return balanceNow;
    }

    /**
     * 遞歸檢查是否平衡,實際上這里采用了后序遍歷,即左子節(jié)點-右子節(jié)點-根節(jié)點的方法遞歸遍歷檢查
     *
     * @param root 根節(jié)點
     * @return 節(jié)點的高度
     */
    private int checkBalance(BinaryTreeNode<E> root) {
        if (root == null) {
            return -1;
        }
        //返回左子樹的高度
        int hl = checkBalance(root.left);
        //返回右子樹的高度
        int hr = checkBalance(root.right);
        //如果root的左右子樹高度差絕對值大于1,或者checkBalance和getHeight方法獲取的左/右子樹高度不一致,那么算作不平衡
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1 ||
                getHeight(root.left) != hl || getHeight(root.right) != hr) {
            balance = false;
        }
        return getHeight(root);
    }

   /**
     * 插入,開放給外部使用的api
     *
     * @param e 要插入的元素
     */
    public void insert(E e) {
        //返回root,但此時新的節(jié)點可能已經(jīng)被插入進去了
        root = insert(e, root);
    }

    /**
     * 插入,開放給外部使用的api
     *
     * @param es 要插入的元素的數(shù)組,注意,數(shù)組元素的順序存儲的位置將會影響二叉排序樹的生成
     */
    public void insert(E[] es) {
        //返回root,但此時新的節(jié)點可能已經(jīng)被插入進去了
        for (E e : es) {
            root = insert(e, root);
        }

    }

    /**
     * 插入,內(nèi)部調(diào)用的方法,先從根節(jié)點開始遞歸查找要插入的位置,然后插入
     * 大部分代碼都和排序二叉樹的相似，區(qū)別就是在插入之后，會調(diào)用嘗試重平衡的方法rebalance
     *
     * @param e    要插入的數(shù)據(jù)
     * @param root 節(jié)點
     * @return 原節(jié)點重平衡之后的節(jié)點或者新插入的節(jié)點
     */
    private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
        /*沒有查找到,那么直接構(gòu)建新的節(jié)點返回,將會在上一層方法中被賦值給其父節(jié)點的某個引用,這個插入的位置肯定是該遍歷路徑上的最后一點
         * 即插入的元素節(jié)點肯定是屬于葉子節(jié)點*/
        if (root == null) {
            size++;
            return new BinaryTreeNode<>(e);
        }
        /*調(diào)用比較的方法*/
        int i = compare(e, root.data);
        /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
        if (i > 0) {
            //重新賦值
            root.right = insert(e, root.right);
            /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
        } else if (i < 0) {
            //重新賦值
            root.left = insert(e, root.left);
        } else {
            /*如果等于0，則說明e=root.date 即存在節(jié)點 什么都不做*/
        }
        /*insert遞歸插入之后,在返回時,會調(diào)用重新平衡并且設(shè)置高度的方法 嘗試重平衡root根節(jié)點  而不是像排序二叉樹一樣簡單的返回root
         *從新插入節(jié)點的父節(jié)點一直向上回溯直到根節(jié)點,嘗試尋找最小不平衡樹,找到之后會進行平衡,返回返回平衡之后的樹,.*/
        return rebalance(root);
    }

    /**
     * 重平衡的方法
     * 1)	在節(jié)點X的左孩子節(jié)點的左子樹中插入元素，簡稱LL 右旋
     * 2)	在節(jié)點X的左孩子節(jié)點的右子樹中插入元素，簡稱LR 左-右雙旋
     * 3)	在節(jié)點X的右孩子節(jié)點的左子樹中插入元素，簡稱RL 左旋
     * 4)	在節(jié)點X的右孩子節(jié)點的右子樹中插入元素，簡稱RR 右-左雙旋
     *
     * @param root 樹的根節(jié)點,無論是否是最小不平衡樹,都是走這個方法
     * @return 平衡之后的樹的根節(jié)點
     */
    private BinaryTreeNode<E> rebalance(BinaryTreeNode<E> root) {
        /*1、如果節(jié)點為null,直接返回null*/
        if (root == null) {
            return null;
        }
        /*2、開始旋轉(zhuǎn)*/
        /*2.1、如果左子樹的高度減去右子樹的高度值大于1,說明左子樹的高度大于右子樹的高度至少2層,可能是情況1、2 繼續(xù)判斷*/
        if (getHeight(root.left) - getHeight(root.right) > 1) {
            /*如果左子節(jié)點的左子節(jié)點高度大于左子節(jié)點的右子節(jié)點高度,那說明是情況1,否則是情況2*/
            if (getHeight(root.left.left) >= getHeight(root.left.right)) {
                /*2.1.1、右旋*/
                root = rotateRight(root);
            } else {
                /*2.1.2、左-右雙旋*/
                root = rotateLeftAndRight(root);
            }
            /*2.2、如果右子樹的高度減去左子樹的高度值大于1,說明右子樹的高度大于左子樹的高度至少2層,可能是情況3、4 繼續(xù)判斷*/
        } else if (getHeight(root.right) - getHeight(root.left) > 1) {
            /*如果右子節(jié)點的右子節(jié)點高度大于右子節(jié)點的左子節(jié)點高度,那說明是情況4,否則是情況3*/
            if (getHeight(root.right.right) >= getHeight(root.right.left)) {
                /*2.2.1、左旋*/
                root = rotateLeft(root);
            } else {
                /*2.2.2、右-左雙旋*/
                root = rotateRightAndLeft(root);
            }
        }
        /*3、到這一步,說明旋轉(zhuǎn)完畢,或者不需要旋轉(zhuǎn),但是都需要重新計算高度,高度為左/右子樹高度最大值+1*/
        root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        return root;
    }


    /**
     * 右旋
     * 通解:右旋之后，k2成為根節(jié)點，k1成為k2的右子節(jié)點，k2的右子樹2成為k1的左子樹
     *
     * @param k1 需要旋轉(zhuǎn)的最小不平衡樹根節(jié)點
     * @return k2 旋轉(zhuǎn)后的最小不平衡樹根節(jié)點, 已經(jīng)轉(zhuǎn)換為平衡二叉樹
     */
    private BinaryTreeNode<E> rotateRight(BinaryTreeNode<E> k1) {
        //獲取k2,k2是k1的左子節(jié)點
        BinaryTreeNode<E> k2 = k1.left;
        //k2的右子樹成為k1的左子樹
        k1.left = k2.right;
        //k1成為k2的右子節(jié)點
        k2.right = k1;
        //k1的高度等于k1的左或者右子樹的高度的最大值+1;
        k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
        //k2的高度等于k2的左子節(jié)點和k1的高度(此時k1就是k2的右子節(jié)點)的最大值+1
        k2.height = Math.max(getHeight(k2.left), k1.height) + 1;
        //返回k2,k2成為根節(jié)點
        return k2;
    }

    /**
     * 左旋 很簡單,實際上就是右旋的鏡像
     * 通解:左旋之后，k2成為根節(jié)點，k1成為k2的左子節(jié)點，k2的左子樹2成為k1的右子樹
     *
     * @param k1 需要旋轉(zhuǎn)的最小不平衡樹根節(jié)點
     * @return k2 旋轉(zhuǎn)后的最小不平衡樹根節(jié)點, 已經(jīng)轉(zhuǎn)換為平衡二叉樹
     */
    private BinaryTreeNode<E> rotateLeft(BinaryTreeNode<E> k1) {
        //獲取k2,k2是k1的右子節(jié)點
        BinaryTreeNode<E> k2 = k1.right;
        //k2的左子樹成為k1的右子樹
        k1.right = k2.left;
        //k1成為k2的左子節(jié)點
        k2.left = k1;
        //k1的高度等于k1的左或者右子樹的高度的最大值+1;
        k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
        //k2的高度等于k2的右子節(jié)點和k1的高度(此時k1就是k2的左子節(jié)點)的最大值+1
        k2.height = Math.max(getHeight(k2.right), k1.height) + 1;
        //返回k2,k2成為根節(jié)點
        return k2;
    }

    /**
     * 右-左雙旋
     * 通解：將k3當(dāng)作新的根節(jié)點，并且先使得k2右旋成為k3的右子樹，然后k1左旋成為k3的左子樹，并且左子樹2成為k1的右子樹，右子樹2成為k2的左子樹
     *
     * @param k1 需要旋轉(zhuǎn)的最小不平衡樹根節(jié)點
     * @return 旋轉(zhuǎn)后的最小不平衡樹根節(jié)點, 已經(jīng)轉(zhuǎn)換為平衡二叉樹
     */
    private BinaryTreeNode<E> rotateRightAndLeft(BinaryTreeNode<E> k1) {
        /*1、先對k1的右子節(jié)點k2進行右旋,返回右旋之后的根節(jié)點k3,然后使得成為k3成為的k1的左子樹*/
        k1.right = rotateRight(k1.right);
        /*2、然后對k1進行左旋,成為k3的左子樹,返回的根節(jié)點就是k3,即返回旋轉(zhuǎn)之后的根節(jié)點*/
        return rotateLeft(k1);
    }

    /**
     * 左-右雙旋 很簡單,實際上就是右-左雙旋的鏡像
     * 通解: 將k3當(dāng)作新的根節(jié)點，并且先使得k2左旋成為k3的左子樹，然后k1右旋成為k3的右子樹，并且左子樹2成為k2的右子樹，右子樹2成為k1的左子樹
     *
     * @param k1 需要旋轉(zhuǎn)的最小不平衡樹根節(jié)點
     * @return 旋轉(zhuǎn)后的最小不平衡樹根節(jié)點, 已經(jīng)轉(zhuǎn)換為平衡二叉樹
     */
    private BinaryTreeNode<E> rotateLeftAndRight(BinaryTreeNode<E> k1) {
        /*1、先對k1的左子節(jié)點k2進行左旋,返回左旋之后的根節(jié)點k3,然后使得成為k3成為的k1的左子樹*/
        k1.left = rotateLeft(k1.left);
        /*2、然后對k1進行右旋,成為k3的右子樹,返回的根節(jié)點就是k3,即返回旋轉(zhuǎn)之后的根節(jié)點*/
        return rotateRight(k1);
    }

AvlTree<Integer> avlTree = new AvlTree<>();
Integer[] es = new Integer[]{3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
//批量插入
avlTree.insert(es);
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//數(shù)量
System.out.println(avlTree.size());

/**
 * 查找最小的節(jié)點
 *
 * @param root 根節(jié)點
 * @return 最小的節(jié)點
 */
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果該節(jié)點沒有左右子節(jié)點，那么該節(jié)點就是最小的節(jié)點，返回*/
    } else if (root.left == null) {
        return root;
    }
    /*如果該節(jié)點存在左子節(jié)點，那么繼續(xù)向左遞歸查找*/
    return findMin(root.left);
}

/**
 * 查找最大的節(jié)點
 *
 * @param root 根節(jié)點
 * @return 最大的節(jié)點
 */
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果該節(jié)點沒有右子節(jié)點，那么該節(jié)點就是最大的節(jié)點，返回*/
    } else if (root.right == null) {
        return root;
    }
    /*如果該節(jié)點存在右子節(jié)點，那么繼續(xù)向右遞歸查找*/
    return findMax(root.right);
}

/**
 * 刪除,開放給外部使用的api
 *
 * @param e 要刪除的元素
 */
public void delete(E e) {
    //返回root,但此時可能有一個節(jié)點已經(jīng)被刪除了
    root = delete(e, root);
}

/**
 * 刪除,內(nèi)部調(diào)用的方法,刪除分為三種情況: 1、該節(jié)點沒有子節(jié)點 2、該字節(jié)僅有一個子節(jié)點 3、該節(jié)點具有兩個子節(jié)點
 *
 * @param e    要刪除的數(shù)據(jù)
 * @param root (子)樹根節(jié)點
 * @return 該根節(jié)點重平衡之后的節(jié)點
 */
private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
    /*沒有查找到,那么什么都不做*/
    if (root == null) {
        return null;
    }
    /*調(diào)用比較的方法*/
    int i = compare(e, root.data);
    /*如果大于0，則說明e>root.date 繼續(xù)查詢右子樹*/
    if (i > 0) {
        //重新賦值
        root.right = delete(e, root.right);
        /*如果小于0，則說明e<root.date 繼續(xù)查詢左子樹*/
    } else if (i < 0) {
        //重新賦值
        root.left = delete(e, root.left);
    } else {
        /*如果等于0，則說明e=root.date 即查詢成功 開始執(zhí)行刪除*/
        /*如果兩個子節(jié)點都不為null*/
        if (root.left != null && root.right != null) {
            /*遞歸查找最小的節(jié)點，然后遞歸刪除*/
            root.data = findMin(root.right).data;
            root.right = delete(root.data, root.right);
        } else {
            /*如果一個子節(jié)點不為null，則返回該子節(jié)點；或者兩個子節(jié)點都為null，則返回null
             * 此時該root節(jié)點已經(jīng)被"繞過了"*/
            root = (root.left != null) ? root.left : root.right;
            --size;
        }
    }
    /*和二叉排序樹直接返回節(jié)點不同的是,刪除操作完成之后將會調(diào)用該方法,從被刪除節(jié)點回溯至根節(jié)點,對節(jié)點進行重平衡,然后才返回平衡后的節(jié)點*/
    return rebalance(root);
}

System.out.println("======>首先刪除5  此時沒有影響,不需要重平衡");
avlTree.delete(5);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());


System.out.println("======>再次刪除6  此時節(jié)點4的BF為2 需要右旋重平衡");
avlTree.delete(6);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());

System.out.println("======>再次刪除11  由于該節(jié)點擁有左右子樹,實際上刪除的是該節(jié)點的右子樹的最小節(jié)點12,然后將12的值賦值給11的節(jié)點,并導(dǎo)致節(jié)點12的原父節(jié)點11不平衡,需要重平衡");
avlTree.delete(11);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());

System.out.println("======>再次刪除7  由于該節(jié)點擁有左右子樹,實際上刪除的是該節(jié)點的右子樹的最小節(jié)點8,然后將8的值賦值給7的節(jié)點,并導(dǎo)致節(jié)點8的原父節(jié)點9不平衡,需要重平衡");
avlTree.delete(7);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());

System.out.println("======>再次刪除9、12  此時不需要重平衡");
avlTree.delete(9);
avlTree.delete(12);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());

System.out.println("======>最后刪除8  由于該節(jié)點擁有左右子樹,實際上刪除的是該節(jié)點的右子樹的最小節(jié)點10節(jié)點,然后將10的值賦值給8的節(jié)點,并導(dǎo)致節(jié)點10的原父節(jié)點13不平衡,需要重平衡");
avlTree.delete(8);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.size());
System.out.println(avlTree.toInorderTraversalString());