搞定面试中的平衡二叉树（AVL树）！

简单介绍

什么是平衡二叉树？

平衡二叉树简称AVL，是改进的二叉搜索树，拥有自平衡特性。

为什么需要平衡二叉树？

这是一棵二叉搜索树：

二叉搜索树出现的目的是为了帮助我们将普通二叉树的查找效率优化。但是像上图这样的情况下二叉搜索树的查找效率和普通二叉树是一样的。深度拓展到比较大的数的情况下查找效率就很不美观了...

于是我们就希望在二叉搜索树的基础上，树上的节点能分布的更加“分散”一些，而不是“线性”的排列，这样才能更大程度的利用它二分法查找的功能：

我们把这样节点”分散“的二叉搜索树规定了标准，并把拥有这样特性的二叉搜索树叫做平衡二叉树(AVL树)。

平衡二叉树的特性

「在满足二叉搜索树的性质基础上」：任何一个节点的左右子树都是平衡二叉树，并且左右子树的高度之差的绝对值不能超过1。

平衡因子

我们在讨论平衡二叉树的某节点的左右子树的高度差的时候习惯以「平衡因子」来代称。

所以我们能很容易总结一条特性： “平衡二叉树中不存在平衡因子大于1的节点。”

平衡因子大小的含义：

• 0：左右子树登高。

• 1：左子树比右子树高1。

• -1：右子树比左子树高1。

平衡二叉树的失衡和调整

什么是失衡

向平衡二叉树插入一个新的节点，导致树中存在节点不满足平衡二叉树特性，则称该平衡二叉树失衡了。

并且从新插入节点往上查找，第一个平衡因子的绝对值超过1的节点为根的子树，我们称为「最小失衡子树」。

调整操作

❝

接下来我们分析调整过程，作图用圆圈代表节点，方框代表子树，「这里的子树都是高度相同的」。额外的小方框理解成新插入的节点作为子树高度的叠加。

❞

LL型

A的平衡因子>1，并且失衡原因出在A的左孩子的左子树。这个时候我们进行LL调整，B往上抬，替代A的位置，A顺次往下，作为B的右孩子，这个过程中B的原右孩子不得不与B拆散，并且填补到唯一的空缺：A的左子树。

❝

解决LL型的冲突的旋转我们也可以叫做「右旋」

❞

编码实现：

 private Node<T> llRotate(Node<T> avlNode) {
     Node<T> node = avlNode.leftChild;
     avlNode.leftChild = node.rightChild;
     node.rightChild = avlNode;
     return node;
 }

RR型

A的平衡因子>1，并且失衡原因出在A的右孩子的右子树。

❝

RR就和LL的描述同理了。

❞

❝

解决LL型的冲突的旋转我们也可以叫做「左旋」

❞

❝

这个时候编码就很简单了，直接和LL型反过来就OK了。

❞

编码实现：

 private Node<T> rrRotate(Node<T> avlNode) {
     Node<T> node = avlNode.rightChild;
     avlNode.rightChild = node.leftChild;
     node.leftChild = avlNode;
     return node;
 }

LR型

A的平衡因子>1，并且失衡原因出在A的左孩子的右孩子的子树。

同样的，我们从根出发根据LR找到C，然后往上拎到根节点的位置，A往下放，和B分别作为C的右子树和左子树，这个过程C的子树只能和C拆散并就近的连接在B的右边和A的边了。

也可以这样理解，先以节点的左孩子为根进行RR调整，再对该节点进行LL调整。

编码实现：

 private Node<T> lrRotate(Node<T> avlNode) {
   // 等同于先对节点的左孩子为根进行RR调整，再对该节点进行LL调整
     avlNode.leftChild = rrRotate(avlNode.leftChild);
     return llRotate(avlNode);
 }

❝

深入理解LR型

❞

对于LR型，我们构建最简单的模型：

这个情况下我们解决冲突尝试对A进行右旋，结果可以预想到，没有解决掉冲突，反而变成了RL型冲突：

于是我们联想到了可不可以将LR型冲突先转换成LL型冲突，然后再解决问题，即：

这样一来我们当前的模型已经无法满足我们的转换要求了，我们引入一个新的点C

对B进行一次左旋，这下结果就变成了我们想要的LL型冲突了！

那么解决LL型冲突，只需要对A进行一次右旋就可以解决冲突了

RL型

A的平衡因子>1，并且失衡原因出在A的右孩子的左孩子的子树。

❝

RL就和LR的描述同理了。

❞

❝

这个时候编码也很简单了，直接和LR型反过来就OK了

❞

编码实现：

 private Node<T> rlRotate(Node<T> avlNode) {// 等同于先对节点的右孩子为根进行LL调整，再对该节点进行RR调整
     avlNode.rightChild = llRotate(avlNode.rightChild);
     return rrRotate(avlNode);
 }

平衡二叉树的编码

❝

本部分不包括「上面已经提供的」调整操作编码。

❞

平衡二叉树节点的定义

public class Node<T extends Comparable<T>> {
    /**
     * 数据域
     */
    public T data;
    /**
     * 节点子树的高度，依据此计算平衡因子
     */
    public int height;
    /**
     * 左孩子
     */
    public Node<T> leftChild;
    /**
     * 右孩子
     */
    public Node<T> rightChild;
    public Node(T data) {
        this(data, null, null);
    }
    public Node(T data, Node<T> leftChild, Node<T> rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

计算节点深度

private int getAvlTreeHeight(Node<T> node) {
    if (node == null) {
        return 0;
    } else {
        int leftWeight = getAvlTreeHeight(node.leftChild);
        int rightWeight = getAvlTreeHeight(node.rightChild);
        return Math.max(leftWeight, rightWeight) + 1;
    }
}

插入节点操作

private Node<T> balance(Node<T> node) {
    // 左子树比右子树高度大于1以上
    if (getAvlTreeHeight(node.leftChild) - getAvlTreeHeight(node.rightChild) > 1) {
        if (getAvlTreeHeight(node.leftChild.leftChild) >= getAvlTreeHeight(node.leftChild.rightChild)) {
            // 执行LL型调整
            node = llRotate(node);
        } else {
            // 执行LR型调整
            node = lrRotate(node);
        }
    } else if (getAvlTreeHeight(node.rightChild) - getAvlTreeHeight(node.leftChild) > 1) {
        if (getAvlTreeHeight(node.rightChild.rightChild) >= getAvlTreeHeight(node.rightChild.leftChild)) {
            // 执行RR型调整
            node = rrRotate(node);
        } else {
            // 执行RL型调整
            node = rlRotate(node);
        }
    }
    return node;
}

private Node<T> insert(Node<T> root, T data) {
    // 根节点为空，说明树为空，则创建一颗树
    if (root == null) {
        return new Node<>(data);
    } else {
        if (compare(root, data) > 0) {
            root.leftChild = insert(root.leftChild, data);
            root = balance(root);
        } else if (compare(root, data) < 0) {
            root.rightChild = insert(root.rightChild, data);
            root = balance(root);
        }
        return root;
    }
}

建树操作

public void createTree(T data) {
    if (data == null) {
        return;
    }
    root = insert(root, data);
}

删除节点操作

「节点的类型有三种：」

• 叶子节点；
• 只有左子树或只有右子树；
• 既有左子树又有右子树。

「删除后调整：」

• 「当删除的节点是叶子节点：」 将节点删除，然后从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，此时到根节点还发现没有失衡，则说此时树是平衡的；如果中间过程发现失衡，则判断属于哪种类型 的失衡（左左，左右，右左，右右），然后进行调整。
• 「删除的节点只有左子树或只有右子树：」 这种情况其实就比删除叶子节点的步骤多一步，就是将节点删除，然后把仅有一支的左子树或右子树替代原有结点的位置，后面的步骤就一样了，从父节点开始，判断是否失衡，如果没有失衡，则再判断父节点的父节点是否失衡，直到根节点，如果中间过程发现失衡，则根据失衡的类型进行调整。
• 「删除的节点既有左子树又有右子树：」 这种情况又比上面这种多一步，就是中序遍历，找到待删除节点的前驱或者后驱都行(前驱为该节点左子树权最大节点，后驱为该节点右子树最小节点)，然后与待删除节点互换位置，然后把待删除的节点删掉，后面的步骤也是一样，判断是否失衡，然后根据失衡类型进行调整。

/**
     * 删除接口
     *
     * @param data 数据
     */
public void remove(T data) {
    if (data==null){
        throw new RuntimeException("data can't not be null ");
    }
    this.root=remove(root,data);
}

public Node<T> remove(Node<T> root, T data){
    if(root ==null)
        return null;
    int result=data.compareTo(root.data);
    //从左子树查找需要删除的元素
    if(result<0){
        root.leftChild=remove(root.leftChild, data);
        root=balance(root);
    }
    //从右子树查找需要删除的元素
    else if(result>0){
        root.rightChild=remove(root.rightChild, data);
        //检测是否平衡
        root=balance(root);
    }
    //已找到需要删除的元素,并且要删除的结点拥有两个子节点
    else if(root.rightChild!=null&&root.leftChild!=null){
        //寻找替换结点
        root.data=findMin(root.rightChild).data;
        //移除用于替换的结点
        root.rightChild = remove(root.rightChild ,root.data);
    }
    else {
        //只有一个孩子结点或者只是叶子结点的情况
        root = (root.leftChild!=null)? root.leftChild:root.rightChild;
    }
    //更新高度值
    if(root!=null)
        root.height = Math.max(getAvlTreeHeight(root.leftChild), getAvlTreeHeight(root.rightChild)) + 1;
    return root;
}

/**
     * 查找最小值结点
     * @param root 根
     * @return
     */
private Node<T> findMin(Node<T> root){
    if (root==null)//结束条件
        return null;
    else if (root.leftChild==null)//如果没有左结点,那么t就是最小的
        return root;
    return findMin(root.leftChild);
}

功能测试

测试建AVL树：

public class TestAvlTree {

    private static final Integer[] arrays = new Integer[]{26, 21, 30, 50, 60, 66, 68, 70};

    @Test
    public void testCreateTree(){
        AvlTree<Integer> avlTree = new AvlTree<>();
        for (Integer data : arrays) {
            avlTree.createTree(data);
        }
        avlTree.printTree();
    }
}

测试结果：

前序遍历： 50 26 21 30 66 60 68 70 
中序遍历： 21 26 30 50 60 66 68 70 
后序遍历： 21 30 26 60 70 68 66 50

当前树的图示如下：

测试删除：

@Test
public void testDeleteTree(){
    AvlTree<Integer> avlTree = new AvlTree<>();
    for (Integer data : arrays) {
        avlTree.createTree(data);
    }
    avlTree.printTree();
    System.out.println("删除掉30");
    avlTree.remove(30);
    avlTree.printTree();
}

前序遍历： 50 26 21 30 66 60 68 70 
中序遍历： 21 26 30 50 60 66 68 70 
后序遍历： 21 30 26 60 70 68 66 50 
删除掉30
前序遍历： 50 26 21 66 60 68 70 
中序遍历： 21 26 50 60 66 68 70 
后序遍历： 21 26 60 70 68 66 50

小结

平衡二叉树是高度平衡的二叉树，「查询的时间复杂度是O(logN)」 。插入的话如果失衡则进行四种调整，最多也只需要调整2次，所以「插入的时间复杂度是O(1)」 。

平衡二叉树的问题在于删除处理，删除节点可能失衡，导致需要从删除节点的父节点开始，不断回溯到根节点，如果平衡二叉树很高的话则需要判断多个节点。

所以后面出现了综合性能更好的树--红黑树。