【恋上数据结构与算法一】(十一)红黑树

作者: AlanGe | 来源:发表于2021-04-19 00:25 被阅读0次

红黑树(Red Black Tree)

◼ 红黑树也是一种自平衡的二叉搜索树
以前也叫做平衡二叉B树(Symmetric Binary B-tree)

◼红黑树必须满足以下 5 条性质
1.节点是RED或者BLACK
2.根节点是BLACK
3.叶子节点(外部节点，空节点)都是BLACK
4.RED 节点的子节点都是 BLACK
✓RED 节点的 parent 都是 BLACK
✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
5.从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

◼ 为何这些规则下，就能保证平衡?

请问下面这棵是红黑树么?

◼红黑树必须满足以下 5 条性质
1.节点是RED或者BLACK
2.根节点是BLACK
3.叶子节点(外部节点，空节点)都是BLACK
4.RED 节点的子节点都是 BLACK
✓RED 节点的 parent 都是 BLACK
✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
5.从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

不是，不满足第5条性质，38后面有null子叶，根节点到38这个节点包含的BLACK节点数与其他不一样。

红黑树的等价变换

◼红黑树和 4阶B树(2-3-4树)具有等价性
◼BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
◼红黑树的 BLACK 节点个数与 4阶B树的节点总个数相等
◼网上有些教程:用 2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况
◼注意:因为PPT界面空间有限，后面展示的红黑树都会省略NULL 节点

红黑树 vs 2-3-4树

◼思考:如果上图最底层的BLACK 节点是不存在的，在B树中是什么样的情形?
整棵B树只有1个节点，而且是超级节点

几个英文单词

◼ parent:父节点
◼ sibling:兄弟节点
◼ uncle:叔父节点( parent 的兄弟节点)
◼ grand:祖父节点( parent 的父节点)

一些辅助函数

private Node<E> color(Node<E> node, boolean color) {
    if (node == null) return node;
    ((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;
}

public Node<E> sibling() {
    if (isLeftChild()) {
        return parent.right;
    }
    
    if (isRightChild()) {
        return parent.left;
    }
    
    return null;
}

添加

◼已知
B树中，新元素必定是添加到叶子节点中
4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3

◼ 建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足(性质 1、2、3、5 都满足，性质 4 不一定)

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

添加的所有情况

◼ 有 4 种情况满足红黑树的性质 4 :parent 为 BLACK
同样也满足 4阶B树的性质
因此不用做任何额外处理

◼ 有 8 种情况不满足红黑树的性质 4 :parent 为 RED( Double Red )
其中前 4 种属于B树节点上溢的情况

添加 – 修复性质4 – LL\RR

◼判定条件:uncle 不是RED
1.parent 染成 BLACK，grand 染成 RED
2.grand 进行单旋操作
LL:右旋转
RR:左旋转

添加 – 修复性质4 – LR\RL

◼判定条件:uncle 不是RED

自己染成BLACK，grand染成RED
进行双旋操作
LR:parent 左旋转， grand 右旋转
RL:parent 右旋转， grand 左旋转

添加 – 修复性质4 – 上溢 – LL

◼判定条件:uncle 是RED
1parent、uncle 染成 BLACK
2.grand 向上合并
染成 RED，当做是新添加的节点进行处理

◼grand 向上合并时，可能继续发生上溢

◼ 若上溢持续到根节点，只需将根节点染成 BLACK

添加 – 修复性质4 – 上溢 – RR

◼判定条件:uncle 是RED
1.parent、uncle 染成 BLACK
2.grand 向上合并
染成 RED，当做是新添加的节点进行处理

添加 – 修复性质4 – 上溢 – LR

◼判定条件:uncle 是RED

parent、uncle 染成 BLACK
grand 向上合并
染成 RED，当做是新添加的节点进行处理

添加 – 修复性质4 – 上溢 – RL

◼判定条件:uncle 是RED

parent、uncle 染成 BLACK
grand 向上合并
染成 RED，当做是新添加的节点进行处理

@Override
protected void afterAdd(Node<E> node) {
    Node<E> parent = node.parent;
    
    // 添加的是根节点 或者 上溢到达了根节点
    if (parent == null) {
        black(node);
        return;
    }
    
    // 如果父节点是黑色，直接返回
    if (isBlack(parent)) return;
    
    // 以上已经处理前4种情况
    
    // 中间4种
    // 叔父节点
    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);
    }
}

static void test1() {
    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("---------------------------------------");
    }
}

删除

◼ B树中，最后真正被删除的元素都在叶子节点中

删除 – RED节点

◼ 直接删除，不用作任何调整

删除 – BLACK节点

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

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

BLACK 叶子节点

删除 – 拥有1个RED子节点的BLACK节点

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

◼将替代的子节点染成BLACK 即可保持红黑树性质

删除 – BLACK叶子节点 – sibling为BLACK

◼BLACK 叶子节点被删除后，会导致B树节点下溢(比如删除88)
◼ 如果 sibling 至少有 1 个 RED 子节点
进行旋转操作
旋转之后的中心节点继承 parent 的颜色
旋转之后的左右节点染为 BLACK

◼ 判定条件:sibling 没有 1 个 RED 子节点
◼ 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

◼ 如果 parent 是 BLACK
会导致parent 也下溢
这时只需要把 parent 当做被删除的节点处理即可

删除 – BLACK叶子节点 – sibling为RED

◼ 如果 sibling 是 RED
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();
    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);
        }
    }
}

static void test() {
    Integer data[] = new Integer[] {
            55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
    };
    System.out.println("--------------------------------------- 红黑树 - 添加");
    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);
    }
}

验证：http://520it.com/binarytrees/

红黑树的平衡

◼ 最初遗留的困惑：为何那5条性质，就能保证红黑树是平衡的?
那5条性质，可以保证红黑树等价于 4阶B树

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

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

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

平均时间复杂度

◼ 搜索:O(logn)
◼添加:O(logn)，O(1) 次的旋转操作
◼删除:O(logn)，O(1) 次的旋转操作

AVL树 vs 红黑树

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

◼ 红黑树
平衡标准比较宽松:没有一条路径会大于其他路径的2倍
最大高度是 2 ∗ log2(n + 1)( 100W个节点，红黑树最大树高40)
搜索、添加、删除都是 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

网友评论

本文标题：【恋上数据结构与算法一】(十一)红黑树

本文链接：https://www.haomeiwen.com/subject/lppblltx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！