红黑树介绍
- 下面的这棵是红黑树吗？
红黑树与 4阶B树（等价性）
- 红黑树与 2-3-4树等价转换
红黑树基础代码
- 一些辅助函数
添加（12种情况）
- 1、parent 为 BLACK【 4 种】
- 2、parent 为 RED
- - Ⅰ、uncle 节点是红色【上溢的情况 4 种】
  - Ⅱ、uncle 节点不是红色【旋转的情况 4 种】
- 添加代码
删除（12种情况）
- 1、删除 RED 节点【 3 种】
- 2、删除 BLACK 节点
- - Ⅰ、拥有 2 个 RED 子节点的 BLACK 节点
  - Ⅱ、拥有 1 个 RED 子节点的 BLACK 节点【 2 种】
  - Ⅲ、BLACK 叶子节点
  - - 兄弟节点 sibling 为 BLACK【 4 种】
    - 兄弟节点 sibling 为 RED
- 删除代码
红黑树的完整代码
红黑树的平衡
平均时间复杂度
AVL树 vs 红黑树
BST vs AVL Tree vs Red Black Tree

红黑树介绍

在这里插入图片描述

红黑树也是一种自平衡的二叉搜索树

以前也叫做平衡二叉B树（Symmetric Binary B-tree）

红黑树必须满足以下5 条性质

节点是RED 或者BLACK
根节点是BLACK
叶子节点（外部节点，空节点）都是BLACK
RED节点的子节点都是BLACK
① RED节点的parent 都是BLACK
② 从根节点到叶子节点的所有路径上不能有 2 个连续的RED节点
从任意节点到叶子节点的所有路径都包含相同数目的BLACK节点

下面的这棵是红黑树吗？

不是
在这里插入图片描述

红黑树与 4阶B树（等价性）

在这里插入图片描述

红黑树和 4阶B树（2-3-4树）具有等价性

BLACK节点与它的RED子节点融合在一起，形成1个B树节点（在B树节点中，黑色节点永远是父节点）

上面那张红黑树变成了下面这个样子：
在这里插入图片描述

红黑树的 BLACK节点个数与 4阶B树的节点总个数相等；

下面是一个与上面的红黑树等价的 4阶B树；
在这里插入图片描述
网上有些教程用 2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况。
由于界面有限，后面展示的红黑树都会省略 黑色NULL节点。

红黑树与 2-3-4树等价转换

在这里插入图片描述
思考：如果上图最底层的 BLACK 节点是不存在的，在 B树中是什么样的情形？

整棵 B树只有1个节点，而且是超级节点

红黑树基础代码

在这里插入图片描述

一些辅助函数

/**
 * 对传入的节点染色，并返回染色后的该节点
 */
private Node<E> color(Node<E> node, boolean color) {
    if (node == null) return node;
    ((RBTNode<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);
}
/**
 * 判断当前节点是什么颜色
 * @return 返回 BLACK 或 RED
 */
private boolean colorOf(Node<E> node) {
    // 如果节点是null，说明是空节点，返回black，否则返回节点本身的颜色
    return node == null ? BLACK : ((RBTNode<E>) node).color;
}
/**
 * 判断当前节点是否是黑颜色
 * @return true 或 false
 */
private boolean isBlack(Node<E> node) {
    return colorOf(node) == BLACK;
}
/**
 * 判断当前节点是否是红颜色
 * @return true 或 false
 */
private boolean isRed(Node<E> node) {
    return colorOf(node) == RED;
}

添加（12种情况）

已知

B树中，新元素必定是添加到叶子节点中
4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）

添加有12种情况：
新添加的节点（默认红色）

1、当 parent 是黑色，不做任何处理，添加完成后任是一棵红黑树。

2、当 parent 不是黑色（为红色）：即当前节点和父节点都是红色的情况（double red）

Ⅰ：其中4种为上溢的情况：【判定条件：uncle 节点是红色】
①：上溢【LL】【RR】【LR】【RL】：
将 parent、uncle 染成黑色，然后 grand 向上合并，并且将 grand 染成红色当作新节点处理【递归】；
grand 向上合并时，可能会继续发生上溢，若上溢到根节点，只需将根节点染成黑色。

Ⅱ：其中4种为旋转的情况：【判定条件：uncle 节点不是红色（是黑色）】
①：旋转【LL】【RR】
将 parent 染成黑色，grand 染成红色，
然后对 grand 进行旋转，
若 grand 是 LL 的情况：右旋转，
若 grand 是 RR 的情况：左旋转。
②：旋转【LR】【RL】
将自己染成黑色，grand 染成红色，
然后对 grand 进行旋转，
若 grand 是 LR 的情况：parent 左旋转、grand 右旋转，
若 grand 是 RL 的情况：parent 右旋转、grand 左旋转。

1、parent 为 BLACK【 4 种】

有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK

同样也满足 4阶B树的性质
因此不用做任何额外处理

2、parent 为 RED

有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ）

Ⅰ、uncle 节点是红色【上溢的情况 4 种】

其中这 4 种属于B树节点上溢的情况【LL】【RR】【LR】【RL】
在这里插入图片描述

Ⅱ、uncle 节点不是红色【旋转的情况 4 种】

其中这 4 种为旋转的情况
在这里插入图片描述

添加代码

@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 = parent.parent;
    if (isRed(uncle)) {
     // 叔父节点是红色【B树节点上溢】
        black(parent);
        black(uncle);
        // 把祖父节点当做是新添加的节点
        afterAdd(red(grand));
    } else {
     // 叔父节点不是红色【旋转】
        if (parent.isLeftChild()) {
     // L
            if (node.isLeftChild()) {
     // LL
                red(grand);
                black(parent);
                rotateRight(grand);
            } else {
     // LR
                red(grand);
                black(node);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {
     // R
            if (node.isLeftChild()) {
     // RL
                red(grand);
                black(node);
                rotateRight(parent);
                rotateLeft(grand);
            } else {
     // RR
                red(grand);
                black(parent);
                rotateLeft(grand);
            }
        }
    }
}

删除（12种情况）

◼ B树中，最后真正被删除的元素都在叶子节点中
在这里插入图片描述

1、删除 RED 节点【 3 种】

◼ 直接删除，不用作任何调整
在这里插入图片描述

2、删除 BLACK 节点

◼ BLACK 节点，有 2 个 RED 子节点（拥有 2 个 RED 子节点的 BLACK 节点）
✓ 不可能被直接删除，因为会找它的子节点替代删除
✓ 因此不用考虑这种情况

◼ BLACK 节点，有 1 个 RED 子节点（拥有 1 个 RED 子节点的 BLACK 节点）

◼ BLACK 叶子节点

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

Ⅱ、拥有 1 个 RED 子节点的 BLACK 节点【 2 种】

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

◼ 将替代的子节点染成 BLACK 即可保持红黑树性质
在这里插入图片描述

Ⅲ、BLACK 叶子节点

兄弟节点 sibling 为 BLACK【 4 种】

BLACK 叶子节点被删除后，会导致B树节点下溢（比如删除88）

◼ 判断条件： sibling 至少有 1 个 RED 子节点【3种，左、右、左右节点】（可以找兄弟节点借）

◼ 步骤：
 进行旋转操作

 旋转之后的中心节点继承 parent 的颜色（parent可能为黑色或红色）

 旋转之后的左右节点染为 BLACK
在这里插入图片描述
◼ 判定条件：sibling 没有 RED 子节点【1种】（无法找兄弟节点借）需要看父节点的颜色

若是红色（说明肯定有个黑色节点和它在同一高度），直接将红色父节点下来合并，原来的位置不会产生下溢
若是黑色（说明和它在同一高度，只有它一个节点），那么黑色父节点下来合并后，父节点的位置会产生下溢，此时将父节点当成要删除的节点处理即可（递归）

步骤：
 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

◼ 如果 parent 是 BLACK

 会导致 parent 也下溢

 这时只需要把 parent 当做被删除的节点处理即可
在这里插入图片描述

兄弟节点 sibling 为 RED

◼ 如果 sibling 是 RED【站在B树的角度，要处在同一层的兄弟节点才可以借，sibling（55）是在该节点（88）的父节点（80）里，需要将sibing节点的子节点（76）变成该节点的sibing，即要将 76 变成 80 的子节点，对80进行右旋转】

步骤：
 sibling 染成 BLACK，parent 染成 RED，进行旋转

 于是又回到 sibling 是 BLACK 的情况
在这里插入图片描述

删除代码

@Override
protected void afterRemove(Node<E> node) {
    // 如果删除的节点是红色
    // 或者 用以取代删除节点的子节点是红色
    if (isRed(node)) {
        black(node);
        return;
    }
    Node<E> parent = node.parent;
    // 删除的是根节点
    if (parent == null) return;
    // 删除的是黑色叶子节点【下溢】
    // 判断被删除的node是左还是右
    boolean left = (parent.left == null || node.isLeftChild());
    // 如果left为true，兄弟节点就是right，否则就是left
    Node<E> sibling = left ? parent.right : parent.left;
    if (left) {
     // 被删除的节点在左边，兄弟节点在右边
        if (isRed(sibling)) {
     // 兄弟节点是红色
            black(sibling);
            red(parent);
            rotateLeft(parent);
            // 更换兄弟
            sibling = parent.right;
        }
        // 兄弟节点必然是黑色
        if (isBlack(sibling.left) && isBlack(sibling.right)) {
            // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else {
     // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            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)) {
            // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
            boolean parentBlack = isBlack(parent);
            black(parent);
            red(sibling);
            if (parentBlack) {
                afterRemove(parent);
            }
        } else {
     // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
            // 兄弟节点的左边是黑色，兄弟要先旋转
            if (isBlack(sibling.left)) {
                rotateLeft(sibling);
                sibling = parent.left;
            }
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(parent);
            rotateRight(parent);
        }
    }
}

红黑树的完整代码

由于红黑树完整代码太多，单独写了一篇文章红黑树的完整代码

红黑树的平衡

◼ 最初遗留的困惑：为何那 5 条性质，就能保证红黑树是平衡的？

 那 5 条性质，可以保证红黑树等价于 4阶B树
在这里插入图片描述
◼ 相比 AVL 树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍

◼ 是一种弱平衡、黑高度平衡

◼ 红黑树的最大高度是 2 ∗ l o g 2 ( n + 1 ) 2 ∗ log2(n + 1) 2∗log2(n+1) ，依然是 O ( l o g n ) O(logn) O(logn) 级别

平均时间复杂度

◼ 搜索：O(logn)

◼ 添加：O(logn)，O(1) 次的旋转操作

◼ 删除：O(logn)，O(1) 次的旋转操作

AVL树 vs 红黑树

◼ AVL树

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

◼ 红黑树