public class AVLTree {
    static class TreeNode{
        //內(nèi)部類，表示AVL樹的每個節(jié)點
        //val值
        public int val;
        //左孩子的引用
        public TreeNode left;
        //右孩子的引用
        public TreeNode right;
        //父親節(jié)點的引用
        public TreeNode parent;
        //平衡因子(每個節(jié)點都有）
        public int bf;
        public TreeNode(int val){
            this.val = val;
        }
    }
    //根節(jié)點
    public TreeNode root;
    public boolean insert(int val){
    }
}

   TreeNode node = new TreeNode(val);
        if(root == null){
            //沒有根節(jié)點，要插入的就是根節(jié)點
            root = node;
            return true;
        }
        //記錄每個節(jié)點的父節(jié)點
        TreeNode parent = null;
        //要移動的代節(jié)點
        TreeNode cur = root;
        //根據(jù)val的值和root進行比較來確定應該插入節(jié)點的位置
        while (cur != null){
            if(cur.val > val){
                //大于證明此節(jié)點應在左子樹
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                //大于證明此節(jié)點應在右子樹
                parent = cur;
                cur = cur.right;
            }else {
                //不能有值一樣的節(jié)點
                return false;
            }
        }
        //此時cur為空，需要找到對應的位置
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }

        //而此時就需要對樹進行平衡因子的調(diào)整了，保證樹是高度平衡的
        //再反著回去寫
        node.parent = parent;
        cur = node;
        //當父親節(jié)點一直存在的時候，就表示沒有調(diào)到根節(jié)點就需要繼續(xù)調(diào)整
        while(parent != null){
            if(cur == parent.right){
                //在右邊右樹高度加一，因此bf+1
                parent.bf++;
            }else{
                //再左邊，左樹高度加一，因此bf-1
                parent.bf--;
            }
            //在這里就要進行判斷了，如果此時的父親節(jié)點如果平衡因子為0了，那么就不需要再往上走了，因為上面的都是平衡的
	        if(parent.bf == 0){
	            return true;
	        }else if(parent.bf == -1 || parent.bf == 1){
	            //此時父親節(jié)點的平衡因子為1、-1
	             //此時表示當前樹平衡了，但是不表示整棵樹都平衡了，因此還需要繼續(xù)往上走
	            cur = parent;
	            parent = cur.parent;
	        }else{
	            //此時父親節(jié)點的平衡因子為2、-2
	            if(parent.bf == 2){
                //此時右樹高 需要降低右樹的高度
	                if(cur.bf == 1){
	                    //左單旋
	                    rotateLeft(parent);
	                }else{
	                    //右左雙旋
	                    rotateRL(parent);
	                }
	            }else{
	                //此時左樹高，需要降低左樹的高度
	                if(cur.bf == 1){
	                    //左右雙旋
	                    rotateLR(parent);
	                }else{
	                    //右單旋
	                    rotateRight(parent);
	                }
	            }
	            //調(diào)整完就平衡了
	            break;
	        }
        }

private void rotateRight(TreeNode parent){
        //右單旋
        //此時parent的平衡因子為-2，cur的平衡因子為-1
        TreeNode cur = parent.left;
        //記錄cur的右節(jié)點
        TreeNode curR = cur.right;
        parent.left = curR;
        cur.right = parent;
        //如果cur有右節(jié)點需要賦給parent的左節(jié)點，但是沒有就不需要給了
        if(curR != null){
            curR.parent = parent;
        }
        //然后將cur的右孩子改變?yōu)閜arent
        //需要記錄parent的根節(jié)點
        TreeNode pParent = parent.parent;
        parent.parent = cur;
        //檢查當前是不是根節(jié)點，不是根節(jié)點需要看是左子樹，還是右子樹
        if(pParent != null){
            //改變之前的指向
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //此時parent就是root，因為沒有根節(jié)點
            root = cur;
            root.parent = null;
        }
        //最后記得一定要修改平衡因子
        parent.bf = 0;
        cur.bf = 0;
    }

private void rotateLeft(TreeNode parent){
        //左單旋
        //此時parent平衡因子為2，cur的平衡因子為1
        //需要記錄父親節(jié)點
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.right;
        //記錄cur的左節(jié)點
        TreeNode curL = cur.left;
        parent.right = curL;
        cur.left = parent;
        //判斷左節(jié)點是不是空的，如果是空的就不需要管了，不是空的就需要將parent右節(jié)點指向它，并且它的父親節(jié)點為parent
        if(curL != null){
            //改變指向
            curL.parent = parent;
        }
        //改變cur的指向
        parent.parent = cur;
        //判斷如果pParent不為空，就表示parent不是root，就需要看其是左孩子還是右孩子
        if(pParent != null){
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //是根節(jié)點
            root = cur;
            root.parent = null;
        }
        cur.bf = 0;
        parent.bf = 0;
    }

private void rotateLR(TreeNode parent){
        //左右雙旋
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        //此時就需要看curR的平衡因子，再決定最后其他節(jié)點的平衡因子
        int bf = curR.bf;
        //先調(diào)用左旋再右旋
        rotateLeft(cur);
        rotateRight(parent);
        //這里通過規(guī)律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此里就需要做出修改
        if(bf == -1){
            //當bf為-1時，其應修改的如下
            curR.bf = 0;
            cur.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            //當bf為1時，其應修改的如下
            curR.bf = 0;
            cur.bf = -1;
            parent.bf = 0;
        }
        //另外當bf為0的時候就已經(jīng)平衡了，就不需要改了，因為在兩次旋轉(zhuǎn)的時候就已經(jīng)將其改為0了
    }

  private void rotateRL(TreeNode parent) {
        //右左雙旋
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        //此時就需要看curL的平衡因子了，再決定最后其他節(jié)點的平衡因子
        int bf = curL.bf;
        rotateRight(cur);
        rotateLeft(parent);
        //這里通過規(guī)律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此里就需要做出修改
        if(bf == -1){
            //當bf為-1時，其應修改的如下
            parent.bf = 0;
            cur.bf = 0;
            curL.bf = 1;
        }else if(bf == 1){
            //當bf為1時，其應修改的如下
            parent.bf = -1;
            curL.bf = 0;
            cur.bf = 0;
        }
        //另外當bf為0的時候就已經(jīng)平衡了，就不需要改了，因為在兩次旋轉(zhuǎn)的時候就已經(jīng)將其改為0了
    }