public class AVL {
    class TreeNode{
        int val;
        int height;
        TreeNode left;
        TreeNode right;
        TreeNode (int val){
            this.val=val;
            this.height=0;
        }
        public void print(){
            if(left!=null) left.print();
            System.out.printf("%s-",val);
            if(right!=null) right.print();
        }
        public void printHeight(){
            if(left!=null) left.printHeight();
            System.out.printf("%s-",height);
            if(right!=null) right.printHeight();
        }
        // 层序遍历打印，方便看结果；
        public void printLevel(TreeNode root){
            TreeNode temp=root;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(temp);
            while(queue.size()>0){
                int size =queue.size();
                while(size-- > 0){
                    temp=queue.poll();
                    if(temp!=null){
                        System.out.printf("%s-%s  ",temp.val,temp.height);
                        queue.offer(temp.left);
                        queue.offer(temp.right);
                    }else{
                        System.out.printf("%s  ",null);
                    }
                }
                System.out.println();
            }
        }
    }
    // 计算高度
    public int height(TreeNode node){
        if(node==null) return -1;
        int lh=node.left==null?-1:node.left.height;
        int rh=node.right==null?-1:node.right.height;
        return Math.max(lh+1,rh+1);
    }

    // 左旋
    public TreeNode leftRotate(TreeNode root){
        if(root==null) return null;
        TreeNode temp= root.right;
        root.right=temp.left;
        temp.left=root;
        // 修改经过调整后对的高度计数
        root.height=height(root);
        temp.height=height(temp);
        return temp;
    }

    // 右旋
    public TreeNode rightRotate(TreeNode root){
        if(root==null) return null;
        TreeNode temp=root.left;
        root.left=temp.right;
        temp.right=root;
        // 修改经过调整后的高度计数
        root.height=height(root);
        temp.height=height(temp);
        return temp;
    }


    // 插入
    public TreeNode insert(TreeNode root,TreeNode node){
        if(root==null) return node;
        // 插入
        if(root.val>node.val){
            root.left=insert(root.left,node);
        }else{
            root.right=insert(root.right,node);
        }
        root.height=height(root);

        // 判断是否需要调整结构及高度(也可以把下面的调整结构部分写在上面插入的条件判断里，因为上面已经区分了左右)
        TreeNode leftChild = root.left;
        TreeNode rightChild = root.right;
        int lh=leftChild==null?-1:root.left.height;
        int rh=rightChild==null?-1:root.right.height;

        if(lh-rh>1){
            int llh= height(leftChild.left);
            int lrh= height(leftChild.right);
            //
            if(lrh>llh){
                root.left=leftRotate(root.left);
            }
            root=rightRotate(root);

        }else if(rh-lh>1){
            int rlh=height(rightChild.left);
            int rrh=height(rightChild.right);
            if(rlh>rrh){
                root.right=rightRotate(root.right);
            }
            root=leftRotate(root);
        }
        return root;
    }



    public TreeNode createTreeNode(int[] arr){
        if(arr.length<1) return null;
        TreeNode head = new TreeNode(arr[0]);
        for(int i=1;i<arr.length;i++){
            TreeNode node = new TreeNode(arr[i]);
            head = insert(head,node);
        }
        return head;
    }


    
    public static void main(String[] args) {
        int[] arr=new int[1000];
        for(int i=0;i<1000;i++){
            arr[i]=(int)Math.round(Math.random()*1000);
        }
        AVL avl=new AVL();
        TreeNode node = avl.createTreeNode(arr);
        node.print();
        System.out.println();
        node.printHeight();
        System.out.println();
        node.printLevel(node);

        Queue<Integer> queue=new LinkedList<Integer>();
        queue.offer(null);
        System.out.println();
        System.out.println(queue.size());

    }
}