面试之必掌握知识点：红黑树（二）

面试之必掌握知识点：红黑树（二）

面试之必掌握知识点：红黑树（二）

1. 红黑树的定义2. 如何将2-3-4转变为红黑树3. 红黑树的插入4. 红黑树的删除5. 红黑树的变种
前面我们学习了2-3树和2-3-4树的基本定义和基本 *** 作。现在我们继续前进攻克红黑树！有了前面的基础和原理的支持，我们就能更加容易的理解红黑树各种旋转以及染色等 *** 作，而不用再去死记硬背。话不多说开整~

1. 红黑树的定义

每个节点要么是红色要么是黑色根节点是黑色所有的叶子节点都是黑色。红色节点的子节点一定是黑色的（不能有连续的红色节点）从任一节点到其每个叶子节点的路径所包含的黑色节点数目都相同。

（注意红黑树的叶子节点通常都是空指针，并不保存具体的值，在之后的图中我们会用一个黑色的小点代替，在变换的过程会忽略他们，并且视他们的有值的父节点为逻辑上的叶子节点）

看完了定义后，你一定感觉有点发懵，这红黑树的定义和2-3树,2-3-4树有什么关系呢？掌握了2-3树,2-3-4树，我还是看不懂红黑树的变换？别着急，咱们逐一来分析一下，看看2-3树2-3-4树和红黑树的共同之处。

2. 如何将2-3-4转变为红黑树

2-3-4树中的2节点对应红黑树中的黑色节点，且黑色节点的子节点也全部为黑色。
2-3-4树中的3节点对应红黑树中的黑色节点，且黑色节点的子节点只有一个为黑色。
2-3-4树中的4节点对应红黑树中的黑色节点，且黑色节点的子节点全部都是红色的。

（注：在本篇中，红黑树中希腊字母部分代表黑色的子节点）

看到这里我们就能发现两棵树之间的关联：

红黑树中的黑色节点代表2-3-4树中的一个新节点。红黑树中的红色节点和它的黑色父节点在2-3-4树中属于同一个节点中的不同元素。红黑树中一条路径上的黑色节点有多少个，就代表着2-3-4树一共有多少层。

了解了2种树之间的关联我们再具体看一下，红黑色在插入和删除的过程中是怎么由2-3-4树转换过去的？

3. 红黑树的插入

红黑树在插入的过程中的规则如下：

每次新插节点都是红色的，对比2-3-4树，每次都是优先往现有节点中插入元素，如果节点中的元素超过了3个再去分裂。红黑树中如果新插入的红色节点违反了红黑树的定义和规则，再去进行染色和旋转。如果新插入的节点的父节点为红色，且父亲的兄弟节点也为红色则需要重新染色（等同于2-3-4树中的分裂）。

前面我们提到 "红色节点和它黑色的父节点在2-3-4树中属于同一个节点中的不同元素 "。上图左侧这4个节点在2-3-4树中就属于同一个节点的4个元素，超出了上限，所以需要分裂。2-3-4中分裂后的效果入下图：
如果新插入的节点的父节点为红色，且父亲的兄弟节点为黑色则需要进行旋转。

上图中xyz 3个元素没有超出2-3-4树中单个节点的上限，所以不需要分裂，但是由于规定红黑树中不能连续有两个红色节点直接相连，所以我们需要旋转红黑树。这里的2-3-4树则不需要进行进行任何变换。上面画出了两种需要旋转的情况。

下面我们用一个例子来展示红黑树插入的完整步骤：

插入2-3-4树step1红黑树step 1step 252611310

最后我们比较和总结一下红黑树和2-3-4树的异同。在红黑树中染色的步骤等同于2-3-4树中的分裂，另外如果红黑树中的根节点染色后是红色，需要将根节点变成黑色，这一步在2-3-4树中的意义等于根节点分裂后新增一层（新的根节点）。而红黑树中的旋转是红黑树仅有的。只有新插入的节点的父节点为红色，且父亲的兄弟节点为黑色才需要进行旋转。

4. 红黑树的删除

在红黑树插入的章节中我们详细的对比了2-3-4树与红黑树的异同以及关联，红黑树的删除原理基本也是一样的，是否染色也是基于2-3-4的分裂。旋转基于红黑树2个红色节点不能相连的定义。

case 1: 如果删除的节点不是叶子节点，则也是先找到后继的较大节点去替代，然后再从替代后的位置来删除。如果替代后为叶子节点跳到case 2/case3。否则继续执行case 1，直到删除的节点为叶子节点。case 2: 如果删除的节点是红色的叶子节点，则直接删除。case 3: 如果删除的节点是黑色的叶子节点，这个情况比较复杂了，类似2-3-4中删除掉一个节点后需要填补空位。直接变换红黑树比较复杂，我们可以采用比较好理解的办法，先从红黑树转换2-3-4树，等删除后再转换回红黑树。

case 1 和 case 2都比较好理解，case 3我们将通过一个完整的 *** 作图来看看把变换的细节：

上图红黑树转变成2-3-4树的样子

如果删除元素222，因为该节点只有222一个元素，所以需要从兄弟节点借一个元素：

再转变为红黑树：

如果继续删除元素260，因为兄弟节点只有一个元素，所以需要合并兄弟节点和父节点。（参考上一篇2-3树/2-3-4树删除的的具体 *** 作）

再转变为红黑树：

5. 红黑树的变种

关于红黑树还有一些变种比如，左倾红黑树，右倾红黑树等等。这里我们简单讲一下左倾红黑树：左倾红黑树如果一个节点只有一个红色子节点，那这个红色子节点一定是左边。要做到这一点也比较简单，只需要2-3-4树的3节点在转换为红黑树过程中，将2个元素中较大的元素转换为黑色父节点，较小的元素转换为红色左子节点即可。
例如：

转换为：

总的来说只要理解了2-3树和2-3-4树的 *** 作，再理解红黑树的染色和变换就会轻而易举。好啦！红黑树到这里就结束了，希望可以为大家的面试带来帮助！