红黑树 | 我就是马云飞

红黑树和平衡二叉树的思想是类似的，都是在插入过程中对二叉排序树进行调整，从而提升性能，它的增删改查均可以在O(lg n)内完成。

定义

红黑树是一棵二叉排序树。且满足以下特点：

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图就是一棵简单的红黑树示例：

示例中每个结点最后都是一个NIL结点，它是黑色的，不过我们画图时通常会省略它。所以下文以及后续文章中绘制时都会省略NIL结点，大家记得还有它就可以。

实现原理

红黑树的插入与删除和AVL树类似，也是每插入一个结点，都检查是否破坏了树的结构，然后进行调整。红黑树每个结点插入时默认都为红色，这样做可以降低黑高，也可以减少调整的次数。

插入元素

红黑树的概念理解起来较为复杂，我们以一个简单的示例，看看如何构造一棵红黑树。

现有数组int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6};我们要将其变为一棵红黑树。

首先插入1，此时树是空的，1就是根结点，根结点是黑色的：

然后插入元素10，此时依然符合规则，结果如下：

当插入元素9时，这时是需要调整的第一种情况，结果如下：

红黑树规则4中强调不能有两个相邻的红色结点，所以此时我们需要对其进行调整。调整的原则有多个相关因素，这里的情况是，父结点10是其祖父结点1（父结点的父结点）的右孩子，当前结点9是其父结点10的左孩子，且没有叔叔结点（父结点的兄弟结点），此时需要进行两次旋转，第一次，以父结点10右旋：

然后将父结点（此时是9）染为黑色，祖父结点1染为红色，如下所示：

然后以祖父结点1左旋：

下一步，插入元素2，结果如下：

此时情况与上一步类似，区别在于父结点1是祖父结点9的左孩子，当前结点2是父结点的右孩子，且叔叔结点10是红色的。这时需要先将叔叔结点10染为黑色，再进行下一步操作，具体做法是将父结点1和叔叔结点10染为黑色，祖父结点9染为红色，如下所示：

由于结点9是根节点，必须为黑色，将它染为黑色即可：

下一步，插入元素3，如下所示：

这和我们之前插入元素10的情况一模一样，需要将父结点2染为黑色，祖父结点1染为红色，如下所示：

然后左旋：

下一步，插入元素8，结果如下：

此时和插入元素2有些类似，区别在于父结点3是右孩子，当前结点8也是右孩子，这时也需要先将叔叔结点1染为黑色，具体操作是先将1和3染为黑色，再将祖父结点2染为红色，如下所示：

此时树已经平衡了，不需要再进行其他操作了，现在插入元素7，如下所示：

这时和之前插入元素9时一模一样了，先将7和8右旋，如下所示：

然后将7染为黑色，3染为红色，再进行左旋，结果如下：

下一步要插入的元素是4，结果如下：

这里和插入元素2是类似的，先将3和8染为黑色，7染为红色，如下所示：

但此时2和7相邻且颜色均为红色，我们需要对它们继续进行调整。这时情况变为了父结点2为红色，叔叔结点10为黑色，且2为左孩子，7为右孩子，这时需要以2左旋。这时左旋与之前不同的地方在于结点7旋转完成后将有三个孩子，结果类似于下图：

这种情况处理起来也很简单，只需要把7原来的左孩子3，变成2的右孩子即可，结果如下：

然后再把2的父结点7染为黑色，祖父结点9染为红色。结果如下所示：

此时又需要右旋了，我们要以9右旋，右旋完成后7又有三个孩子，这种情况和上述是对称的，我们把7原有的右孩子8，变成9的左孩子即可，如下所示：

下一个要插入的元素是5，插入后如下所示：

有了上述一些操作，处理5变得十分简单，将3染为红色，4染为黑色，然后左旋，结果如下所示：

最后插入元素6，如下所示：

又是叔叔结点3为红色的情况，这种情况我们处理过多次了，首先将3和5染为黑色，4染为红色，结果如下：

此时问题向上传递到了元素4，我们看2、4、7、9的颜色和位置关系，这种情况我们也处理过，先将2和9染为黑色，7染为红色，结果如下：

最后7是根结点，染为黑色即可，最终结果如下所示：

可以看到，在插入元素时，叔叔结点是主要影响因素，待插入结点与父结点的关系决定了是否需要多次旋转。可以总结为以下几种情况：

如果父结点是黑色，插入即可，无需调整。
如果叔叔结点是红色，就把父结点和叔叔结点都转为黑色，祖父结点转为红色，将不平衡向上传递。
如果叔叔结点是黑色或者没有叔叔结点，就看父结点和待插入结点的关系。如果待插入结点和父结点的关系，与父结点与祖父结点的关系一致，比如待插入结点是父结点的左孩子，父结点也是祖父结点的左孩子，就无需多次旋转。否则就先通过相应的旋转将其关系变为一致。