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

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

  1. 自己染成BLACK，grand染成RED
  2. 进行双旋操作
    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

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

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

◼判定条件:uncle 是RED

  1. parent、uncle 染成 BLACK
  2. 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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,406评论 5赞 475
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,976评论 2赞 379
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,302评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,366评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,372评论 5赞 363
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,457评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,872评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,521评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,717评论 1赞 295
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,523评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,590评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,299评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,859评论 3赞 306
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,883评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,127评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,760评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,290评论 2赞 342