一：前言

学了半个暑假，平衡二叉树算是最恶心人的一个部分了，他的各种转向的可能性的判断确实让人难受，但是还是挺过来了。。。。一部分吧。。。

二：平衡树概念简述

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升^[1]。为了实现更高效的查询，产生了平衡树。

不平衡的树结构

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

1.结点代码

**
 * .
 * \* @author: xiaoyu
 * \* Date: 2021/8/27 TODO 平衡二叉树
 * \* Time: 22:28
 * \
 */
public class Node {
    //数据
    int data;
    //左指针
    Node child;
    //右指针
    Node brother;

    //当前节点高度
    int height;

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getChild() {
        return child;
    }

    public void setChild(Node child) {
        this.child = child;
    }

    public Node getBrother() {
        return brother;
    }

    public void setBrother(Node brother) {
        this.brother = brother;
    }
}

2.插入操作

/**
 * .
 * \* @author: xiaoyu
 * \* Date: 2021/8/27
 * \* Time: 22:31
 * \
 */
public class AVLTree {
    //根节点
    Node root;

    //为什么不用初始化，或者添加最大元素等数据
    /**
     * 插入操作,用户调用
     */
    public void insert(int data){
        this.root = insert(data,root);
    }
    /**
     * 插入操作 递归插入
     * @param data 要插入的结点数据
     * @param node  根节点
     * @return
     */

    public Node insert(int data,Node node){
        if (node == null){
            node = new Node(data);
        }

        if(node.getData()>data){
            node = insert(data,node.getChild());
            if (height(node.getChild()) - height(node.getBrother()) == 2){
                //判断是左孩子还是又孩子，如果是又孩子，则先右旋
                if (node.getChild().getData()>data){
                    //右旋操作
                    node = rightRotate(node);
                }else{
                    //左旋操作
                    node = leftRotate(node);
                }


            }
        }
        if (node.getData()<data){
            node = insert(data,node.getBrother());
            if (height(node.getChild()) - height(node.getBrother()) ==2){
                //
            }
        }
        //重新判断每个节点的高度
//        node.height = height(node) + 1;
        node.height = Math.max(height(node.getChild()),height(node.getBrother()));
        return node;
    }

    /**
     * 右旋操作 新增结点插入的根节点的左子树的左孩子
     * @param node  从这个结点开始 旋转
     * @return  根节点
     */


    public Node rightRotate(Node node){
        //先获取节点的左子树
        Node lefttree = node.getChild();
        //节点的左节点为子树的右节点
        node.setChild(lefttree.getBrother());
        //节点的右子树为节点
        lefttree.setBrother(node);
        //重新排序
        lefttree.height = Math.max(height(lefttree.getChild()),height(lefttree.getBrother())) + 1;
        //根节点的重新排序
        node.height = Math.max(height(node.getChild()),height(node.getBrother())) + 1;
        return lefttree;
    }
    /**
     * 左旋 新增结点插入根节点的右子树的右孩子
     * @param node 结点
     * @return  根节点
     */
    public Node leftRotate(Node node){
        //先获取节点的右子树
        Node righttree = node.getBrother();
        //节点的右节点为右子树的左孩子
        node.setBrother(righttree.getChild());
        //右子树的左节点为根节点
        righttree.setChild(node);
        //重新计算高度
        righttree.height = Math.max(height(righttree.getBrother()),height(righttree.getChild()));
        //重新计算根节点高度
        node.height = Math.max(height(node.getChild()),height(node.getBrother()));
        return righttree;
    }

    /**
     * 先左旋 在右旋
     * 左旋：找到最近的不平衡节点，对其左子树进行左旋
     * 右旋：对不平衡结点右旋
     * @return
     */
    public Node leftRightRatate(Node node){
        node.setChild(leftRotate(node.getChild()));

        return rightRotate(node);
    }
    public Node rightLeftRatate(Node node){
        node.setChild(rightRotate(node.getBrother()));
        return leftRotate(node);
    }



    /**
     * 高度的判断非常的巧妙，值得去吸收和学习
     * @param node
     * @return
     */
    public int height(Node node){
        return node == null ? -1 : node.getHeight();
    }
    /**
     * 遍历，采用前继遍历
     */
    public void preTraverse(){
        preTraverse(root);
    }
    public void preTraverse(Node node){
        if(node != null){
            System.out.println(node.data + "");
        }
        //访问左子树
        preTraverse(node.getChild());
        preTraverse(node.getBrother());
    }
}