数据结构之“艾薇儿”树

封面画师：ツチヤ     封面ID：79898339

本文参考视频：小马哥教育(SEEMYGO) 2019 年 恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

0. 前言

二叉搜索树的复杂度分析

如果是按照 7、4、9、2、5、8、11 的顺序添加节点：

如果我们想要添加一个节点 12，那么我们需要先和根节点 7 进行比较，然后和其子节点 8 进行比较，最后在和 8 的子节点 11 进行比较，确定插入位置。同理，如果我们要添加节点 1 或 6 也是同样的道理。

不难发现，二叉搜索树的复杂度与元素（节点）的个数无关，与树的高度有关。

因此，上述二叉搜索树（满二叉树）的复杂度为： O(h) = O(logn)，可以看出二叉搜索树的添加、查找效率很高。

❗但是！

如果我们更换添加节点的顺序，将添加节点的顺序变成从小到大添加：

这时，这棵二叉搜索树的复杂度为： O(h) = O(n)，二叉搜索树退化成 链表 。

---

我们发现，当二叉树的节点数量 n 较大时，两者的性能差异比较大。

比如 n = 1000000 时，二叉搜索树的最低高度是 20，但最大高度是 1000000，这两种情况很极端，会导致其搜索效率出现很大的差别。

---

添加节点顺序不当可能会造成二叉搜索树退化成链表，删除节点时，也可能导致二叉搜索树退化成链表。比如我删除最开始的二叉树中的 2、8、11、9 四个节点时：

综上可知，添加、删除节点时，都可能会导致二叉搜索树退化成链表。

那么，我们有什么办法防止二叉搜索树退化成链表吗？ 让添加、删除、搜索的复杂度维持在 O(logn)。

这时，又一个「天降猛男」登场了 —— 平衡二叉搜索树。💪

1 平衡二叉搜索树

1.1 平衡

平衡（Balance）： 当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度越低）。

上图所示的二叉树越来越平衡。

这里又可以引入 理想平衡 的概念：最理想的平衡，就是像完全二叉树、满二叉树一样，高度是最小的。

1.2 改进二叉搜索树

前面已经分析：节点的添加、删除可能会导致 BST 退化成链表，但是因为节点的添加、删除是无限制的，基本是随机的，因此我们并不能在节点的添加和删除上天机限制。

但是我们依然有改进方案： 在节点的添加、删除之后，想办法让二叉搜索树恢复平衡（减小树的高度）。

我们还可以继续调整节点的位置，并完全可以达到理想平衡，但是付出的代价可能会比较大。由于增加了调整的次数，反而会增加时间复杂度，甚至超过链表的时间复杂度而得不偿失。

总的来说，我们不能一昧地调整，我们 用尽量少的调整次数让BST达到适度的平衡即可 。

一棵达到适度平衡的 BST 可以称之为： 平衡二叉搜索树。

1.3 平衡二叉搜索树

平衡二叉搜索树，Balanced Binary Search Tree，简称：BBST。经典的平衡二叉搜索树有：

• AVL 树
  • 在 Windows NT 内核中广泛使用
• 红黑树
  • C++ STL （比如 map、set 等）
  • Java 中 的 TreeMap、TreeSet、HashMap、HashSet
  • Linux 的进程调度
  • Nginx 的 timer 管理

一般也称它们为： 自平衡的二叉搜索树 （Self-balancing Binary Search Tree）

2. AVL 树

2.1 基本概念

AVL 树是最早发明的自平衡二叉搜索树，那么 AVL 是什么意思？ AVL 取名于两位发明者的名字：

G. M. Adelson-Velsky 和 E. M. Landis，这是两位来自苏联的科学家（「精苏」狂喜 😜）

AVL？ 艾薇儿？ 艾薇儿树？ 嗯！ 可以！😂

平衡因子

平衡因子（Balance Factor）：某节点的 左右子树高度差 （左 子树的高度减 右 子树的高度）。

比如：

对于 AVL 树来说，AVL 树每个节点的平衡因子只可能是 1、0、-1（绝对值小于等于 1，如果超过 1，称之为「失衡」），换句话说，AVL树每个节点的左右子树高度差不超过 1 。搜索、添加、删除的时间复杂度是 O(logn)。

AVL 树示例：

2.2 代码重构

为了便于代码复用，我们可以对编写的二叉搜索树代码进行重构，即：编写一个 BinaryTree 类，用来表示所有二叉树都具有的一些公共方法和成员变量；将原来表示二叉搜索树的类 BinarySearchTree 改写为 BST，同时使用 BST 类继承 BinaryTree。

BinaryTree 中包含的一些方法和成员变量（省略方法的实现，具体实现参考 二叉搜索树 中给出的代码）：

package com.yang.Tree;
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree<E>{
    // 使用访问修饰符 protected 让不同包的子类可以访问这个变量
    protected int size;   // 节点个数
    protected Node<E> root; //根节点
    public int size() {
        return size;
    }

    public boolean isEmpty() {...}

    public void clear() {...}

    // 前序
    public void preorder(Visitor<E> visitor) {...}

    private void preorder(Node<E> node,Visitor<E> visitor) {...}

    // 中序
    public void inorder(Visitor<E> visitor) {...}

    private void inorder(Node<E> node, Visitor<E> visitor) {...}

    // 后序
    public void postorder(Visitor<E> visitor) {...}

    private void postorder(Node<E> node, Visitor<E> visitor) {...}

    public void levelOrder(Visitor<E> visitor) {...}

    public boolean isComplete() {...}

    public int height() {...}

    // 获取整棵树的高度
    public int height2() {...}

    // 获取某一节点的高度
    private int height(Node<E> node) {...}

    protected Node<E> predecessor(Node<E> node) {...}

    protected Node<E> successor(Node<E> node) {...}

    public static abstract class Visitor<E> {
        // 遍历终止标志 true：终止 false：全遍历
        boolean stop;

        // 如果返回true，表示停止遍历
        abstract boolean visit(E element);
    }
    // 一个节点就是一个Node
    protected static class Node<E> {...}
}

BST 中包含的一些方法和成员变量（省略方法的实现，具体实现参考 二叉搜索树 中给出的代码）：

package com.yang.Tree;
import java.util.Comparator;
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator;

    public BST() {
        this(null);
    }

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public void add(E element) {...}

    // 删除某一元素
    public void remove(E element) {...}

    public boolean contains(E element) {...}

    // 删除某一节点
    private void remove(Node<E> node) {...}

    // 根据元素找寻节点
    private Node<E> node(E element) {...}

    /**
     * @return 返回值等于0，表示e1和e2相等；返回值大于0，表示e1大于e2；返回值小于0，表示e1小于e2
     */
    private int compare(E e1, E e2) {...}

    // 节点空值检查
    private void elementNotNullCheck(E element) {...}
}

---

AVL 树是自平衡二叉搜索树，是一种特殊的二叉搜索树，因此在编写 AVL 树的代码时，我们可以让表示 AVL 树的类 AVLTree 继承 BST。可以初步得到以下代码：

public class AVLTree<E> extends BST<E>{
    
    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }
}

2.3 添加失衡

比如向下面这棵子树中添加元素 13：

可以看到，原本这棵子树是平衡的，添加元素 13 后而变成了失衡。最坏情况下，甚至可能导致添加节点的 所有祖先节点 都失衡，但添加节点的父节点（节点 12）、非祖先节点（节点 4、6、8）不会失衡。

那么怎么解决因为添加而导致的失衡呢？ 需要使用到旋转。 👇

2.4 添加旋转

2.4.1 LL - 右旋转（单旋）

右旋转示意图：

右旋转动态图：

在上述示意图中，n 表示节点， p（parent）表示父节点，g（grandparent）表示祖父节点；T0、T1、T2、T3 分别表示节点下的子树，其中 T0、T1 的高度相等，T2、T3 的高度相等。

最开始时，整棵子树是平衡的，当我们在 T0 子树出处插入一个节点（图中红色矩形）时，节点 g 处于失衡状态，我们需要对其进行操作，让它恢复平衡。

这时，需要对 g 用到 右旋转 。右旋转步骤如下：

• g.left = p.right
• p.right = g
• 让 p 成为这棵子树的根节点
• 旋转后仍然是一棵二叉搜索树： T0 < n < T1 < p < T2 < g < T3
• 整棵树都达到平衡

旋转结果如上图的右侧部分。明明是右旋转，为什么要叫LL呢？因为失去平衡的节点是由其左子树的左子树下的节点造成的。

并不是旋转了就完事了，我们还需要注意维护的内容：

• T2、p、g 的 parent 属性
• 先后 更新 g、p 的高度

2.4.2 RR - 左旋转（单旋）

左旋转示意图：

左旋转动态图：

在上述示意图中，n 表示节点， p（parent）表示父节点，g（grandparent）表示祖父节点；T0、T1、T2、T3 分别表示节点下的子树，其中 T0、T1 的高度相等，T2、T3 的高度相等。

最开始时，整棵子树是平衡的，当我们在 T3 子树出处插入一个节点（图中红色矩形）时，节点 g 处于失衡状态，我们需要对其进行操作，让它恢复平衡。

这时，需要对 g 用到 左旋转 。左旋转步骤如下：

• g.right = p.left
• p.left = g
• 让 p 成为这棵子树的根节点
• 仍然是一棵二叉搜索树： T0 < g < T1 < p < T2 < n < T3
• 整棵树都达到平衡

旋转结果如上图的右侧部分。

并不是旋转了就完事了，我们还需要注意维护的内容：

• T1、p、g 的 parent 属性
• 先后 更新 g、p 的高度

2.4.3 双旋

LR

遇上 LR 的情况（向 T1、T2 处添加节点），需要先对 p 进行 RR 左旋转，再对 g 进行 LL 右旋转（双旋）。过程如下：

RL

遇上 RL 的情况（向 T1、T2 处添加节点），需要先对 p 进行 LL 右旋转，再对 g 进行 RR 左旋转（双旋）。过程如下：

2.5 计算平衡因子

由于 AVL 树的特性，我们在添加元素时需要计算某一节点的平衡因子，并对失衡节点进行旋转，让其再次达到平衡状态，而这一步骤的前提就是需要计算平衡因子。

平衡因子就是某一节点 左子树的高度减去右子树的高度 ，明白了这个道理后就很好计算了。

需要找到一种表示节点高度的方法，首先想到的就是在 BinaryTree 类中的静态嵌套类 Node 中添加表示高度的成员变量 height。但是这么做有一个问题，如果我创建的不是 AVL 树，只是普通的 BST，那么这个时候也会开辟一段内存空间用来存储 height，而 BST 中并没有用到它，造成空间被白白浪费。

我们可以在 AVLTree 类中编写表示 AVL 树自己节点的类 AVLNode，让这个类继承 Node 并添加成员变量 height，这样就可以做到创建 AVL 树或创建 BST 时，都有满足自身要求的节点。最后，就可以根据 height 来计算平衡因子并判断某一节点是否平衡：

// 判断节点是否平衡
private boolean isBalanced(Node<E> node){
    return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
}

private static class AVLNode<E> extends Node<E> {
    // 新添加节点是叶子节点，高度一定是 1 
    int height = 1;

    public AVLNode(E element, Node<E> parent) {
        super(element, parent);
    }

    // 获取平衡因子
    public int balanceFactor() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        return leftHeight - rightHeight;
    }
}

---

AVLTree 继承了 BST，它俩 使用相同的节点添加方法 ，但是我们知道 AVL 树和 BST 添加的节点是不一样的，AVL 树添加的节点中有 height 表示高度，而 BST 是没有的。因为这个差异，我们需要对代码进行修改：

先在 BinaryTree 中编写节点添加方法：

// 访问修饰符 protected 让该类的子类可以使用
protected Node<E> createNode(E element, Node<E> parent){
    return new Node<>(element, parent);
}

修改 BST 中的添加方法，使用 createNode() 方法创建节点，同时编写 afterAdd() 方法（该方法为空，在 AVLTree 进行重写）表示添加节点后需要做的调整：

public void add(E element) {
    elementNotNullCheck(element);
    // 添加第一个节点 （根节点）
    if (root == null) {
        // 使用新创建节点方法
        root = createNode(element,null);
        size++;
        // 添加节点后的处理 传入参数类型为Node
        afterAdd(root);
        return;
    }
    // 添加的不是第一个节点 ---> 找到插入节点的父节点
    Node<E> parent = root;
    Node<E> node = 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;
        }
    }
    // 看看插入到父节点的哪个位置
    Node<E> newNode = createNode(element, parent); // 使用新创建节点方法
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    // 添加节点后的处理 传入参数类型为Node
    afterAdd(newNode);
}

// 添加节点之后的调整 node是新添加的节点
// 在其他代码中实现
protected void afterAdd(Node<E> node){ }

最后在 AVLTree 中重写 createNode() 方法：

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

2.6 更新高度

前一步需要计算平衡因子，但是计算平衡因子需要某一节点左右子树的高度差，换句话说就是需要左右子树的高度。在前一步中，我们仅仅是设置了表示高度的成员变量 height，当我们给 AVL 树添加节点后，需要更新其父节点（祖先节点）的高度以便计算平衡因子。

我们可以在 AVLNode 内部类中编写更新 AVL 树节点高度的方法 updateHeight()：

private static class AVLNode<E> extends Node<E> {
      ......
    
    // 更新节点高度
    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);
    }
}

在前一节中，我们计划编写一个 afterAdd(Node<E> node) 方法，用于表示添加节点后需要做出的调整，同时该方法传入参数类型为 Node，而在 AVLTree 类中节点类型为 AVLNode，我们在 afterAdd(Node<E> node) 方法中需要对参数 node 进行强制类型转换，为了避免大量的类型转换代码，我们可以将节点高度更新的方法再次进行封装。在 AVLTree 类中再次封装节点高度更新方法：

// 节点高度更新封装
private void updateHeight(Node<E> node){
    ((AVLNode<E>) node).updateHeight();
}

2.7 旋转准备

接下来就是旋转前的最后准备了，前面已经分析过两大种单旋—— LL 和 RR （双旋由单旋组合而成），而旋转的重点就是要知道到底是哪种失衡，因此我们最后的准备就是判断是哪种情况导致的失衡。

在此之前，我们需要在 AVLTree 类中重写 afterAdd(Node<E> node)，在这个方法中编写添加节点后需要做的操作。

关于 afterAdd(Node<E> node)，有以下几点需要分析：

• 参数 node 表示新添加的节点
• 这个方法主要用来 更新高度 和 修复平衡
• 我们可以沿着插入节点的父节点一直向上寻找，查看有无失衡或直到根节点
• 当前节点处于平衡状态时，我们需要更新它的高度（因为插入了新节点，新节点的祖先节点高度会发生改变）
• 当前节点处于失衡状态时，我们需要让其恢复平衡，最后跳出循环

@Override
protected void afterAdd(Node<E> node) { // node是新添加的节点
    // 平衡修复 --> 对最低失衡节点进行修复
    // 可能不存在失衡节点 一路向上找即可
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {// 当node平衡时
            // 更新高度
            updateHeight(node);
        } else {// 当node不平衡时
            // 恢复平衡
            rebalance(node);
            // 整棵树恢复平衡后跳出循环
            break;
        }
    }
}

在上述代码中，更新节点高度的方法 updateHeight() 已经编写好了，但是恢复平衡的方法 rebalance() 还没有编写，接下来就是他的主场！ ​ 😏

首先我们知道，节点失衡是一系列的，所谓一系列就是指当一个节点发生失衡后，最坏可能其祖先节点都失衡。因此，要想恢复平衡就是要针对高度最低的失衡点进行修复。在上述 afterAdd() 代码中已经成功获取到了高度最低的失衡点：

接下来要做的就是针对这个节点判断失衡方式并进行恢复。判断节点失衡反思是 针对失衡点的子节点进行判断 的，如果失衡节点的左子节点的左子节点位置插入了节点，并导致 AVL 树失衡，我们称这种失衡方式为 LL。同理可得其他三种失衡方式。

还需要判断失衡点的子节点是左子节点还是右子节点，而之所以失衡是因为左右子树高度差大于了 1，因此我们判断失衡方式是需要获取当前节点高度最高的子节点，因为高度最高的子节点（或其子节点）就是插入节点的位置。

在获取高度最高的子节点时，需要比较左右子树的高度，比较结果有三种： 大于、小于、等于。大于和小于很好处理，而针对等于的情况可以选择左子节点返回，也可以选择右子节点返回，我们规定返回当前节点的位置。即：如果当前节点是其父节点的左节点，那么就返回左子节点；反之返回右子节点。

针对这种情况，我们在 BinaryTree 类中的静态嵌套类 Node 中添加方法，以 判断当前节点相对于父节点的位置 ：

// 一个节点就是一个Node
protected static class Node<E> {
    ......

    // 判断当前节点是否是其父节点的左子节点
    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }

    // 判断当前节点是否是其父节点的右子节点
    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }
}

然后在 AVLTree 类中的静态嵌套类 AVLNode 中编写 获取当前节点高度最高的子节点 的方法：

private static class AVLNode<E> extends Node<E> {
    ......

    // 获取当前节点高度最高的子节点
    public Node<E> tallerChild() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        if (leftHeight > rightHeight) return left;
        if (leftHeight < rightHeight) return right;
        return isLeftChild() ? left : right;
    }
}

最后在 AVLTree 类中编写恢复平衡的方法 rebalance(Node<E> grand)：

/**
* 恢复平衡
* @param grand 高度最低的不平衡节点
*/
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            rotateRight(grand);
        } else { // LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node.isLeftChild()){ // RL
            rotateRight(parent);
            rotateLeft(grand);
        } else { // RR
            rotateLeft(grand);
        }
    }
}

---

上述代码中右旋方法 rotateRight(Node<E> node) 和左旋方法 rotateLeft(Node<E> node) 尚未编写，我们在下节 进行重点分析！

// 左旋转
private void rotateLeft(Node<E> node){
    ......
}

// 右旋转
private void rotateRight(Node<E> node){
    ......
}

2.8 实现旋转

在 2.4 旋转 一节中已经分析了旋转的基本原理，接下来就是要使用代码实现旋转。

代码内容分为两部分：

• 旋转逻辑
• 旋转后的处理 （更新父节点、更新高度）

通过比较左旋转和右旋转的旋转逻辑我们可以发现，两种旋转方式除了旋转逻辑之外，旋转后的处理是类似（或者说相同的），为了减少重复代码，我们可以将旋转后的处理操作代码封装成一个方法： afterRotate()，即：

private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child){
    // 让 parent 成为根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()){
        grand.parent.left = parent;
    } else if (grand.isRightChild()){
        grand.parent.right = parent;
    } else { // 没有父节点， grand是根节点
        root = parent;
    }
    // 更新其他节点的父节点
    if (child != null){
        child.parent = grand;
    }
    grand.parent = parent;
    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

左旋转与右旋转逻辑：

// 左旋转
private void rotateLeft(Node<E> grand){
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    // 旋转
    grand.right = child;
    parent.left = grand;
    // 旋转后
    afterRotate(grand,parent,child);
}

// 右旋转
private void rotateRight(Node<E> grand){
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    // 旋转
    grand.left = child;
    parent.right = grand;
    // 旋转后
    afterRotate(grand,parent,child);
}

2.9 旋转统一

在实现旋转时，我们编写了右旋转 rotateRight(Node<E> grand) 和左旋转 rotateLeft(Node<E> grand) 对应的方法，但是通过上面的图可以发现旋转是可以使用一个方法来完成的。

a、c、e、g 表示子树，可以为空；b、d、f 表示节点。它们的高度顺序为： a < b < c < d < e < f < g。 四种情况下最终得到的旋转后的子树都很类似，仅仅是插入节点位置不同。

利用这个原理，可以编写以下用来统一旋转方法 rotate() 的代码：

private void rotate(
    Node<E> r, // 根节点
    Node<E> a, Node<E> b, Node<E> c,
    Node<E> d,
    Node<E> e, Node<E> f, 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;
    }

    // a - b - c
    b.left = a;
    if (a != null) {
        a.parent = b;
    }
    b.right = c;
    if (c != null) {
        c.parent = b;
    }
    updateHeight(b);

    // e - f - g
    f.left = e;
    if (e != null) {
        e.parent = f;
    }
    f.right = g;
    if (g != null) {
        g.parent = f;
    }
    updateHeight(f);

    // b - d - f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}

然后改写一下恢复平衡的方法 rebalance()：

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

---

我们从最开始给出的示意图可以看到，a、g 在旋转前后是没有改变的，针对 AVL 树，我们是可以不用处理这两个地方的。但为了泛用，我依旧将它们进行处理。

2.1 0 删除失衡

原本这棵子树是平衡的，但当我们删除这棵子树中的元素 16 时，可能会导致 父节点 或 祖先节点 失衡（只有一个节点会失衡）， 其他节点都不可能失衡 。

针对父节点失衡：删除节点后，删除节点的父节点可能失衡，也可能不失衡。

假设节点 15 的左子树为空， 右子节点只有一个 16，当我们删除 16 时，虽然节点 15 的高度发生了改变，但是并没有失衡。

针对上述子树不做任何变化，直接删除节点 16，那么节点 15 会失衡，且只有节点 15 会失衡。因为删除节点 16 后，节点 15 的平衡因子发生了变化，但是其高度并没有变化，因此不会影响到其他节点。

同时，我们还可以得出一个结论： 如果删除一个节点导致其父节点失衡，那么删除节点一定位于其父节点高度较小的子树中 。 除此之外，节点恢复平衡后，还可能导致更高层祖先节点失衡。

2.1 1 删除旋转

LL - 右旋转（单旋）

原本子树是平衡的，当我们删除 红色节点 后，子树处于失衡状态，且是节点 g 处于失衡，因此需要进行恢复平衡。进一步可以得出，失衡的原因是 LL，因此进行右旋转即可。

旋转后整棵子树恢复平衡了，但是并不代表整棵树恢复了平衡。如果旋转前后子树的高度发生了变化，即： 绿色节点不存在，这棵子树的高度减一。未删除节点前，恰逢这棵子树的父节点的另外一棵子树的高度比这棵子树大 1，如果这时候绿色节点不存在，那么导致高度差成为 2，这棵子树的父节点失衡。

因此，如果绿色节点不存在，更高层的祖先节点可能也会失衡，需要再次恢复平衡，然后有可能导致更高层的祖先节点失衡…

极端情况下，所有祖先节点都需要进行恢复平衡，共 O(logn) 次调整。

RR - 左旋转（单旋）

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

遇上 LR 的情况，需要先对 p 进行 RR 左旋转，再对 g 进行 LL 右旋转（双旋）。过程如下：

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

遇上 RL 的情况，需要先对 p 进行 LL 右旋转，再对 g 进行 RR 左旋转（双旋）。过程如下：

---

绿色节点为删除节点后子树高度变化的标志，如果绿色节点不存在，那么整棵子树的高度减一，极有可能导致这棵子树的父节点失衡，然后需要再次恢复平衡，然后又可能导致这棵子树父节点的父节点（祖先节点）失衡，而陷入一个循环…

2.1 2 实现删除

与添加节点类似，我们同样需要在 BST 类中添加一个方法 afterRemove(Node<E> node)，表示删除节点后需要进行的调整。

/**
*  删除节点之后的调整
*  node是被删除的节点
*  或者用以取代被删除节点的子节点（当被删除节点的度为 1 ，红黑树中使用）
* */
// 在其他代码中实现
protected void afterRemove(Node<E> node){ }
// 删除某一元素
public void remove(E element) {
    remove(node(element));
}

afterRemove(Node<E> node) 在 BST 类中为空，表明该方法在二叉搜索树中的删除方法不用被实现，在需要进行调整的地方进行重写（比如：AVL 树中的节点删除操作）。

然后修改 BST 类中删除节点的方法 remove(Node<E> node)，在这个方法中 合适的位置 添加 afterRemove() 方法：

// 删除某一节点
private void remove(Node<E> node) {
    if (node == null) return;
    size--;
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继节点
        Node<E> s = successor(node);
        // 用后继节点的值覆盖被删除节点的值
        node.element = s.element;
        // 变量node指向其后继节点，等待后续删除
        node = s;
    }
    // 删除node节点（node的度必然为1或0）
    Node<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {   // node度为1
        // 更改parent
        replacement.parent = node.parent;
        // 更改noded的parent的left、right的指向
        if (node.parent == null) { // node度为1，且为根节点
            root = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }

        // 被删除的节点
        afterRemove(node);
    } else if (node.parent == null) {     // node度为0，是叶子节点，并且是根节点
        root = null;
        // 被删除的节点
        afterRemove(node);
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
        // 被删除的节点
        afterRemove(node);
    }
}

那么什么地方是合适的位置？我们知道在 BST 中，删除节点有时并不是真的删除（地址）了需要被删除的节点，可能删除的是它的前驱或后继节点，然后还需要进行覆盖。覆盖时会改变节点的左右子树、父节点，afterRemove() 方法就可以放在改变后，表示在节点真正被删除后对完整的树进行平衡恢复，而不是一删除就进行恢复。

PS：在 AVL 树中，我们可以看出 afterRemove() 方法都是在执行完覆盖调用的，那么可以将它直接写在最后吗？答案是可以的，但是为了后续 红黑树 的实现，不建议这样做，因为红黑树的删除后的调整在不同的位置执行不同。

添加失衡和删除失衡所用的旋转逻辑是一样，代码是一样，可以直接复用。

最后在 AVLTree 中重写 afterRemove() 方法：

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

这样，删除的实现就完成了！ 🎉 🎊

Q&A

• afterRemove() 方法与 afterAdd() 方法仅是一个 break 的差别，这是为什么？

两者找寻失衡节点、更新高度、恢复平衡的逻辑是一样的，因此两者的打码大致一样。添加失衡只需要修复高度最低的失衡节点就能让整棵树恢复平衡，因此使用 break 跳出循环；但对于删除节点是不行的，因为节点恢复平衡后，还可能导致更高层的「祖宗」节点失衡，因此需要一直遍历，直到根节点，故不使用 break。

• 在 afterRemove() 方法中使用 node = node.parent 进行循环遍历不会出现空指针异常吗？

不会出现。从 BST 的节点删除方法中可以看到：我们虽然删除了选中的节点，但只是取消了其他节点对被删除节点的应用，而被删除节点对其父节点的引用并没有取消，因此是不会出现空指针异常的。

2.1 3 AVL 树总结

添加

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

删除

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

平均时间复杂度

• 搜索： O(logn)
• 添加： O(logn)，仅需 O(1)次的旋转操作（并不是说只操作 1 次，而是说旋转次数是常数级别的）
• 删除： O(logn)，最多需要 O(logn)次的旋转操作