package ALV;

public class ALVTreeDemo {
    /*
    平衡二叉树：也叫平衡二叉搜索树，也叫AVL，与二叉排序树相比，可以保证查询效率（前提是一颗二叉排序树）
    特点：左右两棵子树的高度差绝对值不超过一
    平衡二叉树的常用实现方法有：红黑树和AVL（算法）
     */
    public static void main(String[] args) {
        int[] arr = {10,11,7,6,8,9};
       AVLtree avl = new AVLtree();
        for (int i = 0; i <arr.length ; i++) {
            avl.add(new Node(arr[i]));
        }
        avl.midOrder();

        System.out.println(avl.getRoot().height());
        System.out.println(avl.getRoot().leftheight());
        System.out.println(avl.getRoot().rightheight());
    }
}

class  AVLtree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }
    //添加节点的方法
    public void add(Node node){
        if(root==null){
            root=node;
        }else{
            this.root.addNode2(node);
        }
    }
    //中序遍历
    public void midOrder(){
        if(this.root!=null){
            this.root.midOrder();
        }else{
            System.out.println("该树为空");
        }
    }
}

class Node{
    int value;
    Node left;
    Node right;
    public Node(){

    }
    public Node(int value){
        this.value=value;
    }
    //添加节点的方法
    //要求满足二叉排序树的要求
    public void addNode2(Node node){
        if(node==null){
            return;
        }
        if(node.value<this.value){
            if(this.left==null){
                this.left=node;
            }else{
                this.left.addNode2(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.addNode2(node);
            }
        }
        //添加完一个节点以后右子树的高度-左子树的高度>1,进行左旋转
        if(rightheight()-leftheight()>1){
            if(this.right!=null&&(this.right.leftheight()>this.right.rightheight())){
                this.right.rightRatate();
                leftRatate();
            }else{
                leftRatate();
            }

            return;
        }
        if(leftheight()-rightheight()>1){
            if(this.left!=null && this.left.rightheight()>this.left.leftheight()){
                //记当前节点的左子树为left节点
                //left节点的右子树高度>left节点的左子树高度，需要先将left节点进行左旋转
                this.left.leftRatate();
                rightRatate();
            }else{
                rightRatate();
            }
            //当前节点进行右旋转

        }
    }
    public void midOrder(){
        if(this.left!=null){
            this.left.midOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.midOrder();
        }
    }

    //计算以当前节点为根节点树的高度
    public int height(){
        return Math.max(this.left==null?0:this.left.height(),
                this.right==null?0:this.right.height())+1;
    }
    //返回左子树的高度
    public int leftheight(){
        if(this.left==null){
            return 0;
        }else{
            return this.left.height();
        }
    }
    //返回右子树的高度
    public int rightheight(){
        if(this.right==null){
            return 0;
        }else{
            return this.right.height();
        }
    }

    //左旋转的实现
    private void leftRatate(){
        //创建新的节点为当前根节点的值
        Node newborn = new Node(this.value);
        //新节点的左子节点为当前节点的左子节点
        newborn.left=this.left;
        //新节点的右子节点为当前节点的右子节点的左子节点（满足二叉排序树）
        newborn.right=this.right.left;
        //将当前节点替换为为当前节点的右子节点（右子树的高度降低）
        this.value=this.right.value;
        //新的根节点的右子节点为元根节点的右子节点，做子节点为新生成的节点
        //满足排序树
        this.right=this.right.right;
        this.left=newborn;
        //添加完一个节点以后调用
    }
    private void rightRatate(){
        //右旋
        Node newborn = new Node(this.value);
        newborn.right=this.right;
        newborn.left=this.left.right;
        this.value=this.left.value;
        this.left=this.left.left;
        this.right=newborn;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}