红黑树

前言
红黑树特性
树的旋转
- 旋转的轴
红黑树插入数据

前言

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

在JAVA中，许多跟排序有关的实现类都涉及到红黑树，最典型的如TreeMap。

本文主要就红黑树的特性和红黑树在插入和删除元素时的变化过程做详细的说明，以便帮助读者理解红黑树，当然，也方便自己记忆和查阅。

红黑树特性

红黑树有5个特性：

特性一：节点是红色或者是黑色；
特性二：根节点是黑色；
特性三：每个叶节点（NIL或空节点）是黑色；
特性四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；
特性五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点；

在谈红黑树节点的插入和删除前，必须先彻底理解这五个特性。

特性一：节点是红色或者是黑色

这个特性其实非常好理解，就是树中的每个节点不是红色就是黑色，这也是红黑树的命名原因。这里的节点是红色和黑色只是为了表明两种不同颜色的节点，实际上只是用来区分不同作用的节点而已，你也可以用蓝色和黄色来标明，所以不需要纠结为什么是红色和黑色。

这个特性跟红黑树调整过程没有关系，基本不会被破坏，是最容易保持的。

特性二：根节点是黑色

根节点是黑色，这个特性实际上是一个比较自然的选择，可以提高红黑树在变化过程保持所有特性的性能，实际上即使没有这个特性，红黑树也是能成立的，只是作为一个特性定义了根节点的颜色而已。

这个特性在红黑树调整过程可能被破坏：

在红黑树变化调整的过程中，有可能出现根节点的两个子节点都是黑色的情况，此时依然保持根节点为黑色即可。
在红黑树变化调整的过程中，也有可能出现根节点被调整成红色，同时根节点的两个子节点都是黑色的情况，此时也要将根节点调整为黑色。

特性三：每个叶节点（NIL或空节点）是黑色

这个特性可能看图会比较直观：

红黑树

从这里我们可以看到，所有叶子节点都是NIL，也就是空节点，并且都是黑色的。

在红黑树插入节点的过程中，插入的节点一定会替换已有的某个NIL节点，并且插入的节点也会同时自动附带左右两个NIL节点。

这个特性也是很好保持的，因为只要下面某个节点下面没有节点了，就等于有两个空节点，插入一个新节点时，肯定是成为某个节点的子节点，自然会替换掉原本为空的那个节点。

特性四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）

这个特性指的是每一个红色的节点，它的两个子节点都不能是红色，也就是从根节点到叶子节点（NIL节点）的所有路径中，不会出现连续的红色节点。

这个特性非常容易被破坏，多数情况下插入节点和删除节点都会破坏这个特性。

特性五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点

这个特性也不是很好理解，如图：

红黑树

这里我们看到，从根节点开始，无论通过哪条路径到达NIL节点，经过的黑色节点数（包括NIL节点）是相同的，如：

13 -> 8 -> 1 -> NIL
13 -> 17 -> 25 -> 27 -> NIL
这两条路径，经过的黑色节点数都是3个，其他路径也必然都是3个。

这个特性也是非常容易被破坏的，多数情况下插入节点和删除节点都会破坏这个特性。

总结

从上面的特性我们可以总结如下几点：

总结一：特性一，二，三非常容易保持，在插入节点时，基本不会被破坏
总结二：黑色节点的两个子节点可以是黑色的，也就是从根节点到叶子节点（NIL节点）的路径中，可以出现连续的黑色节点；
总结三：插入节点时，如果新节点是黑色的，必然会破坏特性五，如果是红色的，则必然不会破坏规则五，但是有可能破坏规则四；

树的旋转

在对数进行插入和删除操作时，很容易破坏红黑树原有的特性，尤其是特性四和特性五，因此在插入或删除某个节点后，为了保持这些特性，需要调整红黑树的指针结构，以便保持红黑树的特性，这个修改的过程一般是通过树的旋转来完成的。

树的旋转包含两种：

左旋

右旋

左旋是以根节点为轴，逆时针旋转，右旋是以根节点为轴，顺时间旋转，为方便记忆，可以记住左逆右顺即可。

旋转的轴

我们一般说树的旋转，都是指以树的根节点作为转轴进行旋转，当然，这个树可能是某个树的子树，如下图：

子树旋转

这里A2子树进行右旋时，是以A2节点为根的树，会以A2节点为轴进行旋转。
A树进行左旋时，是以A节点为根的树，会以A节点为轴进行旋转。

值得注意的是，很多时候，红黑树的特性被破坏后，并不能通过一次旋转来修复特性，在修复特性过程中，有可能需要多次并且对不同的子树进行旋转。

红黑树插入数据

这里为了方便看，我们重新贴一下红黑树的五个特性和根据特性得出的三个总结：

特性一： 节点是红色或者是黑色；

特性二： 根节点是黑色；

特性三： 每个叶节点（NIL或空节点）是黑色；

特性四： 每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；

特性五： 从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点；

总结一： 特性一，二，三非常容易保持，在插入节点时，基本不会被破坏

总结二： 黑色节点的两个子节点可以是黑色的，也就是从根节点到叶子节点（NIL节点）的路径中，可以出现连续的黑色节点；

总结三： 插入节点时，如果新节点是黑色的，必然会破坏特性五，如果是红色的，则必然不会破坏规则五，但是有可能破坏规则四；

红黑树插入数据时，遵循如下规则：

插入节点必须是红色
插入节点时，如果父节点是黑色，则不破坏所有特性，不需要调整红黑树
插入节点时，如果父节点是红色，则破坏特性四，需要调整红黑树

这里，插入节点必须是红色其实是一个比较自然的选择，根据总结三，我们知道，如果插入节点是红色，有可能不会破坏所有规则，不需要对树进行调整，如果插入节点是黑色，则一定需要对树进行调整，所以尽量选择不需要调整的方案，自然就会设置为红色。

现在我们假设已有的一棵红黑树如下：

红黑树

假设我们插入的节点是Z

下面我们分如下情况来讨论插入节点后的如何调整：

情况1： 父节点是黑色；
情况2： 父节点是红色；
- 情况2.1： 叔节点是红色；
- 情况2.2： 叔节点是黑色；

情况1：父节点是黑色

如果Z插入的位置正好如下：

红黑树

这时我们看到的真个红黑树特性没有被破坏，因此树不用进行调整。

情况2：父节点是红色

如果插入节点的父节点是红色，则特性四必然被破坏，此时需要调整红黑树，但是这个时候我们需要根据新节点的叔节点的颜色来决定如何调整。

情况2.1：叔节点是红色

如果Z插入的位置如下：

红黑树

这个时候我们发现，整个树的特性四被破坏了。

我们从整个树的根节点往下搜索，找到的第一个破坏特性的节点作为参照节点，这个节点就是Z。

实际上也可以从修改的节点（Z）往根搜索第一个破坏特性的节点，是4节点，那么4节点的前一个节点（Z）就是参照节点。

此时观察Z节点的叔节点，正好是红色，那么做如下调整：

把Z节点的叔节点和父节点都涂成黑色，并把5节点涂成红色即可：

红黑树

实际上，如果只是为了保持特性四（每个红色节点的两个子节点都是黑色的），只涂黑节点4即可，但是这样同时会破坏特性五（从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点）, 所以不能只涂黑4节点。

现在我们看到10节点子树破坏了特性四，继续从根节点往下搜索，第一个破坏特性的节点是5节点。

实际上也可以从修改的节点（5节点）往根搜索第一个破坏特性的节点，是10节点，那么10节点的前一个节点（5节点）就是参照节点。

那么我们观察5节点的叔节点（50节点），也是红色，那么继续将10节点和50节点涂黑，将15节点涂红（实际上由于15节点是根节点，为了保证特性二，不涂红）：

红黑树

此时发现已经满足红黑树的所有特性了，调整完成。

注意：从这里也可以看出，实际上红黑树并不是平衡树，但是红黑树是接近平衡的树，也就是说，可以用红黑树来实现平衡树。

情况2.2：叔节点是黑色

叔节点是黑色节点时，情况会稍微复杂一些，因为直接涂红参考节点的父节点，会破坏特性五（从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点），因此不能通过涂色来满足特性四（每个红色节点的两个子节点都是黑色的）。

我们假设一个已有的红黑树如下：

红黑树

插入节点Z的位置如下：

红黑树

此时我们发现新节点的叔节点（3节点的右子节点）是一个空节点，根据特性三（每个叶节点【NIL或空节点】是黑色），可以知道此时叔节点是黑色的，因此修改颜色后会导致破坏特性五（从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点），要再通过旋转来调整树满足特性五。