本文最后更新于:1 年前

红黑树是一个让人又爱又恨的数据结构,“爱”是因为它稳定、高效的性能,“恨”是因为实现起来实在太难了。下面的红黑树的实现,理解起来可能会有些困难。但是,我觉得没必要去死磕它。

因为,即便你将左右旋背得滚瓜烂熟,保证你过不几天就忘光了。因为,学习红黑树的代码实现,对于你平时做项目开发没有太大帮助。对于绝大部分开发工程师来说,这辈子你可能都用不着亲手写一个红黑树。除此之外,它对于算法面试也几乎没什么用,一般情况下,靠谱的面试官也不会让你手写红黑树的。

如果你对数据结构和算法很感兴趣,想要开拓眼界、训练思维,还是很推荐你看一看这篇的内容。但是如果学完今天的内容你还觉得懵懵懂懂的话,也不要纠结。要有的放矢去学习。你先把平时要用的、基础的东西都搞会了,如果有余力了,再来深入地研究这节内容。

上一篇讲到红黑树定义的时候,提到红黑树的叶子节点都是黑色的空节点。当时只是粗略地解释了,这是为了代码实现方便,那更加确切的原因是什么呢?

实现红黑树的基本思想

实际上,红黑树的平衡过程跟魔方复原非常神似,大致过程就是:遇到什么样的节点排布,就对应怎么去调整。只要按照这些固定的调整规则来操作,就能将一个非平衡的红黑树调整成平衡的。

还记得红黑树的定义吗?回顾一下。一棵合格的红黑树需要满足这样几个要求:

  • 根节点是黑色的;
  • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
  • 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点。

在插入、删除节点的过程中,第三、第四点要求可能会被破坏,而“平衡调整”,实际上就是要把被破坏的第三、第四点恢复过来。
有两个非常重要的操作,左旋rotate left)、右旋rotate right)。左旋全称其实是叫围绕某个节点的左旋,那右旋的就叫围绕某个节点的右旋
image.png
红黑树的插入、删除操作会破坏红黑树的定义,具体来说就是会破坏红黑树的平衡,所以,现在就来看下,红黑树在插入、删除数据之后,如何调整平衡,继续当一棵合格的红黑树的。

插入操作的平衡调整

红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。所以,关于插入操作的平衡调整,有这样两种特殊情况:

  • 如果插入节点的父节点是黑色的,那就什么都不用做,它仍然满足红黑树的定义。

  • 如果插入的节点是根节点,那就直接改变它的颜色,把它变成黑色就可以了。

除此之外,其他情况都会违背红黑树的定义,于是就需要进行调整,调整的过程包含两种基础的操作:左右旋转改变颜色

红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理,而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入之后,如果红黑树的平衡被打破,那一般会有下面三种情况:

CASE 1:如果关注节点是 a,它的叔叔节点 d 是红色,就依次执行下面的操作:

  • 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色;
  • 将关注节点 a 的祖父节点 c 的颜色设置成红色;
  • 关注节点变成 a 的祖父节点 c
  • 跳到 CASE 2 或者 CASE 3
    image.png

CASE 2:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的右子节点,就依次执行下面的操作:

  • 关注节点变成节点 a 的父节点 b
  • 围绕新的关注节点 b 左旋;
  • 跳到 CASE 3
    image.png

CASE 3:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的左子节点,就依次执行下面的操作:

  • 围绕关注节点 a 的祖父节点 c 右旋;
  • 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
  • 调整结束。
    image.png

删除操作的平衡调整

删除操作的平衡调整分为两步,第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后,仍然满足最后一条定义的要求,也就是说,每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;第二步是针对关注节点进行二次调整,让它满足红黑树的第三条定义,即不存在相邻的两个红色节点。

1. 针对删除节点初步调整

这里需要注意一下,红黑树的定义中“只包含红色节点和黑色节点”,经过初步调整之后,为了保证满足红黑树定义的最后一条要求,有些节点会被标记成两种颜色,“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”,那在计算黑色节点个数的时候,要算成两个黑色节点。

CASE 1:如果要删除的节点是 a,它只有一个子节点 b,那就依次进行下面的操作:

  • 删除节点 a,并且把节点 b 替换到节点 a 的位置,这一部分操作跟普通的二叉查找树的删除操作一样;
  • 节点 a 只能是黑色,节点 b 也只能是红色,其他情况均不符合红黑树的定义。这种情况下,把节点 b 改为黑色;
  • 调整结束,不需要进行二次调整。
    image.png

CASE 2:如果要删除的节点 a 有两个非空子节点,并且它的后继节点就是节点 a 的右子节点 c。就依次进行下面的操作:

  • 如果节点 a 的后继节点就是右子节点 c,那右子节点 c 肯定没有左子树。把节点 a 删除,并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异;
  • 然后把节点 c 的颜色设置为跟节点 a 相同的颜色;
  • 如果节点 c 是黑色,为了不违反红黑树的最后一条定义,给节点 c 的右子节点 d 多加一个黑色,这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”;
  • 这个时候,关注节点变成了节点 d,第二步的调整操作就会针对关注节点来做。
    image.png

CASE 3:如果要删除的是节点 a,它有两个非空子节点,并且节点 a 的后继节点不是右子节点,就依次进行下面的操作:

  • 找到后继节点 d,并将它删除,删除后继节点 d 的过程参照 CASE 1
  • 将节点 a 替换成后继节点 d
  • 把节点 d 的颜色设置为跟节点 a 相同的颜色;
  • 如果节点 d 是黑色,为了不违反红黑树的最后一条定义,给节点 d 的右子节点 c 多加一个黑色,这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”;
  • 这个时候,关注节点变成了节点 c,第二步的调整操作就会针对关注节点来做。
    image.png

2. 针对关注节点进行二次调整

经过初步调整之后,关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点,再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

CASE 1:如果关注节点是 a,它的兄弟节点 c 是红色的,就依次进行下面的操作:

  • 围绕关注节点 a 的父节点 b 左旋;
  • 关注节点 a 的父节点 b 和祖父节点 c 交换颜色;
  • 关注节点不变;
  • 继续从四种情况中选择适合的规则来调整。
    image.png

CASE 2:如果关注节点是 a,它的兄弟节点 c 是黑色的,并且节点 c 的左右子节点 de 都是黑色的,就依次进行下面的操作:

  • 将关注节点 a 的兄弟节点 c 的颜色变成红色;
  • 从关注节点 a 中去掉一个黑色,这个时候节点 a 就是单纯的红色或者黑色;
  • 给关注节点 a 的父节点 b 添加一个黑色,这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”;
  • 关注节点从 a 变成其父节点 b
  • 继续从四种情况中选择符合的规则来调整。
    image.png

CASE 3:如果关注节点是 a,它的兄弟节点 c 是黑色,c 的左子节点 d 是红色,c 的右子节点 e 是黑色,就依次进行下面的操作:

  • 围绕关注节点 a 的兄弟节点 c 右旋;
  • 节点 c 和节点 d 交换颜色;
  • 关注节点不变;
  • 跳转到 CASE 4,继续调整。
    image.png

CASE 4:如果关注节点 a 的兄弟节点 c 是黑色的,并且 c 的右子节点是红色的,就依次进行下面的操作:

  • 围绕关注节点 a 的父节点 b 左旋;
  • 将关注节点 a 的兄弟节点 c 的颜色,跟关注节点 a 的父节点 b 设置成相同的颜色;
  • 将关注节点 a 的父节点 b 的颜色设置为黑色;
  • 从关注节点 a 中去掉一个黑色,节点 a 就变成了单纯的红色或者黑色;
  • 将关注节点 a 的叔叔节点 e 设置为黑色;
  • 调整结束。
    image.png

总结

“红黑树一向都很难学”,有这种想法的人很多。但其实主要原因是,很多人试图去记忆它的平衡调整策略。实际上,只需要能看懂上面的过程,没有知识盲点,就算是掌握了这部分内容了。毕竟实际的软件开发并不是闭卷考试,当你真的需要实现一个红黑树的时候,可以对照着上面的步骤,一点一点去实现。

现在就来总结一下,如何比较轻松地看懂上面的操作过程。

第一点,把红黑树的平衡调整的过程比作魔方复原,不要过于深究这个算法的正确性。只需要明白,只要按照固定的操作步骤,保持插入、删除的过程,不破坏平衡树的定义就行了。

第二点,找准关注节点,不要搞丢、搞错关注节点。因为每种操作规则,都是基于关注节点来做的,只有弄对了关注节点,才能对应到正确的操作规则中。在迭代的调整过程中,关注节点在不停地改变,所以,这个过程一定要注意,不要弄丢了关注节点。

第三点,插入操作的平衡调整比较简单,但是删除操作就比较复杂。针对删除操作,有两次调整,第一次是针对要删除的节点做初步调整,让调整后的红黑树继续满足第四条定义,“每个节点到可达叶子节点的路径都包含相同个数的黑色节点”。但是这个时候,第三条定义就不满足了,有可能会存在两个红色节点相邻的情况。第二次调整就是解决这个问题,让红黑树不存在相邻的红色节点。

思考

  • 为什么红黑树的定义中,要求叶子节点是黑色的空节点?

    之所以有这么奇怪的要求,其实就是为了实现起来方便。只要满足这一条要求,那在任何时刻,红黑树的平衡操作都可以归结为刚刚讲的那几种情况。

    还是有点不好理解,通过一个例子来解释一下。假设红黑树的定义中不包含刚刚提到的那一条“叶子节点必须是黑色的空节点”,往一棵红黑树中插入一个数据,新插入节点的父节点也是红色的,两个红色的节点相邻,这个时候,红黑树的定义就被破坏了。那应该如何调整呢?
    image.png
    你会发现,这个时候,前面讲的插入时,三种情况下的平衡调整规则,没有一种是适用的。但是,如果把黑色的空节点都给它加上,变成下面这样,你会发现,它满足 CASE 2 了。
    image.png
    你可能会说,可以调整一下平衡调整规则啊。比如把 CASE 2 改为“如果关注节点 a 的叔叔节点 b 是黑色或者不存在,a 是父节点的右子节点,就进行某某操作”。当然可以,但是这样的话规则就没有原来简洁了。

    你可能还会想,这样给红黑树添加黑色的空的叶子节点,会不会比较浪费存储空间呢?答案是不会的。实际上,在具体实现的时候,只需要像下面这样,共用一个黑色的、空的叶子节点就行了。
    image.png

  • 如果你以前了解或者学习过红黑树,关于红黑树的实现,你是怎样来学习的?在学习的过程中,有过什么样的心得体会?有没有什么好的学习方法?

欢迎留言和我分享。



欢迎关注我的公众号😘