红黑树

在我学习数据结构和算法一段时间之后,就被灌输了二分查找的性能非常好的观念,确实,这也没什么毛病,毕竟 O(logn) 的复杂度确实已经很好了。那么,习惯得,我也将二叉树认为是查找元素的不二选择,好像这在通常情况下问题也不大。

但是,当理论遇到现实的时候,事情就变得有点糟糕了,例如二叉树的理想状态应该是平衡二叉树,也就是说对于每一个分支,左右子树的高度差最多就是一个,这样可以保证查找一个元素的时间复杂度是 O(logn)。事实上,这很难做到,我是说在不修正的情况下,要想让一棵二叉树随时保持平衡,那么我们就需要在增加或删除元素的时候做平衡处理,而这处理的代价经常都会是 O(logn)

为了在尽可能保持二叉树的优点的同时,又尽可能解决缺点,有很多类似的树型结构被发现,其中有 2-3树/AVL 树/红黑树/B树/B+树等等,每种都有其独特并且优异的地方,而在这篇文章中,我就以红黑树为例,温习一下红黑树的知识。

红黑树与AVL树的比较:

  1. AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
  2. 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;
  3. 所以简单说,如果你的应用中,搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。

红黑树的特点

一棵二叉查找树如果满足以下的红黑性质,那么这就是一棵红黑树

  1. 每个节点要么是红的,要么是黑的
  2. 根节点是黑的
  3. 每个叶节点(NULL)是黑的
  4. 如果一个节点是红的,那么它的两个儿子都是黑的
  5. 对于每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点

对第 4 个点稍作解释,其实可以说成是没有父子节点都是红的情况,但是,却可以存在父子节点都是黑的情况。

对于一棵红黑树来说,那么它一定满足这些性质,那么只有两种情况会破坏这些性质,那就是插入删除,所以我们需要做一些特别的操作来使 红黑树 能够继续满足条件。

插入节点

往一棵红黑树中插入一个节点时,我们要遵循一些规则:

  1. 插入的节点最开始一定是设置成红的
  2. 插入的节点的位置一开始一定是叶子节点的位置
  3. 只有当父节点的颜色也是红的时候,我们才需要考虑调整

这就是一棵简单的红黑树:

这里将元素4 插入到原来的红黑树中,所以,这里也就破坏红黑性质了,这也是唯一一种需要转换的情况,那就是父子节点都是红的。对于父子节点都是红的,我们需要考虑两种情况:

  • 新的节点在父节点的左树
  • 新的节点在父节点的右树

但是,处理这个问题,有时候很简单得完成,那就是第三种情况:

  • 父节点的兄弟节点也是红的

这个时候我们归纳一下,插入一个新元素的时候,红黑特性被破坏,我们有三种情况需要处理:

  • 父节点的兄弟节点也是红的
  • 新的节点在父节点的左子树
  • 新的节点在父节点的右子树

下面我们就对这三种情况一一解决。

父节点的兄弟节点也是红的

对于这种情况,我们上面的示例就恰恰是这样的:

这个时候因为 5 和 8 都是红的,所以我们可以这么操作:

  • 将 5 和 8 变为黑,然后将 7 变成红

即可,这样我们就让新插入的节点不会破坏 红黑性质 了,因为对于节点 7 来说,我们可以保证它到子节点中的黑节点个数不变,这样的话,整棵树的黑节点路径原则也不会被破坏。

变换之后就是:

但是,可以发现,父节点被变换颜色之后又和它的父节点产生了冲突,这个时候就不能通过变换兄弟节点的颜色来解决了。但是,我们可以发现,现在 2 和 7 的情况就是我们的另外一种情况:新的节点在父节点的右子树

新的节点在父节点的右子树

对于父节点的兄弟不是红色的,并且新的节点在父节点的左树的情况:

这就是刚才解决新插入节点之后的新情况,对节点 7 和节点 2 产生了冲突,这个时候我们需要解决。这里需要引入一个新的概念叫做旋转旋转包含左旋右旋,其实他们是对称操作:

所以这里需要利用 左旋 的操作,根据上图的指引,我们进行以节点 2 为根进行 左旋 后的结果是:

这个时候又遇到情况了,那就是节点 2 和节点 7 又冲突了并且就是最后一种情况:新的节点在父节点的左子树

新的节点在父节点的左子树

当遇到这种情况的时候,我们就要进行 右旋 操作,右旋操作有个前提就是

  • 将父节点设置为 Black
  • 将父节点的父节点设置为 Red
  • 右旋 父节点的父节点

右旋 之后的结果应该是:

这个时候可以发现这棵二叉查找树 已经满足了所有的 红黑性质,也就是说这又是一棵红黑树,也就是将插入操作调整完毕了。

插入小结

可以看到,这个简单的操作就涉及到了 3 种类型,其实过程中可能不止做一种类型的转换,还会涉及到 2 种或者 3 种类型的转换。

  1. 父节点的兄弟节点也是红的
    1. 将父节点和兄弟节点都改成黑的
    2. 将父节点的父节点改成红的
  2. 新的节点在父节点的右子树
    1. 左旋
  3. 新的节点在父节点的右子树
    1. 将父节点设置为 Black
    2. 将父节点的父节点设置为 Red
    3. 右旋父节点的父节点

删除节点

红黑树中的删除和普通二叉查找树的删除差不多,也就多了一项红黑节点调整。所以假设我们先不考虑红黑调整,那么删除一个节点就是:

这就是一个普通的删除二叉查找树的步骤,其中 tree_successor 就是搜索下一个用来替换当前节点的值,这里需要说明的是这个被用来替换的值肯定是叶子节点,或者说只有右子树的节点,没有其他情况。然后我们所谓的删除就是将两个值调换,将替换的值删掉。

现在是时候考虑一下红黑平衡了,考虑一下,什么时候需要红黑平衡?根据这里的代码,我们可以发现真正被删除的是 y,所以,有两种情况需要考虑:

  • y 是红色的,那么删除红色节点之后,并不会影响后续节点路径中黑色节点的个数,也不会导致两个红色节点成为父子节点,那么也就是说是安全的,无需红黑平衡了。
  • y 是黑色的,那么这个时候被删除了,和 y 有关的路径就少了一个黑色节点,那么我们可以考虑将这个黑色节点下移,转给 y 的儿子 x,也就是说 x 必须承担一个黑色。

这个时候又需要考虑两种情况了,对于 x 来说,也有两种可能,那就是:

  • x 是红色的,那么我们直接将 x 转变为黑色,那么整个路径上黑色节点的个数也平衡了,而且也不会有两个红色成为父子节点,就成功了。
  • x 是黑色的,那么显然不能再提供一个黑色,那么只能继续迁移,需要记住,此时 x 承担了 2 个黑色的责任,需要找人承担一个

对于 x 需要承担 2 个黑色的情况,我们有几种情况要考虑:

  1. x 的兄弟 w 是红色的

    那么对于这种情况,我们可以考虑进行一个左旋,然后再改变一下兄弟节点的颜色:

    这里考虑将 节点D 进行一个左旋,那么旋转之后的结果就是:

    我们将 B/D 的颜色进行一个转换,然后我们需要注意的是 x 对应的节点也还必须承担多一个黑色,然而这个 x 已经是黑色了,所以还得转接,但是,很明显,兄弟节点不是红色了,不能旋转了,那我们就需要考虑另外一种情况了。

  2. x 的兄弟 w 是黑色的,而且 w 的两个孩子都是黑色的

    因为 x 不能承担多一个黑色,所以我们考虑 w 的情况,首先考虑 w 有两个孩子,并且两个孩子都是黑色的,那么就是这样子的:

    rb-case2-01.png

    对于这种情况,我们可以将 节点D 的颜色变为红色,这样的话可以发现左右都差一个黑色,那么我们就将这差的一个黑色让 父节点c 承担,虽然图示中 父节点c 的颜色是红色的,但是事实上红黑都有可能:

    • 如果是红色,那么直接变成黑色就大功告成了
    • 如果是黑色,那么就需要多贡献一个黑色,如果不能贡献,那只能继续根据各种情况递归下去

      所以变换之后应该是这样的:

      rb-case2-02.png

  3. x 的兄弟 w 是黑色的,而且 w 的左子节点是红色,右子节点是黑色

    这种情况我们可以用图示来表示:

    rb-case3-01.png

    对于这种情况,我们不能一次性迁移 节点x 的状态,那只能退而求其次,找出一个中间状态,构建这个中间状态:

    rb-case3-02.png

    这里讲 节点C 的位置提升为父节点,然后将原来的 父节点D 将为 节点C 的子节点,并且改变为红色,然后我们再讨论这种情况。

  4. x 的兄弟 w 是黑色的,并且 w 的右子节点是红色

    这里我们可以发现我们只关注 节点w 的右子节点,并且为红色即可,不需要关注左子节点,这个时候我们可以这样表示这个图:

    rb-case4-01.png

    这时,我们可以将 节点D 左旋,然后就得到了这种情况:

    rb-case4-02.png

    这里有几点地方需要指出来:

    1. 原来 节点w 的右节点E 变成了 Black
    2. 原来 节点D 的颜色变成了 节点B 的颜色
    3. 父节点B 的颜色一定变成 Black

      这时,我们再看这张图,会发现 x 不见了,也就是说没有任何节点需要多提供一个黑色,也就是说我们这棵红黑树平衡了。

以上就是我们需要考虑的删除一个节点之后红黑不平衡的问题了,其实核心要点就是记住 变量x 就是表示这个节点需要多提供一个黑色,所以当 x 是 Root 或者是红色的时候,那么我们就成功了,因为:

  • 如果 root 需要提供多一个黑色,那么其实完全就不用多提供了,因为 root 无父节点需要平衡。
  • 如果是红色节点需要提供多一个黑色,那么尽管把它变成黑色好了,因为把它变成黑色不会影响我们的红黑特性,最可能影响到的一条特性就是任何路径上的黑色节点数一样,但是因为包含这个节点的路径都少了一个,所以尽管变成黑色就可以了。

小结

红黑树的目的就是尽可能保持二叉搜索树的平衡,保证二叉搜索树的搜索速度,同时又要提高插入元素的速度,所以红黑树要设立红黑特性,保证在这两方面之间得到权衡。和 AVL 树相比:

  • 如果你的插入和搜索频率差不多,那么就用 红黑树
  • 如果插入远远少于查询,那么用 AVL树 划算

Reference

  1. 算法导论
  2. 教你透彻了解红黑树
  3. 二叉树可视化工具

· EOF ·

最近爬虫很是凶猛,标注下文章的原文地址: https://liuliqiang.info/post/red-black-tree/