十六、AVL树

1、概念

• AVL树是最早发明的自平衡二叉搜索树之一
• AVL 取名于两位发明者的名字
  • G. M. Adelson-Velsky 和 E. M. Landis（来自苏联的科学家）
• Something interesting
  • 有人把AVL树念做“艾薇儿树”
  • 加拿大女歌手，几首不错的歌：《Complicated》、《When You're Gone》、《Innocence》

2、平衡因子

• 平衡因子（Balance Factor）：某结点的左右子树的高度差
• AVL树的特点
  • 每个节点的平衡因子只可能是 1、0、-1（绝对值 ≤ 1，如果超过 1，称之为“失衡”）
  • 每个节点的左右子树高度差不超过 1
  • 搜索、添加、删除的时间复杂度是O(logn)
    平衡因子

3、平衡对比

输入数据：35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82

平衡对比

4、添加导致的失衡

• 示例：往下面这棵子树中添加 13
• 最坏情况：可能会导致都失衡
• 父节点、非祖先节点，都不可能失衡

添加导致的失衡

4.1、节点旋转

4.1.1、LL – 右旋转（单旋）

LL代表的是g的左子树和p的左子树，在n节点的左或者右子树添加一个节点导致失衡，这种情况需要进行右旋转。

LL – 右旋转（单旋）

4.1.2、RR – 左旋转（单旋）

RR代表的是g的右子树和p的右子树，在n节点的左或者右子树添加一个节点导致失衡，这种情况需要进行左旋转。

RR – 左旋转（单旋）

4.1.3、LR – RR左旋转，LL右旋转（双旋）

LR代表的是g的左子树和p的的右子树，在n节点的左或者右子树添加一个节点导致失衡，这种情况需要进行先左旋转在右旋转。

LR – RR左旋转，LL右旋转（双旋）

4.1.4、RL – LL右旋转，RR左旋转（双旋）

RL代表的是g的右子树和p的的左子树，在n节点的左或者右子树添加一个节点导致失衡，这种情况需要进行先右旋转在左旋转。

RL – LL右旋转，RR左旋转（双旋）

4.2、代码实现

4.2.1、简单的继承结构

4.2.2、实现前准备

如果要进行平衡的调整，那么是要在添加之后进行调整的。那么在BST(二叉搜索树)里提供一个afterAdd方法给子类去实现。
BST.java中：

AVLTree.java中实现afterAdd方法：

4.2.3、实现afterAdd方法

如果添加一个节点后出现失衡，那么可以通过添加节点的parent.parent....可以找到失衡的节点，出现失衡的节点就进行调整。这里失衡的会出现多个节点，我们只需要调整最低的失衡节点就可以了(调整好最低的失衡节点，那么整个树就平衡了)。
伪代码：

@Override
protected void afterAdd(Node<E> node) {
    while((node = node.parent) != null) {
        //不断的找添加节点的parent
        if(node是否平衡) {
            
        }else {
            
        }
    }
}

4.2.4、计算平衡因子

这里需要在Node节点类里新增height属性，将来好用于计算平衡因子。

但是这个Node类是在BinaryTree(二叉树)类里面的,这个BinaryTree(二叉树)类又是通用的，不能强加一些AVLTree的东西到这里来，所以这里的height直接在AVLTree类里新增一个节点AVLNode类里。

但是这里又有要个新的问题，就是添加节点的方法是在BST类里，而这个添加方法里面用到的是Node类，那么AVLTree里的AVLNode就没法在添加里使用到，因此这里在BinaryTree里提供一个createNode方法提供给子类使用。
BinaryTree.java

protected Node<E> createNode(E element, Node<E> parent) {
    return new Node<>(element, parent);// 默认返回通用节点
}

BST.java

AVLTree.java中重写createNode方法

@Override
protected Node<E> createNode(E element, Node<E> parent) {
    return new AVLNode<>(element, parent);
}

在AVLNode类里提供一个平衡因子的balanceFactor方法

public int balanceFactor() {
    int leftHeight = left == null ? 0 : ((AVLNode)left).height;
    int rightHeight = right == null ? 0 : ((AVLNode)right).height;
    return leftHeight - rightHeight;
}

在AVLTree类里提供isBalanced方法来判断节点是否平衡

4.2.5、更新高度

上面求平衡因子有个问题，就是height默认是0，所以在判断平衡因子都是0，那么在什么情况下给高度进行赋值呢？有一种做法是这样的：之前有一种做法是通过递归求高度，一个节点的高度等于它左右子节点比较高度的高度加1，左右子节点的高度又等于它的左右子节点比较高度的高度加1，这样一层一层往下递归。但是这种效率太低了，没有必要这样做。
这里我可以在afterAdd方法的while循环里在判断节点是否平衡里可以做更新高度

protected void afterAdd(Node<E> node) {
    //不断的找添加节点的parent
    while((node = node.parent) != null) {
        if(isBalanced(node)) {
            // 更新高度
        }else {
            // 恢复平衡
        }
    }
}

这里只要是新添加的节点必然是叶子节点，那么我们默认给叶子节点的高度默认是1，就是在AVLNode里的height默认等于1。在AVLNode里提供一个updateHeight方法更新当前节点的高度。

4.2.6、恢复平衡

只要找到第一个不平衡的节点，让其恢复平衡，整个树就恢复平衡了。

这里的reblalance方法的参数node其实就是上面LL-左旋转的g节点，那么现在怎么找到p节点和n节点呢？p节点可以通过g节点的左右子节点的最高的那个，同理n节点也是一样的。这样也就可以知道旋转方向是LL、RR、LR、RL、RR了。


创建左旋转和右旋转的方法

4.2.7、左旋转的实现

可以根据上面的《RR – 左旋转（单旋）》图来实现具体的代码。

private void rotateLeft(Node<E> g) {
    // 因为是左旋转，那么p节点肯定是g节点的右子树
    Node<E> p = g.right;
    Node<E> child = p.left;
    g.right = child;
    p.left = g;
    
    // 让p成为这棵子树的根节点
    p.parent = g.parent;
    if(g.isLeftChild()) {
        g.parent.left = p;
    }else if(g.isRightChild()) {
        g.parent.right = p;
    }else {// g是root节点
        root = p;
    }
    
    // 更新child的parent
    if(child != null) {
        child.parent = g;
    }
    
    // 更新g的parent
    g.parent = p;
    
    // 更新高度(先更新比较矮的g，再更新比较高的p)
    updateHeight(g);
    updateHeight(p);
}

4.2.8、右旋转的实现

可以根据上面的《LL – 右旋转（单旋）》图来实现具体的代码。这里右旋转和左旋转都有相同的一些代码，所以可以抽出公共的方法afterRotate。

private void rotateLeft(Node<E> g) {
    // 因为是左旋转，那么p节点肯定是g节点的右子树
    Node<E> p = g.right;
    Node<E> child = p.left;
    g.right = child;
    p.left = g;
    afterRotate(g,p,child);
}

private void rotateRight(Node<E> g) {
    Node<E> p = g.left;
    Node<E> child = p.right;
    g.left = child;
    p.right = g;
    afterRotate(g,p,child);
}

private void afterRotate(Node<E> g, Node<E> p, Node<E> child) {
    // 让p成为这棵子树的根节点
    p.parent = g.parent;
    if(g.isLeftChild()) {
        g.parent.left = p;
    }else if(g.isRightChild()) {
        g.parent.right = p;
    }else {// g是root节点
        root = p;
    }
    
    // 更新child的parent
    if(child != null) {
        child.parent = g;
    }
    
    // 更新g的parent
    g.parent = p;
    
    // 更新高度(先更新比较矮的g，再更新比较高的p)
    updateHeight(g);
    updateHeight(p);
}

4.2.9、代码测试

可以通过BinaryTreeGraph (520it.com)这个网站和测试代码生成的AVL树进行对比，可以发现是一样的，说明代码是没有问题的

4.2.10、统一所有旋转操作

通过上图，我们可以发现LL、RR、LR、RL最终生成的树都是一样的，所以之前的左旋转和右旋转可以进行统一旋转操作。

/**
 * 恢复平衡
 * @param node 高度最低的那个不平衡节点
 */
private void reblalance(Node<E> g) {
    Node<E> p = ((AVLNode)g).tallerChild();
    Node<E> n = ((AVLNode)p).tallerChild();
    if(p.isLeftChild()) {// L
        if(n.isLeftChild()) {// LL
            rotate(g, n, n.right, p, p.right, g);
        }else {// LR
            rotate(g, p, n.left, n, n.right, g);
        }
    }else {// R
        if(n.isLeftChild()) {// RL
            rotate(g, g, n.left, n, n.right, p);
        }else {// RR
            rotate(g, g, p.left, p, n.left, n);
        }
    }
}

private void rotate(
        Node<E> r,// 子树的根节点
        Node<E> b,Node<E> c,
        Node<E> d,
        Node<E> e,Node<E> f) {
    // 让d成为这棵树的根节点
    d.parent = r.parent;
    if(r.isLeftChild()) {
        r.parent.left = d;
    }else if(r.isRightChild()) {
        r.parent.right = d;
    }else {
        root = d;
    }
    
    // b-c
    b.right = c;
    if(c != null) c.parent = b;
    updateHeight(b);
    
    // e-f
    f.left = e;
    if(e != null) e.parent = f;
    updateHeight(f);
    
    //b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}

5、删除导致的失衡

• 示例：删除子树中的16
• 可能会导致或失衡(只有1个节点会失衡)，其他节点，都不可能失衡
  

5.1、节点旋转

5.1.1、LL – 右旋转（单旋）

1. 下面删除红色节点后，会导致g节点失衡，当进行右旋转后恢复平衡(右边图)，但是如果绿色节点不存在，更高层的祖先节点可能会失衡，需要再次恢复平衡，然后又可能导致更高层祖先节点失衡...
2. 极端情况下，所有祖先节点都需要进行恢复平衡的操作，共0(logn)此调整。
   LL – 右旋转（单旋）

5.1.2、RR – 左旋转（单旋）

RR – 左旋转（单旋）

5.1.3、LR – RR左旋转，LL右旋转（双旋）

LR – RR左旋转，LL右旋转（双旋）

5.1.4、RL – LL右旋转，RR左旋转（双旋）

RL – LL右旋转，RR左旋转（双旋）

5.2、代码实现

删除代码大致跟添加节点一样，在BST(二叉搜索树)里新增afterRemove方法，以及在remove方法里调用afterRemove方法

通过之前介绍的《二叉搜索树--删除节点、clear和contains方法》里的的逻辑，可以知道有时在删除节点时，并不是真正的删除这个节点，而是将其子节点的元素替换要删除的节点元素。

这里，需要将afterRemove方法放在节点删除成功后调用，因为只有删除后才会导致失衡，这里的afterRemove方法又三处地方调用，也可以在remove方法的最后统一调用一次afterRemove方法，但是为啥还要在三个地方调用呢？这是因为以后在实现红黑树时通用。

在AVLTree类里重写afterRemove方法，逻辑跟afterAdd方法类似，只不过在恢复平衡哪里没有break语句了，这是因为，让父节点恢复平衡后，可能会导致更高层的祖先节点失衡，因此这里去掉break语句，让失衡的祖先节点也可以得到平衡。剩下的恢复平衡的代码和添加节点恢复平衡的逻辑一摸一样了。

6、总结

1. 添加

• 可能会导致都失衡
• 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1)次调整】

2. 删除

• 可能会导致或失衡（只有1个节点会失衡）
• 恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn)次调整】

3. 平均时间复杂度

• 搜索：O(logn)
• 添加：O(logn)，仅需O(1)次的旋转操作
• 删除：O(logn)，最多需要O(logn)次的旋转操作

代码路径