二叉平衡树（AVL）

一种二叉排序树，其中每个节点的左子树和右子树的高度差至多等于1
基本思想：在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了平衡性，若是，找出最小不平衡树。在保持二叉排序树特性的前提下，调整最小不平衡树中各节点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

需要平衡处理的四种情况：

1.对当前节点的左孩子的左子树改变---- 右旋转
2.对当前节点的左孩子的右子树改变-----左右旋转
3.对当前节点的右孩子的左子树改变-----右左旋转
4.对当前节点的右孩子的右子树改变-----左旋转

    private static class BalanceBinaryNode {

        //关键字
        private String key;

        //值
        private int val;

        //高度
        private int height;

        //左子树
        private BalanceBinaryNode left;

        //右子树
        private BalanceBinaryNode right;

        public BalanceBinaryNode(String key, int val) {
            this.key = key;
            this.val = val;
        }

        public BalanceBinaryNode(String key, int val, int height) {
            this.key = key;
            this.val = val;
            this.height = height;
        }
    }

    //根节点
    public BalanceBinaryNode root;

    /**
     * 添加
     *
     * @param val
     */
    public void add(String key, int val) {
        if (root == null) {
            root = new BalanceBinaryNode(key, val, 1);
            return;
        }
        root = add(root, key, val);
    }

    /**
     * 添加
     *
     * @param val
     */
    public BalanceBinaryNode add(BalanceBinaryNode node, String key, int val) {
        if (node == null) {
            //根节点初始化，高度为1
            return new BalanceBinaryNode(key, val, 1);
        }

        //比根节点小，在左侧
        if (node.val > val) {

            //找到待插入的左节点，如果没有就新建结点
            node.left = add(node.left, key, val);
            //判断是否出现不平衡，相差达到2时，为不平衡。由于插入的数据，由于数据插入是一直插入到左子树的，所以必然是左边高
            if (height(node.left) - height(node.right) == 2) {
                //结点比左孩子小，则在左孩子的左子树，就是进行右旋
                if (node.left.val > val) {
                    node = rightRotate(node);
                } else {
                    //如果插入的是左孩子的右子树，则由平衡因子，左孩子变成了负数，结点是整数，需要先左旋再右旋转
                    //注意的是，左旋是左旋的该结点的孩子节点，右旋是右旋的该结点
                    node = leftRightRotate(node);
                }
            }
            //比节点大，在右侧
        } else if (node.val < val) {
            node.right = add(node.right, key, val);

            //插入节点的右侧，则肯定右子树的原因变成不平衡
            if (height(node.right) - height(node.left) == 2) {
                //比右孩子数值大，在右侧，进行左旋转
                if (node.right.val < val) {
                    node = leftRotate(node);
                } else {
                    //比右孩子数值小，在右孩子的做孩子节点上，右孩子左孩子节点平衡因子为正，右孩子节点为负数，先右旋在左旋
                    node = rightLeftRotate(node);
                }
            }

        } else {
            //碰到相等的数据，就覆盖掉
            node.key = key;
        }

        node.height = updateHeight(node);
        return node;
    }

    public void remove(int val) {
        root = remove(root, val);
    }

    public BalanceBinaryNode remove(BalanceBinaryNode node, int val) {
        if (node == null) {
            return null;
        }

        //删除的结点在左侧
        if (node.val > val) {
            node.left = remove(node.left, val);
            //因为删除的是左子树的结点，出现不平衡，只会是右边高左边低
            if (height(node.right) - height(node.left) == 2) {
                node = leftRotate(node);
            }
        } else if (node.val < val) {
            //因为删除的是结点的右子树上的结点，出现不平衡只会是左高右低
            node.right = remove(node.right, val);
            if (height(node.left) - height(node.right) == 2) {
                node = rightRotate(node);
            }

        } else {
            //处理一个结点为空时，将另一个子节点赋值给父节点的左右节点
            if (node.right == null) {
                return node.left;
            }

            if (node.left == null) {
                return node.right;
            }

            //都不是空。找到右子树的最小节点，和该结点替换
            BalanceBinaryNode minNode = findMin(node.right);
            minNode.right = removeMin(node.right);
            minNode.left = node.left;

            node = minNode;
            if(height(node.left) - height(node.right) == 2){
                node = rightRotate(node);
            }
        }
        node.height = updateHeight(node);
        return node;
    }

    public BalanceBinaryNode findMin(BalanceBinaryNode node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public BalanceBinaryNode removeMin(BalanceBinaryNode node) {
        if (node == null) {
            return null;
        }

        if (node.left == null) {
            return node.right;
        }

        node.left = removeMin(node.left);

        if (height(node.right) - height(node.left) == 2) {
            node = leftRotate(node);
        }

        return node;
    }

    /**
     * 右旋操作
     *
     * @param node
     */
    public BalanceBinaryNode rightRotate(BalanceBinaryNode node) {
        BalanceBinaryNode x = node.left;
        node.left = x.right;
        x.right = node;

        node.height = updateHeight(node);
        x.height = updateHeight(x);

        return x;
    }

    /**
     * 左旋
     *
     * @param node
     */
    public BalanceBinaryNode leftRotate(BalanceBinaryNode node) {
        BalanceBinaryNode x = node.right;
        node.right = x.left;
        x.left = node;

        node.height = updateHeight(node);
        x.height = updateHeight(x);

        return x;
    }

    /**
     * 左右旋转
     *
     * @param node
     */
    public BalanceBinaryNode leftRightRotate(BalanceBinaryNode node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    /**
     * 右左旋转
     *
     * @param node
     * @return
     */
    public BalanceBinaryNode rightLeftRotate(BalanceBinaryNode node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    /**
     * 修改高度，如果该结点没有左右孩子结点，高度为1
     *
     * @param node
     * @return
     */
    private int updateHeight(BalanceBinaryNode node) {
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    /**
     * 获取高度，默认为0
     *
     * @param node
     * @return
     */
    private int height(BalanceBinaryNode node) {
        return node == null ? 0 : node.height;
    }