平衡二叉树（AVL）

简介

平衡二叉树（Balanced Binary Tree），又称AVL树，指的是左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大，对于任意一个节点，左子树与右子树的高度差最大为1。

上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

实现

本文的AVL树在上一篇BST树的基础上进行修改

实现AVL树之前，先实现四个辅助方法

节点高度

因为我们判断一个二叉树是否平衡是看其任意节点的左右子树的高度差是否小于等于1，因此我们在每个节点，存储该节点的高度。

class Node {
    private Node left; //左孩子
    private Node right; //右孩子
    private E e; //值
    private int height;//节点高度

    public Node(E e){
        left = null;
        right = null;
        this.e = e;
        height=1;//因为初始节点时，，高度默认为1
    }
}

//获得节点node的高度
public int getHeight(Node node){
    if(node==null){
        return 0;
    }
    return node.height;
}

在我们每次新增一个元素时，需要维护新增该节点受到影响的节点高度

public Node add(Node node, E e) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo(node.e) < 0) {
        node.left = add(node.left, e);
    }
    if (e.compareTo(node.e) > 0) {
        node.right = add(node.right, e);
    }
    //这里是递归调用，不管是在左子树新增节点，还是右子树新增节点，当前节点的高度肯定会+1
    //更新height= 当前节点左右子树最高的节点高度+1
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
}    

平衡因子

判断任意个节点左右子树的高度差，只要我们知道可计算出任意节点的平衡因子，就可以知道该二叉树是否为平衡二叉树

实现方法也很简单

//获得节点node的平衡因子
private int getBalanceFactor(Node node){
    if(node==null){
        return 0;
    }
    return getHeight(node.left)-getHeight(node.right);
}

检查二分搜索树性质&平衡性

判断二叉树是否为二分搜索树

我们知道二分搜索树任意节点的都大于该节点的左子树，小于该节点的右子树。即按照中序排序，默认是从小到大，我们利用这个性质可以判断一二叉树是否为二分搜索树

//判断当前二叉树是否是一颗二分搜索树
//因为二叉树，按照中序排序，默认是从小到大
public boolean isBST(){
    ArrayList<E> keys = new ArrayList<>();
    //将当前树，按中序遍历方式，放入数组
    inOrder(root,keys);
   for(int i=1;i<keys.size();i++){
       if(keys.get(i-1).compareTo(keys.get(i))>0){
           return false;
       }
   }
   return true;
}
private void inOrder(Node node,ArrayList<E> keys){
        if (node==null){
            return;
        }
        inOrder(node.left,keys);
        keys.add(node.e);
        inOrder(node.right,keys);
    }

判断二叉树是否平衡

前面我们已经实现了每个节点维护平衡因子的逻辑，因此判断一个二叉树是否平衡的方法，根据根节点递归判断所有子树中，是否存在平衡因子的绝对值大于1的，存在则说明该二分搜索树不平衡

//判断该二叉树是否时一颗平衡二叉树
public boolean isBalanced(){
    return isBalanced(root);
}
// 判断以node为根的二叉树是否是一颗平衡二叉树，递归算法
private boolean isBalanced(Node node){
    if(node==null){
        return true;
    }
    int balanceFactor = getBalanceFactor(node);
    if(Math.abs(balanceFactor)>1){//判断当前节点的二叉树平衡因子，即平衡因子的绝对值大于1
        return false;
    }
    //递归判断左右子孩子是否平衡
    return isBalanced(node.left)&&isBalanced(node.right);
}

综上我们在二分搜索树的基础上，如果维护二分搜索树的平衡性？就用到了旋转 且我们每次新增节点时，只有可能在该节点的父辈节点中，打破平衡性 因子在我们加入节点时，需要沿着节点向上维护平衡性

左左（LL）

从图中可看出，节点Y的平衡因子为2(>1)，左子树的平衡因子为1(大于0)，整个二叉树向左倾斜，即插入元素在不平衡节点的左侧的左侧，这种情况称为“左左”

针对左左，我们需要对二叉树进行右旋转

//对节点y进行向右旋转操作，返回旋转后的新的根节点x
//         y                        x
//        / \                     /   \
//       x   T4   向右旋转（y）   z       y
//      / \       ------->     /  \     / \
//     z   T3                T1   T2  T3  T4
//    / \
//  T1   T2
private Node rightRotate(Node y){//LL 右旋转
    Node x = y.left;
    Node T3 = x.right;
    //向右旋转
    x.right = y;
    y.left = T3;
    //维护高度
    y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
    return x;
}

右右（RR）

和左左同理，节点Y的平衡因子为-2(<-1)，左子树的平衡因子为-1(<0)，整个二叉树向右倾斜，即插入元素在不平衡节点的右侧的右侧，这种情况称为“右右”

针对右右，我们需要对二叉树进行左旋转

//左旋转
private Node LeftRotate(Node y){
    Node x = y.right;
    Node T2 = x.left;
    //向左旋转
    x.left = y;
    y.right = T2;
    //维护高度
    y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
    return x;
}

左右（LR）

从图中可看出，节点Y的平衡因子为2(>1)，左子树的平衡因子为-1(<0)，即插入元素在不平衡节点的左侧的右侧，这种情况称为“左右”

这种情况我们一般需要对该树，进行两次旋转，即先对X节点进行左选择，此时就又转换成了左左情况，然后再对节点Y进行右旋转即可

注意：我们前面左左和右右的情况，旋转时，看似都是在三个节点的基础上，其实做旋转有两个节点就够了，前面的旋转也仅是X、Y节点的旋转

//LR
if(balanceFactor>1&&getBalanceFactor(node.left)<0){
    node.left = LeftRotate(node.left);
    return rightRotate(node);
}

右左（RL）

从图中可看出，节点Y的平衡因子为-2(<-1)，右子树的平衡因子为1(>0)，即插入元素在不平衡节点的右侧的左侧，这种情况称为“右左”

这种情况我们一般需要对该树，进行两次旋转，即先对X节点进行右旋转，此时就又转换成了右右情况，然后再对节点Y进行左旋转即可

//RL
if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
    node.right = rightRotate(node.right);
    return LeftRotate(node);
}

新增

有了之前的辅助方法，我们的新增就简单许多了。在原二分搜索树的基础上，增加旋转操作来维护平衡性即可。

//以node为根节点，插入e 的递归写法
//返回插入新节点后二分搜索的根
public Node add(Node node, E e) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo(node.e) < 0) {
        node.left = add(node.left, e);
    }
    if (e.compareTo(node.e) > 0) {
        node.right = add(node.right, e);
    }
    //更新height= 当前节点左右子树最高的节点高度+1
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    //LL
    if(balanceFactor>1&&getBalanceFactor(node.left)>=0){//当前节点的平衡因子大于1 并且左子树的平衡因子大于=0
        return rightRotate(node);
    }
    //RR
    if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
        return LeftRotate(node);
    }
    //LR
    if(balanceFactor>1&&getBalanceFactor(node.left)<0){
        node.left = LeftRotate(node.left);
        return rightRotate(node);
    }
    //RL
    if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
        node.right = rightRotate(node.right);
        return LeftRotate(node);
    }
    return node;
}

删除

和新增同理，在二分搜索树删除的基础上，进行维护平衡性

//从二分搜索树中删除元素为e的节点
public void remove(E e){
    root =  removeNode(root,e);
}
// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
private Node removeNode(Node node, E e) {
    if (node == null) {
        return null;
    }
    Node retNode;//因为我们最后要统一维护树的平衡性，因此这里不可以直接返回node 最后再返回
    if (e.compareTo(node.e) > 0) {//如果e> node.e 则去node的右孩子找
        node.right = removeNode(node.right, e);
        retNode = node;
    } else if (e.compareTo(node.e) < 0) {//如果e< node.e 则去node的左孩子找
        node.left = removeNode(node.left, e);
        retNode = node;
    } else {//相等 进行删除逻辑
        // 注意：由BST的return改为直接赋值，下面的三种情况本身是互斥的，因此需要加else
        if (node.left == null) {//如果node.left 为空，则逻辑相当于删除 最小节点
            Node temp = node.right;
            node.right = null;
            size--;
            retNode = temp;
        } else if (node.right == null) {//如果node.right 为空，则逻辑相当于删除 最大节点
            Node temp = node.left;
            node.left = null;
            size--;
            retNode = temp;
        } else {//如果左右孩子都不为空，则默认把node的后继放到自己的位置
            //即，找node右孩子的最小节点
            Node rightMin = getMinNode(node.right);
            //且node的后继的右孩子为 removeMinNode(node.right) 这步相当于，把后继节点直接放到node的位置，原来的后继位置删除了
            //rightMin.right = removeMinNode(node.right);//注意removeMinNode里面已经有size--方法了
            //removeMinNode(node.right); 为删除node.right的最小值，而rightMin本身就是最小值，因此改用如下方法
            rightMin.right = removeNode(node.right, rightMin.e);//这样写 removeMinNode就不用维护平衡了
            rightMin.left = node.left;
            node.left = node.right = null;
            retNode = rightMin;
        }

    }
    //最终维护retnode的平衡 方法和新增相同
    if(retNode==null){//如果删除后的节点，返回的新的树节点为null，那么久不需要维护平衡了，直接返回null
        return null;
    }
    //更新height= 当前节点左右子树最高的节点高度+1
    retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);
    //LL
    if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){//当前节点的平衡因子大于1 并且左子树的平衡因子大于=0
        return rightRotate(retNode);
    }
    //RR
    if(balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
        return LeftRotate(retNode);
    }
    //LR
    if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
        retNode.left = LeftRotate(retNode.left);
        return rightRotate(retNode);
    }
    //RL
    if(balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
        retNode.right = rightRotate(retNode.right);
        return LeftRotate(retNode);
    }
    return retNode;
}

测试

public static void main(String[] args) {
    int n = 10000;
    Integer [] arr = ArrayGenatator.getRamArrayOrder(n,n);//随机获取长度为10000的数组
    AvlTree<Integer> bst1 = new AvlTree<>();
    for (int i=0;i<arr.length;i++){
        bst1.add(arr[i]);
    }
    System.out.println(bst1.isBalanced());
    System.out.println(bst1.isBST());
    bst1.remove(3);
    bst1.remove(4);
    bst1.remove(99);
    bst1.remove(100);
    bst1.remove(888);
    System.out.println(bst1.isBST());
    System.out.println(bst1.isBalanced());
}
运行结果：
true
true
true
true    

代码

public class AvlTree<E extends Comparable<E>>{

    class Node {
        private Node left; //左孩子
        private Node right; //右孩子
        private E e; //值
        private int height;//节点高度

        public Node(E e){
            left = null;
            right = null;
            this.e = e;
            height=1;//因为初始节点时，，高度默认为1
        }
    }

    private Node root;
    private int size;

    public int size(){
        return size;
    }

    //判断是否有元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    //判断以node为根节点的二分搜索树，是否有e
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        } else {
            return contains(node.left, e);
        }
    }

    //获得节点node的高度
    public int getHeight(Node node){
        if(node==null){
            return 0;
        }
        return node.height;
    }
    //获得节点node的平衡因子
    private int getBalanceFactor(Node node){
        if(node==null){
            return 0;
        }
        return getHeight(node.left)-getHeight(node.right);
    }
    //判断当前二叉树是否是一颗二分搜索树
    //因为二叉树，按照中序排序，默认是从小到大
    public boolean isBST(){
        ArrayList<E> keys = new ArrayList<>();
        //将当前树，按中序遍历方式，放入数组
        inOrder(root,keys);
       for(int i=1;i<keys.size();i++){
           if(keys.get(i-1).compareTo(keys.get(i))>0){
               return false;
           }
       }
       return true;
    }

    //判断该二叉树是否时一颗平衡二叉树
    public boolean isBalanced(){
        return isBalanced(root);
    }
    // 判断以node为根的二叉树是否是一颗平衡二叉树，递归算法
    private boolean isBalanced(Node node){
        if(node==null){
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor)>1){//判断当前节点的二叉树平衡因子
            return false;
        }
        //递归判断左右子孩子是否平衡
        return isBalanced(node.left)&&isBalanced(node.right);
    }

    private void inOrder(Node node,ArrayList<E> keys){
        if (node==null){
            return;
        }
        inOrder(node.left,keys);
        keys.add(node.e);
        inOrder(node.right,keys);
    }

    public void add(E e) {
        root = add(root, e);
    }

    //以node为根节点，插入e 的递归写法
    //返回插入新节点后二分搜索的根
    public Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        }
        if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        //更新height= 当前节点左右子树最高的节点高度+1
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);
        //LL
        if(balanceFactor>1&&getBalanceFactor(node.left)>=0){//当前节点的平衡因子大于1 并且左子树的平衡因子大于=0
            return rightRotate(node);
        }
        //RR
        if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){
            return LeftRotate(node);
        }
        //LR
        if(balanceFactor>1&&getBalanceFactor(node.left)<0){
            node.left = LeftRotate(node.left);
            return rightRotate(node);
        }
        //RL
        if(balanceFactor<-1&&getBalanceFactor(node.right)>0){
            node.right = rightRotate(node.right);
            return LeftRotate(node);
        }
        return node;
    }
    //获取二分搜索树的最大值
    public E getMaxValue(){
        if(size==0){
            throw new IllegalArgumentException("BST IS empty");
        }
        return getMaxNode(root).e;
    }
    //获取 以node为根节点，值最大值所在的节点
    private Node getMaxNode(Node node){
        if(node.right==null){
            return node;
        }
        return getMaxNode(node.right);
    }

    //获取二分搜索树的最小值
    public E getMinValue(){
        if(size==0){
            throw new IllegalArgumentException("BST IS empty");
        }
        return getMinNode(root).e;
    }
    //获取 以node为根节点，值最小值所在的节点
    private Node getMinNode(Node node){
        if(node.left==null){
            return node;
        }
        return getMinNode(node.left);
    }

    //对节点y进行向右旋转操作，返回旋转后的新的根节点x
    //         y                        x
    //        / \                     /   \
    //       x   T4   向右旋转（y）   z       y
    //      / \       ------->     /  \     / \
    //     z   T3                T1   T2  T3  T4
    //    / \
    //  T1   T2
    private Node rightRotate(Node y){//LL 右旋转
        Node x = y.left;
        Node T3 = x.right;
        //向右旋转
        x.right = y;
        y.left = T3;
        //维护高度
        y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
        x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
        return x;
    }
    //左旋转
    private Node LeftRotate(Node y){
        Node x = y.right;
        Node T2 = x.left;
        //向左旋转
        x.left = y;
        y.right = T2;
        //维护高度
        y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
        x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
        return x;
    }

    //删除二分搜索树的最小值 返回最小值
    public E removeMinValue(){
        E e = getMinValue();//获取最小值
        root = removeMinNode(root);
        return e;
    }
    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node removeMinNode(Node node){
        if(node.left==null){//递归的最终状态，如果node的左孩子为空，则说明它是最小的
            Node temp = node.right;//维护节点的右孩子
            node.right=null;
            size--;
            return temp;//删除后，根节点为右孩子，返回右孩子即可
        }
        //左孩子不为空，说明还不是最小，递归以左孩子为根节点找
        node.left =removeMinNode(node.left);
        return node;
    }

    //删除二分搜索树的最大值，返回最大值
    public E removeMaxValue(){
        E e = getMaxValue();
        root = removeMaxNode(root);
        return e;
    }

    // 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后新的二分搜索树的根
    public Node removeMaxNode(Node node){
        if(node.right==null){
            Node temp = node.left;
            node.left = null;
            size--;
            return temp;
        }
        node.right = removeMaxNode(node.right);
        return node;
    }

    //从二分搜索树中删除元素为e的节点
    public void remove(E e){
        root =  removeNode(root,e);
    }
    // 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    private Node removeNode(Node node, E e) {
        if (node == null) {
            return null;
        }
        Node retNode;//因为我们最后要统一维护树的平衡性，因此这里不可以直接返回node 最后再返回
        if (e.compareTo(node.e) > 0) {//如果e> node.e 则去node的右孩子找
            node.right = removeNode(node.right, e);
            retNode = node;
        } else if (e.compareTo(node.e) < 0) {//如果e< node.e 则去node的左孩子找
            node.left = removeNode(node.left, e);
            retNode = node;
        } else {//相等 进行删除逻辑
            // 注意：由BST的return改为直接赋值，下面的三种情况本身是互斥的，因此需要加else
            if (node.left == null) {//如果node.left 为空，则逻辑相当于删除 最小节点
                Node temp = node.right;
                node.right = null;
                size--;
                retNode = temp;
            } else if (node.right == null) {//如果node.right 为空，则逻辑相当于删除 最大节点
                Node temp = node.left;
                node.left = null;
                size--;
                retNode = temp;
            } else {//如果左右孩子都不为空，则默认把node的后继放到自己的位置
                //即，找node右孩子的最小节点
                Node rightMin = getMinNode(node.right);
                //且node的后继的右孩子为 removeMinNode(node.right) 这步相当于，把后继节点直接放到node的位置，原来的后继位置删除了
                //rightMin.right = removeMinNode(node.right);//注意removeMinNode里面已经有size--方法了
                //removeMinNode(node.right); 为删除node.right的最小值，而rightMin本身就是最小值，因此改用如下方法
                rightMin.right = removeNode(node.right, rightMin.e);//这样写 removeMinNode就不用维护平衡了
                rightMin.left = node.left;
                node.left = node.right = null;
                retNode = rightMin;
            }

        }
        //最终维护retnode的平衡 方法和新增相同
        if(retNode==null){//如果删除后的节点，返回的新的树节点为null，那么久不需要维护平衡了，直接返回null
            return null;
        }
        //更新height= 当前节点左右子树最高的节点高度+1
        retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(retNode);
        //LL
        if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){//当前节点的平衡因子大于1 并且左子树的平衡因子大于=0
            return rightRotate(retNode);
        }
        //RR
        if(balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
            return LeftRotate(retNode);
        }
        //LR
        if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
            retNode.left = LeftRotate(retNode.left);
            return rightRotate(retNode);
        }
        //RL
        if(balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
            retNode.right = rightRotate(retNode.right);
            return LeftRotate(retNode);
        }
        return retNode;
    }
    //遍历
    //前序遍历
    public void preOrder(){
        preOrder(root);
    }
    public void preOrder(Node node){
        if (node!=null){
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    }


    //后续遍历
    public void postOrder(){
        postOrder(root);
    }
    public void postOrder(Node node){
        if (node!=null){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }
    }




    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    // 生成以node为根节点，深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node, int depth, StringBuilder res){

        if(node == null){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e +"\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for(int i = 0 ; i < depth ; i ++)
            res.append("--");
        return res.toString();
    }


    public static void main(String[] args) {
        int n = 10000;
        Integer [] arr = ArrayGenatator.getRamArrayOrder(n,n);//随机获取长度为10000的数组
        AvlTree<Integer> bst1 = new AvlTree<>();
        for (int i=0;i<arr.length;i++){
            bst1.add(arr[i]);
        }
        System.out.println(bst1.isBalanced());
        System.out.println(bst1.isBST());
        bst1.remove(3);
        bst1.remove(4);
        bst1.remove(99);
        bst1.remove(100);
        bst1.remove(888);
        System.out.println(bst1.isBST());
        System.out.println(bst1.isBalanced());
    }
}

参考

• https://class.imooc.com/sale/datastructure?mc_marking=847f8fb5de6faa3343df639065d45b7d&mc_channel=imoocsearch
• http://www.cnblogs.com/skywang12345/p/3561803.html