平衡二叉搜索树之AVL树

1、二叉搜索树的复杂度分析

• 1、如果按照7、4、9、2、5、8、11顺序添加节点（添加顺序和层序遍历的结果一致），则构造成的二叉搜索树如下图：
  image.png
  在二叉搜索树中我们讲述了添加、删除和查询的实现。

• 1、添加：比如添加一个值为12的节点，则会先和根节点7进行比较，然后和9比较，最后和11进行比较，大于11，添加到11的右边。从上面添加过程可以看到，添加的复杂度是和树的高度相关，复杂度为O(h)。而对于满二叉树来说O(h)==O(logn)。
• 2、删除和查询：对于删除和查询来说，也是需要去查找元素，和添加相同，其复杂度为O(h)==O(logn)。

• 2、如果按照从小到大的顺序添加节点

  
  image.png
• 3、这样一来二叉树就退化成了链表，那么此时二叉搜索树的搜索、添加、删除的复杂度就变成了O(h)==O(n)。
  对于上面两种二叉搜索树来说，如果n比较大时，两者的性能差别还是很大的。
• 4、二叉搜索树在删除节点时，也可能会造成二叉树退化成链表。
  那么能不能保证在添加、删除节点时，二叉树不退化成链表，让添加、删除、搜索的复杂度保持在O(logn)?

2、平衡

想要让二叉搜索树在添加和删除之后，不退化成链表，就需要保证它的平衡。

• 平衡：当节点数量固定，左右子树的高度越接近，这颗二叉树就越平衡。高度也会越低。
  image.png
• 最理想的平衡：相同节点数量，完全二叉树或满二叉树就会越平衡。这也是最理想的平衡。
  image.png

3、如何改进二叉搜索树

• 首先，我们不可能限制添加、删除的顺序。

• 所以改进方案是：在添加、删除后，想办法让二叉搜索树恢复平衡，也就是减少树的高度。

  
  image.png
  

  可以看到经过操作将上图中的树的高度减少1，其实可以继续减少树的高度

  
  image.png
• 如果继续调整节点的位置，完全可以达到最理想平衡的状态，但是要付出的代价可能比较大。
  - 比如调整的次数太多，反而增加了时间复杂度。
• 所以，比较合理的解决方案：用尽量少的调整次数来达到适度平衡。
• 一棵达到适度平衡的二叉树称为平衡二叉搜索树。

4、平衡二叉搜索树（Balanced Binary Search Tree）

英文简称为BBST，常见的平衡二叉搜索树有：AVL树和红黑树。
一般也称它们为自平衡的二叉搜索树（Self-balancing Binary Search Tree）。
下面主要来看下AVL树。

5、AVL树

先来看一些基本概念：

• 1、平衡因子（Balance Factor）：一个节点的左右子树的高度差。
• 2、AVL树的特点：
  • 1、每个节点的平衡因子只能是1、0、-1，绝对值<=1，如果平衡因子的绝对值大于1，则树失衡。
  • 2、每个节点的左右子树高度差小于等于1。

  • 3、AVL树的搜索、添加、删除的时间复杂度为O(logn)。

    
    image.png
    

    左侧二叉搜索树没有满足每个节点的平衡因子的绝对值不大于1，右侧二叉搜索树每个平衡因子的绝对值不大于1，所以右侧树是AVL树。

5.1、AVL树添加导致的失衡

先看下图中的二叉搜索树的子树

image.png
可以看出上图中的子树是满足AVL特性的，如果添加值为13的节点，构建的二叉搜索树如下
image.png
可以发现在添加节点之后，节点14、15、9的平衡因子的绝对值大于了1。
总结：

• 1、添加节点，在最坏的情况下，会导致添加节点的所有祖父节点都失衡。

由于上图是二叉树的一部分，在添加节点之后，这个子树的高度增加了1，假设该子树是节点9的父节点的右子树，如果在添加之前9的父节点平衡因子为-1，那么在添加之后其平衡因子变成了-2。以此类推，最坏情况下会导致所有祖父节点都失衡。

• 2、父节点和非祖父节点，都不可能失衡。

• 1、父节点在添加之前无非就有两种情况：a、度为1；2、度为0，在这两种情况下，添加节点都不会导致父节点失衡。
• 2、添加节点只会影响父节点以及祖父节点的平衡因子，并不会影响其他节点的平衡因子。这种情况自己想下很好理解。

下面看下添加导致失衡的四种情况。

5.1.1、LL-右旋转（单旋）

image.png

• 上图中红色块代表的要添加的节点
• T0、T1、T2、T3表示的是子树，可能为空。
• g是祖父节点，表示失衡的节点；p是父节点，祖父节点的左子树的根节点；n表示node节点，父节点的左子树的根节点。
• 从上图可以看出要添加的节点是在祖父节点g的left-left，所以称为LL。
• 针对LL的情况，需要将祖父节点g进行右旋转，来恢复平衡。
• 添加一个节点，在最坏的情况下会导致所有祖父节点失衡，从要添加的节点的node.parent.parent....祖父节点中去找失衡节点，找到第一个失衡的祖父节点，使其恢复平衡，这样整棵树都会恢复平衡。

添加节点导致其祖父节点失衡的原因是祖父节点的子树的高度增加了，在经过右旋转后，子树的高度会变成添加前子树的高度，所以整棵树都恢复了平衡。

右旋的伪代码实现：

• 1、g.left=p.right;
• 2、p.right=g;
• 3、让p称为子树的根节点；
• 4、旋转之后仍然是一棵二叉搜索树：T0 < n < T1 < p < T2 < g < T3
• 5、维护T2、g、p的parent属性
• 6、按顺序维护g、p的高度

由于右旋之后，p变成了根节点，而g变成了p的子节点，所以需要p的高度==p的高度+1。所以需要先维护g的高度。

5.1.2、RR-左旋转（单旋）

image.png

• 要添加的节点在祖父节点的right-right，属于RR情况。
• 需要将祖父节点g进行左旋，恢复树的平衡。
  左旋的伪代码实现
• 1、g.right=p.left;
• 2、p.left=g;
• 3、让p成为子树的根节点；
• 4、旋转之后仍然是一棵二叉搜索树T0 < g < T1 < p < T2 < n < T3
• 5、维护g、p、T1的parent属性。
• 6、按顺序更新g、p的高度
• 7、整棵树都恢复平衡

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

image.png

• 添加的节点在祖父节点的left-right，情况为LR。
• LR需要先对p进行左旋转，然后对g进行右旋转

• 1、针对p、n、T2来说属于RR，所以对节点p进行左旋转
• 2、旋转后属于LL情况，所以对节点g进行右旋转。

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

image.png

5.1.5、添加之后的恢复

上面已经讲解了添加之后失衡的四种情况，下面看下代码的具体实现。
由于AVL树也是二叉搜索树，所以继承关系如下：

image.png

public class AVLTree<E> extends BST<E> {
}

由于添加逻辑是在BST中实现的，所以在BST中定义方法afterAdd(root);

// 添加元素
public void add(E element) {
    // 由于二叉搜索树添加的元素不能为null
    elementNotNullCheck(element);

    // root等于null 第一次添加
    if (root == null) {
        root = createNode(element, null);
        afterAdd(root);
        size++;
        return;
    }
    // 非第一次添加 元素添加的步骤
    // 1、找到要添加节点的parent节点
    Node<E> node = root;
    Node<E> parent = root;
    int cmp = 0;
    while (node != null) {
        cmp = compare(element, node.element);
        parent = node;
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else {
            // 当元素的值相等时进行覆盖
            node.element = element;
            return;
        }
    }
    // 2、创建新的节点
    Node<E> newNode = createNode(element, parent);
    // 3、该节点是parent的左子节点还是右子节点
    if (cmp > 0) {
        parent.right = newNode;
    } else if (cmp < 0) {
        parent.left = newNode;
    }
    afterAdd(newNode);
    size++;
}

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

/**
 * @param node 新添加的节点
 */
protected void afterAdd(Node<E> node) {

}

需要在第一次添加根节点和添加其他节点时调用方法afterAdd()，具体的实现在AVLTree类中。

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

@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) { // 平衡
            // 更新高度
            updateHeight(node);
        } else { // 失衡
            // 恢复平衡
            rebalance(node);
                        break;
        }
    }
}

由于添加节点只会导致祖父节点失衡，父节点和非祖父节点不会失衡，所以我们需要找到最先失衡的祖父节点，并对其进行旋转，使得整棵树都恢复平衡。
判断节点是否失衡，就需要判断节点的左右子树的高度，所以需要在Node中增加高度属性，但是height属性只是AVLTree使用的，所以在AVLTree中定义一个AVLNode继承Node，并在其中定义height属性。并在其中添加判断是否失衡的方法isBalanced(node)

public static class AVLNode<E> extends Node<E> {
    private int height ;
    // 判断是否失衡
    public boolean isBalanced() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        return Math.abs(leftHeight - rightHeight) < 2;
    }
}

但是此时高度属性还没有设置，所以此时调用isBalanced()并没有任何意义。我们知道新添加的节点一定是叶子节点，所以可以将AVLNode中的属性height默认设置为1。
然后调用isBalanced()方法判断节点是否失衡，如果是平衡的则调用updateHeight(node)进行更新高度(这样操作就避免了使用递归来计算高度)，否则执行恢复平衡的操作（恢复平衡后再次更新高度）。这样以来就能做到所有节点的高度都被设置了。*

public static class AVLNode<E> extends Node<E> {
    private int height ;
    //.....
    public void updateHeight() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        height = 1 + Math.max(leftHeight, rightHeight);
    }
}

恢复平衡操作rebalance()

在这里我们需要判断LL、RR、RL、LR四种情况。

/**
 * 恢复平衡
 * 
 * @param grand 高度最低的那个祖父节点
 */
private void rebalance(Node<E> grand) {
    // 进行旋转处理：LL、RR、LR、RL
    /**
     * 那么如何找到parent和node节点呢? 其实parent节点就是祖父节点左右子树中高度较高的子树的根节点
     * node节点是parent节点左右子树中高度较高的子树的根节点
     */
    Node<E> parent = getTallerChildNode(grand);
    Node<E> node = getTallerChildNode(parent);
    // 由于添加之后失衡的一定是祖父节点，所以grand、parent、node一定不会null。
    if (parent == grand.left) { // L
        if (node == parent.left) { // LL
            // 进行右旋
            rotateRight(grand);
        } else { // LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node == parent.left) {// RL
            rotateRight(parent);
            rotateLeft(grand);
        } else {// RR
            rotateLeft(grand);
        }
    }
}

• 1、rebalance(Node<E> grand)方法接收的节点就是最先失衡的祖父节点grand，那么如何找到parent和node节点？

观察我们上面讲述的四种情况，你会发现parent节点其实就是grand节点左右子树中高度较高的子树的根节点。
node节点其实就是parent节点左右子树中高度较高的子树的根节点。而且grand、node、parent节点不可能为空的。

获取较高的子树的根节点

public static class AVLNode<E> extends Node<E> {
    //.....

    public AVLNode<E> getTallerChildNode() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        if (leftHeight > rightHeight)
            return (AVLNode<E>) left;
        if (leftHeight < rightHeight)
            return (AVLNode<E>) right;
        /**
         * 在leftHeight == rightHeight时，如果节点是父节点的左子节点，那么返回左子树 反之则返回父节点的右子节点
         * 注意：在左右子树高度相等时，返回左右子树都是可以的，看自己怎么设计
         */
        return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
    }
}

• 2、需要注意的是进行左旋、右旋的节点：

• LL、RR情况下，旋转的是grand节点
• RL、LR情况下，先旋转的是parent节点，然后再旋转grand节点

rotateLeft()方法的实现

/**
 * 左旋
 * 
 * @param grand 要旋转的节点
 */
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;

    grand.right = child;
    parent.left = grand;

    // 让parent成为根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // 根节点
        root = parent;
    }

    // 设置grand的parent
    grand.parent = parent;
    // 设置child的parent
    if (child != null)
        child.parent = grand;

    // 设置高度
    updateHeight(grand);
    updateHeight(parent);
}

rotateLeft(Node<E> grand)接收的可能是parent节点或grand节点，那在方法中如何得到对应节点的parent节点，既然是左旋，那么就可以参照RR情况。所以可以得到

Node<E> parent = grand.right;

具体旋转的逻辑见上面方法，注释的很清晰。

rotateRight()方法的实现

/**
 * 右旋
 * 
 * @param grand 要旋转的节点
 */
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;

    grand.left = child;
    parent.right = grand;

    // 让parent成为子树的根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // 根节点
        root = parent;
    }
    // 更新grand的parent
    grand.parent = parent;
    // 更新child的parent
    if (child != null)
        child.parent = grand;

    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

可以发现左旋和右旋，在旋转之后的都是将parent变成子树的根节点，维护grand、parent、child的parent属性、先更新grand的高度、再更新parent的高度。

5.2、统一添加节点失衡的所有情况

image.png

从上图可以看到，无论哪种情况下的最终形态都是一样的：

d作为根节点，其左右子树的根节点都是b、f；
b的左右子树为a、c，f的左右子树为e、g；
所以可以对上述四种情形进行统一处理。

/**
 * 对4种情形进行统一处理
 * @param grand
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = getTallerChildNode(grand);
    Node<E> node = getTallerChildNode(parent);
    if (parent == grand.left) { // L
        if (node == parent.left) { // LL
            rotate(grand, node, parent, grand, node.left, node.right, parent.right, grand.right);
        } else { // LR
            rotate(grand, parent, node, grand, parent.left, node.left, node.right, grand.right);
        }
    } else { // R
        if (node == parent.left) {// RL
            rotate(grand, grand, node, parent, grand.left, node.left, node.right, parent.right);
        } else {// RR
            rotate(grand, grand, parent, node, grand.left, parent.left, node.left, node.right);
        }
    }
}

private void rotate(
        Node<E> r,// 子树的根节点
        Node<E> b,Node<E> d,Node<E> f,
        Node<E> a,Node<E> c,Node<E> e,Node<E> g
        ) {
    
    //将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.parent=d;
    b.right=c;
    if(c!=null)
        c.parent=b;
    
    
    // e-f
    f.parent=d;
    f.left=e;
    if(e!=null)
        e.parent=f;
    
    //b d f
    d.left=b;
    d.right=f;
    
    updateHeight(f);
    updateHeight(b);
    updateHeight(d);
}

5.3、删除导致的失衡

image.png
删除上图中的节点16，会导致节点15或节点11失衡。
删除节点，可能会导致父节点或祖父节点失衡，但是只会有1个节点会失衡。

删除导致失衡肯定是删除的节点所在的子树的高度较低，而高度较高的子树并没有变化，所以不会影响其他节点。

5.3.1、LL-右旋转(单旋)

image.png

• 左图是删除前的状态
• 右图是右旋后的结果
• 红色部分是要删除的节点
• 绿色部分可能不存在
  如果删除红色部分后，发现节点g的平衡因子变成了2，节点g失衡，进行右旋，如果绿色部分不存在，发现右旋之后，整个子树的高度减少了1，这样就会导致更高层的祖先节点失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡。。。。
  极端情况下，如果所有祖先节点都需要进行恢复平衡的操作，共O(logn)次调整。

5.3.2、RR-左旋转(单旋)

image.png

5.3.3、LR-RR左旋转，LL右旋转（双旋）

image.png

5.3.4、RL-LL右旋转，RR左旋转（双旋）

image.png

5.4、删除之后的修复

经过上面的分析可知，删除之后的修复和添加后的修复是相同的，只不过添加后的修复只需要进行一次恢复平衡即可，而删除后的修复在极端情况下可能需要进行logn次的平衡操作。
删除操作是在BST中实现的，同样需要在其中创建一个afterRemove(node)方法，然后在AVLTree中进行具体实现。
BST##remove()

private void remove(Node<E> node) {
    if (node == null)
        return;
    // 删除度为2的节点
    if (node.hasTwoChildren()) {
        // 找到前驱节点
        Node<E> precurNode = precursor(node);
        // 用前驱节点的值覆盖要删除节点的值
        node.element = precurNode.element;
        // 删除前驱节点
        node = precurNode;
    }

    // 删除的node节点的度为1或0
    Node<E> child = node.left != null ? node.left : node.right;
    if (child != null) { // 度为1的节点
        // 使用子节点替代要删除节点的位置
        child.parent = node.parent;
        if (node.parent == null)
            root = child;
        else if (node == node.parent.left)
            node.parent.left = child;
        else if (node == node.parent.right)
            node.parent.right = child;
    } // 删除叶子节点
    else if (node.parent == null)
        root = null;
    else if (node == node.parent.left)
        node.parent.left = null;
    else if (node == node.parent.right)
        node.parent.right = null;
    size--;
    afterRemove(node);
}

AVLTree中的具体实现

@Override
protected void afterRemove(Node<E> node) {
    while ((node=node.parent)!=null) {
        if (isBalanced(node)) { // 平衡
            // 更新高度
            updateHeight(node);
        } else { // 失衡
            // 恢复平衡
            rebalance(node);
        }
    }
}

5.5、总结

5.5.1、添加

• 1、添加可能会导致所有祖父节点失衡
• 2、只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡了

5.5.2、删除

• 1、删除可能会导致父节点或祖父节点失衡，只有一个节点会失衡
• 2、恢复平衡后可能会导致更高层祖父节点失衡，最多需要调整logn次。

5.5.3、时间复杂度

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