数据结构之红黑树

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

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

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

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

0. 初始红黑树

红黑树（Red Black Tree），一种自平衡二叉搜索树，旧时称为：平衡二叉B树（Symmetric Binary Tree）。红黑树必须满足以下 五条 性质：

• 节点是 RED 或者 BLACK
• 根节点是 BLACK
• 叶子节点 （外部节点、空节点【假想的】）都是 BLACK
• RED 节点的子节点都是 BLACK
  • RED 节点的父节点（parent）都是 BLACK
  • 从根节点到叶子结点的所有路径上不能有2个连续的 RED 节点
• 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

使用上述五条性质就可以保证红黑树平衡！ 😲

1. B 树

1.1 初识B树

B树（B-tree、B-树）是一种平衡的多路搜索树，多用于文件系统、数据库的实现。

示意图：

观察上述B树，发现了哪些特点？

• 1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
• 拥有二叉搜索树的一些性质（子节点的位置与父节点值大小有关）
• 平衡，每个节点的所有子树高度一致
• 比较矮

上面示意图的几阶是什么意思？

表示一个节点中最多拥有 m （m表示阶数）个子节点。

附赠一张自己做的表情包：

1.2 B树的性质

这里指的是 m 阶B树的性质（m >= 2）：

假设一个节点存储的元素个数为 x ：

• 根节点： 1 <= x <= m - 1

• 非根节点： ┌ m / 2 ┐ - 1 <= x <= m - 1

• 如果有子节点，子节点个数 y = x + 1

  • 根节点： 2 <= y <= m
  • 非根节点： ┌ m / 2 ┐ <= y <= m （┌ ┐ 表示向上取整）

比如：

m = 3，2 <= y <= 3，因此可以成为(2,3)树、2-3树

m = 4，2 <= y <= 4，因此可以成为(2,4)树、2-3-4树

m = 5，3 <= y <= 5，因此可以成为(3,5)树、3-4-5树

m = 6，3 <= y <= 6，因此可以成为(3,6)树

m = 7，4 <= y <= 7，因此可以成为(4,6)树

如果 m = 2，那么这棵B树就是二叉搜索树。现实中，数据库实现中一般用 200 ~ 300 阶B树。

1.3 B树 VS BST

B树和二叉搜索树在逻辑上是等价的。就是说，将二叉搜索树的一些节点进行合并，就可以得到一棵B树。

多代节点（父子节点、爷父子节点…）合并，可以获得一个超级节点（B树上存储了多个元素的节点）。

• 两代合并的超级节点，最多拥有 4 个子节点（至少是 四阶B树）
• 三代合并的超级节点，最多拥有 8 个子节点（至少是 八阶B树）
• n 代合并的超级节点，最多拥有 2ⁿ 个子节点 （至少是 2ⁿ 阶B树）

m 阶B树，最多需要log₂ m 代合并

1.4 节点添加

节点搜索

B树跟二叉搜索树的搜索类似：

1. 先在节点内部从小到大开始搜索元素
2. 如果命中，搜索结束
3. 如果未命中，再去对应的子节点中搜索元素，重复步骤 1

节点添加

B树新添加的元素必定添加到叶子节点。

比如，假设这是一棵四阶B树，先插入元素 55：

再插入元素 95 ：

又插入元素 98 呢？

由于这是一棵四阶B树，那么最右下角的叶子节点的元素个数将超过限制，这种现象可以称之为： 上溢 （overflow）

1.5 解决上溢

假设这棵B树是五阶的，对这棵B树添加元素，抽象出其中一块子树：

上溢节点的元素个数必然等于 m （m 为B树的阶数）

假设上溢节点最中间元素的位置为 k，将 k 位置的元素向上与父节点合并，将 [0, k - 1]和[k + 1, m - 1] 位置的元素分裂成 2 个子节点：

这两个子节点的元素个数，必然都不会低于最低限制（┌ m / 2 ┐ - 1）

一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决。最极端的情况，有可能一直分裂到根节点。

假设已分裂至根节点，那么则有：

上溢至根节点，是唯一一种能够让B树“长高”的情况。

---

若B树的阶数是偶数阶（记为 m ），那么合并的中间元素位置可以是m/2，也可以是m/2+1，看情况选择就行。

添加

因此，紧跟上述B树的添加，在添加元素 98 后，则有：

然后再依次添加元素 52 、 54后，可得到：

1.6 节点删除

删除叶子节点

如果删除的元素在叶子节点中，直接删除即可 ！

删除非叶子节点

如果删除的元素在非叶子节点中：

• 先找到前驱或者后继元素，覆盖需要被删除的元素值
• 再把前驱或后继元素删除

比如，删除下列B树的 60 元素：

我们发现：

• 非叶子节点的前驱或后继元素，必定在叶子节点中
• 所有上述的删除前驱或后继元素，就是最开始提到的情况：删除的元素在叶子节点中
• 真正的删除元素都是发生在叶子节点中的

1.7 下溢问题

先有一棵下列这样的二叉树：

假设这是一棵五阶B树（即： m = 5），对元素 22 进行删除：

由于叶子节点被删除一个元素后，元素个数可能会低于最低限制（小于了 ┌ m / 2 ┐ - 1 ）

这种现象称为： 下溢 （underflow）

解决下溢

下溢节点的元素数量必然等于 ┌ m / 2 ┐ - 2

如果下溢节点临近的兄弟节点有至少 ┌ m / 2 ┐ 个元素，可以向其借一个元素：

• 将下溢节点的父节点元素 b 插入到下溢节点的 0 位置（最小位置）
• 用兄弟节点的元素 a （最大的元素）替代父节点的元素 b
• 这种操作的本质就是： 旋转

如果下溢节点临近的兄弟节点，只有 ┌ m / 2 ┐ - 1 个元素：

• 将父节点的元素 b 挪下来跟左右节点进行合并
• 合并后的节点元素个数等于 ┌ m / 2 ┐ + ┌ m / 2 ┐ - 2 ，不超过 m - 1
• 这个操作可能会导致父节点下溢，依然按照上述方式进行解决。最坏情况下，下溢现象可能会一直往上传播直到根节点

下溢至根节点，是唯一一种能够让B树“变矮”的情况。

1.8 四阶B树

如果能够先了解四阶B树（2-3-4树），将能更好地学习理解红黑树。

四阶B树的性质：

• 所有节点能存储的元素个数 x ： 1 <= x <= 3
• 所有非叶子结点的子节点个数 y ： 2 <= y <= 4

练习

假设有一棵四阶B树，先进行添加元素 1 - 22 ，然后在删除元素 1 - 22 。

添加元素后，这个B树为：

可视化添加网址： Data Structure Visualizations

2. 红黑树

注意：红黑树中的叶子节点指的是假想的空节点（null）。

内容所限，后面展示的红黑树都将省略 NULL 节点。

2.1 等价变换

现有一棵下列这样的红黑树，我们将它的布局变一下：

从右边的图我们可以看到，这棵红黑树的样子很像前面学习的B树。可得一棵四阶B树：

• 红黑树 和 四阶B树（2-3-4树）具有等价性
• BLACK 节点与它的 RED 子节点融合在一起，形成一个B树节点（重点）
• 红黑树的 BLACK 节点个数与四阶B树的节点总个数相等
• 在变换成的B树节点中永远是黑色节点作为父节点
• 用 2-3 树（三阶B树）与红黑树进行类比是极其不严谨的， 2-3 树并不能完美匹配红黑树的所有情况

布局变换

如果上图最底层的 BLACK 节点是不存在的，在B树中会是什么样的情形呢？

整棵B树只有一个根节点，而且是超级节点。

2.2 辅助函数

一些英文定义

• parent ：父节点

• sibling ：兄弟节点

• uncle ： 叔父节点（ parent 的兄弟节点，比如节点 25 是节点 50 的叔父节点）

• grand ： 祖父节点（ parent 的父节点）

辅助函数

红黑树也是一种自平衡二叉搜索树，因此编写红黑树的代码时需要继承二叉搜索树。除此之外，红黑树的节点有颜色之分，与编写AVL树的思路一样，在红黑树里编写一个表示红黑树节点的内部类并继承Node<E>。

也正是因为红黑树的节点有颜色之分，因此我们一般需要编写判断某个节点颜色的代码 。又因为用户在使用时是不会传递节点颜色的，因此还需要编写给节点染色的代码 。

public class RBTree<E> extends BST<E> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public RBTree() {
        this(null);
    }

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

    // 节点染色
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return null;
        ((RBNode<E>) node).color = color;
        return node;
    }

    // 节点染成红色
    private Node<E> red(Node<E> node){
        return color(node, RED);
    }

    // 节点染成黑色
    private Node<E> black(Node<E> node){
        return color(node, BLACK);
    }

    // 查看某一节点的颜色
    private boolean colorOf(Node<E> node){
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    // 判断节点颜色是否是黑色
    private boolean isBlack(Node<E> node){
        return colorOf(node) == BLACK;
    }

    // 判断节点颜色是否是红色
    private boolean isRed (Node<E> node){
        return colorOf(node) == RED;
    }

    private static class RBNode<E> extends Node<E> {
        boolean color = RED;

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

}

最开始时，介绍了一些英文定义，为方便后续编写，我们可以在BinaryTree类中的内部类Node<E>添加一个方法sibling()，该方法由于求取当前节点的兄弟节点：

// 一个节点就是一个Node
protected static class Node<E> {
    E element;  // 节点元素值
    Node<E> left;   // 左节点
    Node<E> right;  // 右节点
    Node<E> parent; // 父节点

    public Node(E element, Node<E> parent) {
        this.element = element;
        this.parent = parent;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    public boolean hasTwoChildren() {
        return left != null && right != null;
    }

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

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

    // 获取兄弟节点
    public Node<E> sibling(){
        if (isLeftChild()){
            return parent.right;
        }
        if (isRightChild()){
            return parent.left;
        }
        return null;
    }
}

如果需要求某一节点的叔父节点，直接node.parent.sibling()即可。

2.3 添加分析

已知：

• B树中，新添加元素必定是添加到叶子节点中
• 四阶B树所有节点的元素个数 x 都符合 1 <= x <= 3

前面已经分析，红黑树可以等价变换为四阶B树，因此我们在思考红黑树时，尽量将其转换成四阶B树进行思考。

建议新添加的节点默认为 RED ，这样能够让红黑树的性质尽快满足。（性质1、2、3、5都满足，性质 4 有待思考）

如果添加的是根节点，染成 BLACK 即可。

2.4 添加分类

先将一颗红黑树的布局进行变换一下：

根据前面的分析，添加节点时一共有下列 12 种位置情况：

• 节点 17 的左右子树
• 节点 33 的左右子树
• 节点 46 的左子树
• 节点 50 的左右子树
• 节点 72 的左右子树
• 节点 76 的右子树
• 节点 88 的左右子树

添加节点满足性质4时

在上述情况中有 4 中情况满足红黑树的性质 4 （其他性质当然也满足）： parent 为 BLACK 的时候，即：

同样，上述添加方式也满足四阶B树的性质，因此不需要做任何额外处理。

添加节点不满足性质4时

性质 4 ： 红黑树中不能有两个连续的红色节点

那么，剩下的 8 中情况不满足红黑树的性质 4 ： parent 为 RED （Double Red），即：

2.5 添加修复

上图中，在节点 50 的右子节点添加节点 52后，似乎会导致节点 46 失衡？注意，现在这棵树是红黑树，不是AVL树，在红黑树中没有平衡因子的概念，更没有失衡的概念，我们只需要满足红黑树的5条性质就可以让红黑树保持平衡。（用前朝的剑，斩本朝的官？ 😨）

添加 - LL / RR

从B树出发，如果我们想添加节点52，那么需要将节点50要变黑，节点46要变==红== ，让节点 50 成为节点46和节点52的父节点，并让节点38指向节点50； 如果想添加节点60 ，同样需要将节点72变黑，节点76要变==红== ，让节点72成为节点60和节点76的父节点，并让节点55指向节点76 ；即：父节点染黑，祖父节点染红，然后进行旋转。

---

判定条件： uncle 不是 RED

1、parent 染成 BLACK ，grand 染成 RED

2、grand 进行单旋操作

• RR：在上述情况中，对节点 46 进行左旋转
• LL：在上述情况中，对节点 76 进行右旋转

添加 - LR / RL

---

判定条件： uncle 不是 RED

1、添加节点自己染成 BLACK ，grand 染成 RED

2、进行双旋操作

• RL： parent 右旋转，grand 左旋转 （节点 48 ）

• LR： parent 左旋转，grand 右旋转 （节点 74 ）

添加 - 上溢 - LL

添加节点 10 后，红黑树等价变换的B树出现上溢现象，对其进行修复。为了方便修复，选择节点 25 （选择节点 17 也行，但是不方便）与变换后的B树根节点进行合并。对B树根节点来说，节点 25 的合并，就相当于对B树根节点插入了一个元素，可以将要进行合并的节点 25 当作新添加的节点进行处理（递归）。

---

判定条件： uncle 是 RED

1、parent、uncle 染成 BLACK

2、grand 向上合并

• grand 染成 RED ，当作是新添加的节点进行处理

然后套用前面的逻辑即可。

grand 向上合并时，可能继续发生上溢，若持续上溢到根节点，只需要将根节点染成 BLACK 即可。

添加 - 上溢 - RR

---

判定条件： uncle 是 RED

1、parent、uncle 染成 BLACK

2、grand 向上合并

• grand 染成 RED ，当作是新添加的节点进行处理

然后套用前面的逻辑即可。

添加 - 上溢 - LR

---

判定条件： uncle 是 RED

1、parent、uncle 染成 BLACK

2、grand 向上合并

• grand 染成 RED ，当作是新添加的节点进行处理

然后套用前面的逻辑即可。

添加 - 上溢 - RL

判定条件： uncle 是 RED

1、parent、uncle 染成 BLACK

2、grand 向上合并

• grand 染成 RED ，当作是新添加的节点进行处理

然后套用前面的逻辑即可。

2.6 添加实现

在 2.5 添加修复 中已经介绍，在红黑树中插入节点时需要使用到旋转的操作，而红黑树的旋转和AVL树的旋转代码逻辑是一样的，两者是可以复用的，因此，我们需要对代码再次进行重构。

编写一个表示自平衡二叉搜索树的类BBST，在这个类中存放与旋转有关的代码，然后就可以用描述AVL树的类和描述红黑树的类来继承这个类，达到旋转代码复用的目的。

BBST.java：

public class BBST<E> extends BST<E> {

    public BBST() {
        this(null);
    }

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

    // 左旋转
    protected 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);
    }

    // 右旋转
    protected 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);
    }

    protected 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;
    }

    protected 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;
        }

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

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

接下来就是红黑树添加节点后的处理了（添加操作直接使用BST类中的添加代码即可，然后重写afterAdd()）

我们先理一下思路：

1、获取插入节点父节点 parent

2、添加节点是根节点时，直接将添加节点染黑并返回

3、添加节点的父节点是黑色时，也直接返回

4、获取添加节点的叔父节点 uncle 、获取添加节点的祖父节点 grand

5、叔父节点是红色时，注意此时B树节点上溢。先将父节点染黑，再将叔父节点染黑，将祖父节点作为新添加节点向上合并进行递归

6、叔父节点不是红色时，按照 LL 、LR、 RL 、 RR 进行判断旋转

最终在RBTree类中重写afterAdd方法，得到的代码如下：

@Override
protected void afterAdd(Node<E> node) {
    Node<E> parent = node.parent;
    // 添加节点是根节点时 或 上溢到根节点
    if (parent == null) {
        black(node);
        return;
    }
    // 如果添加节点的父节点是黑色，直接返回
    if (isBlack(parent)) return;
    // 获取叔父节点
    Node<E> uncle = parent.sibling();
    // 获取祖父节点
    Node<E> grand = red(parent.parent);
    if (isRed(uncle)) { // 叔父节点是红色时[B树节点上溢]
        black(parent);
        black(uncle);
        // 把祖父节点当作新添加的节点
        afterAdd(grand);
        return;
    }
    // 叔父节点不是红色时
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            black(parent);
        } else { // LR
            black(node);
            rotateLeft(parent);
        }
        rotateRight(grand);
    } else { // R
        if (node.isLeftChild()) { // RL
            black(node);
            rotateRight(parent);
        } else { // RR
            black(parent);
        }
        rotateLeft(grand);
    }
}

在创建红黑树节点时，我们需要创建在RBTree类中直接编写的节点对象RBNode<E>，而不是二叉树的默认节点对象Node<E>，因此我们还需要重写创建节点的方法：

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

为了便于打印，我们重写RBNode<E>类中的toString()方法，在打印节点时给红色节点设置一个前缀，黑色节点不进行设置以便于区分：

private static class RBNode<E> extends Node<E> {
    boolean color = RED;

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

    @Override
    public String toString() {
        String str = "";
        if (color == RED){
            str = "R_";
        }
        return str + element.toString();
    }
}

测试代码：

static void test2() {
    Integer[] data = new Integer[]{
            55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
    };
    RBTree<Integer> rb = new RBTree<>();
    for (int i = 0; i < data.length; i++) {
        rb.add(data[i]);
        System.out.println("【"+data[i]+"】");
         BinaryTrees.println(rb);
         System.out.println("---------------------------------");
    }
   // BinaryTrees.println(rb);
}

public static void main(String[] args) { test2(); }

2.7 删除分析

介绍B树时，已经知道： 在B树中删除元素时，真正删除的元素都是发生在叶子节点中的。

而红黑树是可以变换成四阶B树的，比如对于下图的红黑树，真正删除的元素已被圈出：

针对被删除元素的位置可以分成两大类：

• 删除红色节点时 （直接删除，不作任何调整）

• 删除黑色节点时 （后续分析）

2.8 删除黑色节点

对于删除黑色节点，共有三种情况：

1、拥有两个 RED 子节点的 BLACK 节点

• 不可能直接被删除，因为会找它的子节点进行删除
• 因此不考虑这种情况

2、拥有一个 RED 子节点的 BLACK 节点

3、BLACK 叶子节点

因此，需要考虑的情况就只有两种。

那如何区分这两种？判定条件是什么？

判定条件： 用以替代的子节点是 RED

当删除节点 46 或节点 76 时，删除后，我们需要删除节点的父节点指向删除节点的子节点，这个时候删除节点的子节点时红色，且是用以替代的子节点。（删除情况 2 ）

当删除叶子节点 88 时，因为其没有子节点，因此删除后不会有节点来替代它。在红黑树中，我们认为空节点的颜色是黑色，因此也可以认为删除叶子节点后用以替代的节点（空节点）颜色为黑色。（删除情况 3 ）

拥有一个红色子节点的黑色节点

使用子节点替代原删除节点时，可能会出现不满足红黑树性质的情况。

方法：将替代子节点染成 BLACK 即可保持红黑树性质。

原红黑树：

进行删除后：

删除黑色叶子节点 - sibling为黑色，其子节点至少有一个为红色

当我们删除的节点是叶子节点时，可能会发生红黑树转换的B树下溢。在前面B树的分析中，发生下溢后，可以向临近的B树兄弟节点“借”一个元素，但是“借”是有前提的：红黑树中删除节点的兄弟节点必须是 BLACK ，且其子节点至少有一个是 RED 。

具体操作如下：

BLACK 叶子节点被删除后，可能会导致红黑树转换的B树节点下溢（比如删除下列红黑树中的节点 88 ），如果删除节点的兄弟节点为 BACLK ，且兄弟节点至少有一个 RED 子节点：

• 按照不同的类别进行旋转操作
• 旋转最后的中心节点继承 parent 的颜色
• 旋转之后的左右节点染为 BLACK

删除前：

对上述红黑树删除叶子节点 88 后进行的旋转操作：

• 对第一棵红黑树的节点 76 进行左旋转，对节点 80 进行右旋转
• 对第二棵红黑树的节点 80 进行右旋转
• 对第三棵红黑树的节点 80 进行右旋转（也可以进行双旋，此处有两种做法）

删除后：

删除黑色叶子节点 - sibling为黑色，其子节点没有一个为红色

前面说了下溢兄弟节点能“借”的情况，如果兄弟节点不能“借”的时候呢？

删除节点的兄弟节点不能“借”时，就是删除节点的兄弟节点没有一个 RED 子节点的时候（比如删除下列红黑树中的节点 88 ），具体操作如下：

• 如果删除节点的父节点是 RED ，将 sibling 染成 RED ，parent 染成 BLACK 即可修复红黑树性质（因为父节点是红色，必然有一个黑节点与它一起组成B树节点，必然不可能再次下溢）
• 如果删除节点的父节点是 BLACK ，会导致 parent 也下溢，这时只需要把 parent 当作被删除的节点处理即可（递归）

父节点红色时：

父节点黑色时：

删除黑色叶子节点 - sibling为红色

如果删除节点的兄弟节点为 RED 时（侄子变兄弟）：

• sibling 染成 BLACK ，parent 染成 RED ，进行右旋转
• 于是又回到 sibling 是 BLACK 的情况

删除节点 88 ，示意图如下：

染色后，对节点 80 进行右旋转，让节点 76 成为被删除节点 88 的兄弟节点（可以理解为 LL ，这里的 LL 指的是节点 46），主要目的还是为了让节点 76 成为被删除节点 88 的兄弟节点。

2.9 删除实现

分析

删除可以使用BST类中的删除代码，分为：

• 删除度为 2 的节点
• 删除度为 1 的节点
• 删除度为 0 的节点

红黑树中，真正删除的节点都是在转换成B树的叶子节点中。除删除叶子节点外，其他删除节点实际上是删除该节点的前驱或后继节点，而前驱和后继节点都是在叶子节点中，所以真正删除的节点都是在转换成B树的叶子节点中。

删除使用BST的代码，但红黑树在删除节点后会进行一系列修复变化，而这样的修复变化发生在afterRemove()中，BST类中也提供了afterRemove()方法，我们需要在红黑树中重写即可。

理一下哪些情况需要进行修复：

1、删除节点是红色时

2、用于取代被删除节点的子节点是红色时

3、删除节点是根节点时

4、删除节点是黑色叶子节点时，在这种情况下又分为以下几种情况：

首先判断被删除节点是左子节点还是右子节点以便确定其兄弟节点的位置，这两种情况是对称的。对 “被删除节点在左边，兄弟节点在右边” 有以下情况：

• 被删除节点兄弟节点是红色
• 兄弟节点是黑色，兄弟节点一个红色子节点都没，父节点向下跟兄弟节点合并
• 兄弟节点是黑色，兄弟节点至少有一个红色子节点，向兄弟节点借元素
  • 兄弟节点左子节点是黑色，先对兄弟进行旋转
  • 兄弟节点左子节点是红色

实现

先对BST类中节点删除方法remove()进行改写：

// 删除某一节点
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;
        // 更改node的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;
        }

        // 被删除的节点
        /** 传递 replacement
         * 1. 对AVL树无影响
         * AVL树进行删除时会根据 node 的 parent 进行递归
         * 但前面已 replacement.parent = node.parent;
         * 所以传递 node 还是 replacement 对于AVL树都是一样的
         * 2. 而对于红黑树恰好需要传递 replacement 才行
         * 如果传递的是 node ，还得在红黑树的代码中找到被删除节点的代替节点
         * 但是在红黑树中又不能直接使用 node.left 或 node.right 获取
         * 因为后续代码存在递归，如果使用会造成错误
         * 因此对于红黑树，我们必须在此传递 replacement
         * 直接从参数中获取被删除节点的代替节点
         * */
        afterRemove(replacement);
    } 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);
    }
}

在红黑树RBTree类中，对afterRemove()方法进行重写，实现红黑树删除节点后的修复变化：

@Override
protected void afterRemove(Node<E> node) {
    /**
     * 更改BST中删除度为1的代码 afterRemove(replacement);
     * 传入的是 replacement，而不是 node
     * 但 replacement 如果是红色就会直接返回，显然不对
     * 因此，直接注释，使用下面的代码
     */
    // if (isRed(node)) return;
    /**
     * 1. 用于被删除节点是红色 --> 将删除节点又染成了黑色没印象吗？
     * 答： 人都死了，黑就黑了，没影响
     * 2. 或者 用于取代被删除节点的子节点是红色
     */
    if (isRed(node)) {
        black(node);
        return;
    }
    // 获取被删除节点的父节点
    Node<E> parent = node.parent;
    // 被删除节点是根节点
    if (parent == null) return;

    // 被删除节点是黑色叶子节点[下溢]
    /**Node<E> sibling = node.sibling();
     * 不能直接这样获取兄弟节点，无法判断被删除节点是左节点还是右节点
     * 在执行 afterRemove()方法前，被删除节点已被清空
     * 导致无法判断被删除节点是左右节点的哪一个
     * 最终就导致 sibling() 获取的总是为 null
     */
    // 判断被删除的节点是左子节点还是右子节点
    /**
     * 被删除节点已经被清空，设置为 null
     * 如果删除的是左节点（左节点为空），那么其兄弟节点就是右节点
     * 如果删除节点不是叶子节点时（递归传入的节点），需要更换判断
     */
    boolean left = parent.left == null || node.isLeftChild();
    Node<E> sibling = left ? parent.right : parent.left;
    /**
     * 删除有两种情况，这两种情况是对称的
     * 1. 被删除节点在左边，兄弟节点在右边
     * 2. 被删除节点在右边，兄弟节点在左边
     */
    if (left) { // 被删除节点在左边，兄弟节点在右边
        if (isRed(sibling)) { // 被删除节点兄弟节点是红色
            black(sibling);
            red(parent);
            rotateLeft(parent);
            // 更换兄弟
            sibling = parent.right;
        }
        // 此时兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟节点一个红色子节点都没，父节点向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                // 父节点为黑色时，下溢，进行递归
                afterRemove(parent);
            }
        } else { // 兄弟节点至少有一个红色子节点，向兄弟节点借元素
            // 兄弟节点左子节点是黑色，先对兄弟进行旋转
            if (isBlack(sibling.right)) {
                rotateRight(sibling);
                // 旋转后，重置兄弟节点位置
                sibling = parent.right;
            }
            // 先染色兄弟节点，再染色父节点：兄弟节点跟随父节点染色
            color(sibling, colorOf(parent));
            black(sibling.right);
            black(parent);
            rotateLeft(parent);

        }
    } else { // 被删除节点在右边，兄弟节点在左边
        if (isRed(sibling)) { // 被删除节点兄弟节点是红色
            black(sibling);
            red(parent);
            rotateRight(parent);
            // 更换兄弟
            sibling = parent.left;
        }
        // 此时兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟节点一个红色子节点都没，父节点向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else { // 兄弟节点至少有一个红色子节点，向兄弟节点借元素
            // 兄弟节点左子节点是黑色，先对兄弟进行旋转
            if (isBlack(sibling.left)) {
                rotateLeft(sibling);
                sibling = parent.left;
            }
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }
}

测试代码：

static void test3() {
    Integer[] data = new Integer[]{
            55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
    };
    RBTree<Integer> rb = new RBTree<>();
    for (int i = 0; i < data.length; i++) {
        rb.add(data[i]);
    }
    BinaryTrees.println(rb);
    for (int i = 0; i < data.length; i++) {
        rb.remove(data[i]);
        System.out.println("---------------------------------");
        System.out.println("【" + data[i] + "】");
        BinaryTrees.println(rb);
    }
}

我傻了，这玩意儿真的多 😡

3. 红黑树的平衡

红黑树与AVL树都是自平衡二叉搜索树，AVL树中引入平衡因子的概念，要求每个节点的平衡因子绝对值不大于 1 ，这样就能够使AVL达到平衡，那么对于红黑树又是怎么进行平衡的呢？

在本文开头，我们首先就说明了红黑树的五条性质，同时要求红黑树必须满足这些性质才能叫红黑树，那么这些性质有什么用？

这些性质就可以保证红黑树是平衡的，或者说那五条性质可以保证红黑树是等价于四阶B树的。

然后在谈论B树时，就已经说过B树是平衡的（B树比较矮），然后红黑树可以等价于B树，从某种意义上也说明了红黑树是平衡的。

虽然B树是比较矮，也比较平衡，但是红黑树等价的四阶B树展开后又比较高了，真的可以办到比较平衡？

首先回顾一下平衡的概念，我们说的平衡不是绝对的、理想的平衡，就是说当一棵树的高度不要太高、太夸张，我们就可以认为这棵树是平衡的。而红黑树能保证其高度不像二叉搜索树一样夸张，从而退化成链表，这时我们就说红黑树达到了平衡。

相比于AVL树，红黑树的平衡标准比较宽松： 没有一条路径会大于其他路径的 2 倍 ，为什么有这样的标准？

在红黑树中，最长路径是每有一个黑节点就来一个红节点的路径，最短路径是黑色根节点后就只有一个黑子节点的路径，这样就会出现没有一条路径会大于其他路径的 2 倍。

红黑树的平衡是一种弱平衡、黑高度平衡，而AVL树就是一种强平衡。

红黑树的最大高度是 2 * log₂ (n + 1) ，依然是 O(logn) 级别的。

4. 性能对比

4.1 平均时间复杂度

红黑树平均时间复杂度

• 搜索： O(logn)
• 添加： O(logn)，需O(1) 次的旋转操作，旋转次数与树高无关
• 删除： O(logn)，O(1) 次的旋转操作，旋转次数与树高无关。虽然红黑树中的删除也有递归操作，有了递归操作就可能出现旋转，但由于红黑树本身的性质，据统计表明这种递归旋转最多不操作 3 次，因此也是 O(1) 级别的。

AVL树平均时间复杂度

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

4.2 AVL树 VS 红黑树

AVL树

• 平衡标准比较严格： 每个左右子树的高度差不超过 1
• 最大高度是 1.44 * log₂ (n + 2) - 1.328 （100W个节点，AVL树最大树高 28 ）
• 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次调整、删除最多需要 O(logn) 次旋转调整

红黑树

• 平衡标准比较宽松： 没有一条路径会大于其他路径的 2 倍
• 最大高度是 2 * log₂ (n + 1) （100W个节点，红黑树最大树高 40 ）
• 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整

二者抉择

• 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量旋转操作，整体来说性能优于AVL树
• 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

🌸赤黒木の大きな勝利（皮一下，渣机翻）🌸