敞开成长之旅！这是我参加「日新计划 · 12 月更文应战」的第9天，点击检查活动概况

红黑树删去的代码完成

写在前面

文章摘要

  1. 删去的节点在右边的状况
    • 几种简略的状况
    • 兄弟节点是赤色
    • 兄弟节点是黑色
      • 兄弟节点至少有一个赤色的子节点
      • 兄弟节点没有赤色的子节点
  2. 删去的节点在左面的状况（与上面对称）
  3. 优化参数&完好代码

阅览准备

  • 主张阅览时刻：10 ~ 15 分钟
  • 阅览条件：
    • 红黑树删去的剖析 -> 红黑树删去的评论剖析♨️♨️♨️
  • 本篇文章着重点是红黑树删去的代码完成，能够合作一同看👆👆👆

二、怎么用代码完成红黑树的删去

（0）完成前的准备

  • 剖析了这么这么这么久，真是长叹气以掩涕兮了😨🥶😭

  • 只不过看看《红黑树的删去》中对删去的总结，其实也并不是学不会，对吧，假如还有些迷糊，再来看看代码是怎么完成的，更迷糊一些吧~

  • 在开端完成：afterRemove()办法之前，咱们先来做两件工作：

    • 1、在afterRemove()办法中增加一个参数，稍后再解说为什么

    image-20221114182620385

    • 2、复习二叉查找树删去的代码逻辑

image-20221114181923856

（1）几种简略的状况

  • 先来看看这几种状况：
    • ①被删去的节点是赤色
    • ②BST度为1节点
    • ③真实删去的是根节点
    • ④BST”度为2“的节点
  • 看我列了这么多，是不是有些… 别着急，你看看这几种状况的完成，就知道有多简略了

image-20221114183322790

  • 这几种状况能够说是最简略的状况了
    • ①：删去的是赤色节点，不解说了
    • ②：假如传进来用于替代的子节点是赤色，阐明该节点必定是度为 1 的节点嘛，看看删去的代码即可知道
    • ③：取出父节点，若发现父节点是空的。阐明只要一个根节点，你把仅有的节点都删去了，直接回来就行了呗（当然，之后可能有其他状况，可能实际不只要一个节点，可是从逻辑上是，也能够满足）
    • ④：？？？都没看到这种状况啊？确实是，代码都不用写，由于真实被删去的节点在B树的最终一层，度又为2，就只能有一种状况了，再看看上面总结~

（2）下面评论的状况都是删去的是BST中度为0的节点

  • 经过了上面的四种状况，能来到这儿阐明：
    • 在二叉查找树中：删去的是度为0的节点
    • 在等价的4阶B树中：删去后会产生下溢现象
    • 在红黑树中：删去的是黑色的节点，且它自己一个子节点都没有
  • 经过上面的剖析和总结，来到这儿咱们需求取出兄弟节点来评论
  • 怎么取出兄弟节点呢？和之前相同node.sibling()吗？
  • 其实不然，咱们来看看，传入afterRemove()办法中节点的大致内存细节

image-20221116091051015

  • 能够发现，父节点对自己的引证都现已断掉了，只要自己内部还引证着父节点
  • 那咱们来看看node.sibling()办法，还能拿到真实的兄弟节点吗？

image-20221116091847002

  • 看了取兄弟节点的逻辑，是不是发现，根本拿不到兄弟节点了。那该怎么拿呢？
  • 来到这儿删去的必定是BST中度为0的叶子节点，而删去叶子节点，势必会铲除父节点对自己的引证
  • 对父节点来说：要么是 parent.left会清空，要么是parent.right会清空，反过来想想
  • 已然删去的节点在父节点的哪一边，那儿就会被清空。那咱们就能够依据哪边是空的，逆推出删去的是左面，还是右边。假如是parent.left == null，那么兄弟节点便是：parent.right。反之亦然

image-20221116093437030

  • 兄弟节点找到了，直接开端判别吗？
  • 回看上面的剖析，咱们评论的时分，都是用被删去的节点坐落右子树来举例的。其间也提到了，若删去的节点在左面，关于左右操作而言，是完全对称的。并且怎么染色也是共同的
  • 由此，就能够只完成一边，咱们以上面的例子，坐落右子树为例。另外一边只需求修正写好后的左右即可

image-20221116094531510

① BST兄弟节点是赤色

image-20221112201409280

  • 也便是咱们所说的，关系有些杂乱的一种状况，咱们需求将其转化成了解的状况，之后再共同处理

image-20221116150141290

  • 咱们无非是想要将兄弟的子节点（侄子），变成待删去节点的兄弟，所以这儿需求经过右旋，就交流了节点
  • 可是还需求维护红黑树的性质，所以将其原先的兄弟节点染成【黑色】，父节点染成【赤色】
  • 最终别忘了要将新的兄弟节点：sibling 赋值

② BST兄弟节点是黑色

  • 经过上面的操作，成功将兄弟节点是赤色的状况转化成了黑色，下面即可共同处理
  • 也便是说，来到这儿，兄弟节点必定是黑色，那咱们就能够依据兄弟是否有赤色的子节点来评论了

image-20221116150828962

1、至少有一个赤色的子节点

image-20221112091803449

  • 这种状况，兄弟节点很殷实，至少能够借一个给我，那就借一个给下溢的兄弟呗
  • 经过旋转来借节点的时分，会有三种状况：左左、左右、左左或左右，并且旋转完成后，都需求染色来维护性质，那咱们能够先处理一些特殊状况：左右，之后就能够共同当作左左的状况了

image-20221116151424606

  • 经过上面的处理后：

image-20221116151934447

  • LR的状况变成了LL，而有两个赤色孩子的状况左左或右右，本身就能够看做是LL
  • 所以能来到下面的剖析，必定都能够当作LL的状况

image-20221116153317504

  • 也便是需求旋转 + 染色
    • 由于是LL，所以将父节点右旋即可
    • 旋转后兄弟节点变成了新的中心节点，将中心节点承继旧父节点的色彩，再将中心节点的左右两头都染成黑色即可
  • 至于为什么要承继旧父节点的色彩，在上篇文章现已剖析过了，能够结合前面的内容，剖析剖析哟~
2、一个赤色的子节点也没有

image-20221112153839462

  • 最终一种状况，兄弟也借不了，只能向父节点求助了，也便是经过染色将父节点和兄弟节点兼并

image-20221117183049570

  • 实际上是经过染色解决的下溢，这儿就不多解说了
  • 还有一点值得注意的是：染色前，需求记载父节点的色彩
    • 假如原先是赤色，阐明父节点向下兼并后，父节点并不会产生下溢现象，不需求额外处理
    • 可是假如原先是黑色，本身就只要一个黑节点了，向下兼并后，父节点也将会出现下溢
  • 这儿的处理逻辑，便是将父节点作为被删去的节点，递归履行删去后的逻辑
  • 所以，当咱们将父节点传入afterRemove()办法之后，其间有一处需求调整：

image-20221117185652319

  • 由于咱们只是是将父节点作为被删去的节点，所以它履行代码前，左右子节点的引证必定不会发生变化，所以检查是否是左子节点，就得用曾经的办法

（3）对称状况的处理（被删去的节点在左面）

  • 在上面，咱们现已剖析且完成了被删去节点在右边的一切状况。真的谢了✌️✌️
  • 一向说它和在左面是对称的。详细有多对称呢？

image-20221117191313334

  • 看我标赤色的当地，便是交流左右即可
    • 左面取左，右边就变成取右
    • 左面右旋，右边就左旋
  • 当然，有些当地交流了也是相同的效果，就没有交流

（4）优化afterRemove()的参数

  • 看完了上面的完成，真的能够说是苦尽甘来啊！！！
  • 虽然完成了，咱们之前留了一个问题：afterRemove()办法中增加了一个参数

image-20221117192740571

  • 并且这个参数，在整个完成逻辑中，仅在这儿用到了

  • 还有在AVL树的完成中，其实也没有用到这个参数

  • 那咱们能否做到，不要这个参数，共同参数呢？

  • 最初多传这个参数，是想在红黑树这儿方便判别删去的是度为1的节点

  • 也便是需求找到用于替代删去节点的节点。其余的当地都不需求改动，只是需求处理上面代码的逻辑

  • 处理前，咱们先看看，在二叉查找树中，应该怎么传入参数，这是一个值得思考的问题

  • 先来看看度不是0的状况，改回之前的完成即可【箭头指向的是修正后的代码】

image-20221117200717357

  • 仅有要修正的便是下面度为1的节点

image-20221117200441200

  • 由于AVL树和红黑树共用了一个删去模板。所以在考虑传入红黑树的参数时，还得确保AVL树删去后的处理是正常的
  • 之前在完成AVL树的时分，这儿是将被删去节点node传入了afterRemove()办法
  • 而现在传入的是用于替代的child，那么咱们先看看AVL树的完成

image-20221117201420172

  • 能够发现，其实并没有影响，这儿需求拿到被删去节点的父节点就能够。而咱们在传入child的时分，本身就现已将被删去节点的父节点赋值给child.parent了，逻辑也不需求修正

  • 所以并不会产生影响，那红黑树中呢？

  • 咱们先来修正，再解说：

image-20221117195748292

  • 修正这儿，应该很好理解，由于传进来的就只要一个参数了
  • 便是将上面剖析的①②种状况，兼并成共同的逻辑了。看看注释的内容

（5）完好完成afterRemove(Node<E> node)

protected void afterRemove(Node<E> node) {
    /*
        ①、被删去的节点是赤色的状况
        ②、删去的节点有且仅有一个赤色的子节点【也便是在二叉查找树中删去的度为 1 的节点，找到替代它的子节点】
    */
    if (isRed(node)) {
        /*
            ①：假如被删去的节点是赤色的状况，将它染黑也不要紧，横竖它的内存马上就要释放掉了
            ②：将用于代替被删去节点的子节点染成黑色即可
         */
        black(node);
        return;
    }
    Node<E> parent = node.parent; // 取出被删去节点的父节点
    // ③、假如父节点是空的，阐明删去的是根节点
    if (parent == null) return;
    /*
        阐明曾经删去的是左面
        1、(parent.left == null)是被删去的节点
        2、(node.isLeftChild())是父节点下溢
    */
    boolean isLeft = parent.left == null || node.isLeftChild();
    // 左面为 null 阐明右边是兄弟节点，否则是左面
    Node<E> sibling = isLeft ? parent.right : parent.left;
    if (isLeft) { // 被删去的节点在左面，与下面的操作对称
        // 兄弟节点是赤色
        if (isRed(sibling)) { // 将其转化为兄弟节点是黑色的两种状况
            rotateLeft(parent); // 左旋，改换兄弟节点
            red(parent); // 父节点染成赤色
            black(sibling); // 兄弟节点染成黑色
            sibling = parent.right; // 兄弟节点变了，改动引证
        }
        // 能来到这儿，兄弟节点必定是黑色的了
        if (isRed(sibling.right) || isRed(sibling.left)) { // 兄弟至少有一个赤色的子节点
            if (isRed(sibling.left)) { // RL的状况，将其转化为RR，与下面共同处理
                rotateRight(sibling); // 兄弟节点右旋
                sibling = parent.right; // 兄弟节点变化了
            }
            // 能来到这儿，阐明都能够当作是RR的状况了
            rotateLeft(parent); // 将父节点左旋
            /*
                1、兄弟节点变成了新的父节点（新的中心节点）
                2、将新父节点的色彩承继旧父节点的色彩
                3、将新父节点的左右子节点都染成黑色
            */
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(sibling.right);
        } else { // 兄弟一个赤色的子节点都没有
            boolean isBlack = isBlack(parent); // 记载父节点原先的色彩
            // 将父节点染成黑色，兄弟节点染成赤色
            black(parent);
            red(sibling);
            if (isBlack) { // 假如父节点原先便是黑色的
                afterRemove(parent); // 阐明向下兼并后，它也会下溢，将它作为被删去的节点
            }
        }
    } else { // 被删去的节点在右边，与上面的操作对称
        // 兄弟节点是赤色
        if (isRed(sibling)) { // 将其转化为兄弟节点是黑色的两种状况
            rotateRight(parent); // 右旋，改换兄弟节点
            red(parent); // 父节点染成赤色
            black(sibling); // 兄弟节点染成黑色
            sibling = parent.left; // 兄弟节点变了，改动引证
        }
        // 能来到这儿，兄弟节点必定是黑色的了
        if (isRed(sibling.left) || isRed(sibling.right)) { // 兄弟至少有一个赤色的子节点
            if (isRed(sibling.right)) { // LR的状况，将其转化为LL，与下面共同处理
                rotateLeft(sibling); // 兄弟节点左旋
                sibling = parent.left; // 兄弟节点变化了
            }
            // 能来到这儿，阐明都能够当作是LL的状况了
            rotateRight(parent); // 将父节点右旋
            /*
                1、兄弟节点变成了新的父节点（新的中心节点）
                2、将新父节点的色彩承继旧父节点的色彩
                3、将新父节点的左右子节点都染成黑色
            */
            color(sibling, colorOf(parent));
            black(sibling.left);
            black(sibling.right);
        } else { // 兄弟一个赤色的子节点都没有
            boolean isBlack = isBlack(parent); // 记载父节点原先的色彩
            // 将父节点染成黑色，兄弟节点染成赤色
            black(parent);
            red(sibling);
            if (isBlack) { // 假如父节点原先便是黑色的
                afterRemove(parent); // 阐明向下兼并后，它也会下溢，将它作为被删去的节点
            }
        }
    }
}
  • 至此，终于将红黑树的删去剖析完成了
  • 假如你真的耐心的看到了这儿，那和我一同击个掌怎么样~ 🤚🤚🤚

写在后边

  • ✌️✌️✌️完好代码
  • 推荐阅览：
    • 了解二叉查找树 ->《二叉查找树的完成与剖析》
    • 了解树的旋转 ->《透过AVL树的完成，学习树的旋转》
    • 了解上溢现象 ->《你心里有B树吗？》
    • 红黑树的增加 ->《红黑树增加的剖析与完成》

本篇收获

  • 加强红黑树删去的剖析
  • 能够用代码完成红黑树的删去逻辑
  • 复习树的旋转、B树的性质、红黑树的性质