【数据结构】红黑树

2024-03-23 11:30:58

红黑树介绍
- 下面的这棵是红黑树吗？
红黑树与 4阶B树（等价性）
- 红黑树与 2-3-4树等价转换
红黑树基础代码
- 一些辅助函数
添加（12种情况）
删除（12种情况）
红黑树的完整代码
红黑树的平衡
平均时间复杂度
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) 次旋转调整

◼ 红黑树

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

◼ 搜索的次数远远大于插入和删除，选择AVL树；
搜索、插入、删除次数几乎差不多，选择红黑树

◼ 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

◼ 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

BST vs AVL Tree vs Red Black Tree

插入数值：10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96

码农公寓

【数据结构】红黑树

目录

红黑树介绍

下面的这棵是红黑树吗？

红黑树与 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

码农公寓

目录

红黑树介绍

下面的这棵是红黑树吗？

红黑树 与 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

相关文章

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

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

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

兄弟节点 sibling 为 BLACK【 4 种】