引言

红黑树（R-B Tree）是一种自平衡的、高效的二叉查找树，是由Rudolf Bayer于1978年发明。红黑树可以在 时间内完成查找、增加、删除等操作过程，因此应用非常广泛，例如C++ STL中map，Linux内核中CFS进程调度算法均是基于红黑树结构实现的。

红黑树的定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树，具有以下性质：

• 根结点必须是黑色。
• 每个结点要么是黑色，要么是红色。
• 所有叶子结点都是黑色（叶子是NIL结点）。
• 每个红色结点的两个子节点一定都是黑色。
• 任意结点到每个叶子结点的路径都包含数量相同的黑结点。

图1就是标准的红黑树，具有上面5个性质。二叉树的查找效率取决于树的高度，通过这几个性质可以避免二叉查找树退化成单链表的极端情况。性质4和性质5保证任意结点到其每个叶子结点最长路径不会超过最短路径的2倍。红黑树中不可能同时存在两个连续的红结点，但可以存在两个连续的黑结点。

红黑树并不是一个完美的平衡二叉树，左子树和右子树可以不等高，但是左子树和右子树的黑结点的层数是相等的（性质5），所以红黑树这种性质称为黑色完美平衡。

插入操作

红黑树的插入操作包括两部分：1）查找插入的位置；2） 插入后自平衡。查找插入位置和二叉查找树的插入过程一样，步骤如下：

• 从根结点开始查找；
• 若根结点为空，那么插入结点作为根结点，结束；
• 若根结点不为空，那么把根结点作为当前结点；
• 若当前结点为空，返回当前结点的父结点，结束；
• 若当前结点key等于查找key，那么该key的结点就是插入结点，更新结点的值，结束；
• 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
• 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4。

找到插入位置后，新结点应该是什么颜色？从性质5可以知道，红黑树的根结点到每个叶子结点的黑色结点数量相同。若插入结点为黑色，必然破坏性质5，因此选择红色，破坏规则的可能性小一些。

在对插入情景讲解之前，先对结点之间的关系进行梳理，如图所示：

图2的字母并不代表结点key的大小。I表示插入结点，P表示插入结点的父结点，S表示插入结点的叔叔结点，PP表示插入结点的祖父结点。

【情景1：红黑树为空树】

直接将插入结点作为根结点，并设为黑色。

【情景2：插入结点已存在】

插入结点key已存在，说明红黑树已经是平衡状态，此时只需要用插入key值替换结点key值，不用变色。

【情景3：插入结点的父结点为黑色】

由于新插入的结点是红色，并不会影响红黑树的平衡性，因此直接插入，无需做自平衡操作。例如，结点58插入到如图1的红黑树，如图3所示：

【情景4：插入结点的父结点为红色】

根据红黑树的性质1：根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。此情景比较复杂，分成以下几个子情景：

【情景4.1：叔叔结点存在并且为红色】

从红黑树中每个红色结点的两个子结点一定都是黑色，因此不可能同时存在两个相连的红结点，因此需要变色操作维持红黑树平衡。

从图4和图5中可以看出，结点50由黑色变成红色，如果其父结点60是黑色，那么无需再做任何处理；但父结点60是红色，根据性质4可知红黑树不再平衡，因此需要将结点50当作新的插入结点，继续做插入自平衡处理。此时是需要将结点60和结点77变成黑色，结点66变成红色吗？根据性质1，这样的做法是不行的，结点66是根结点，必须是黑色。出现该情景需要使用下面介绍的旋转操作，维持红黑树的平衡性。

【情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父结点是祖父结点的左子结点】

这种情景又分为插入结点是父结点的左子结点和右子结点两种子情景，通常是采用类似平衡二叉树自平衡的方法，只不过增加了变色过程。

【情景4.2.1：插入结点是父结点的左子结点】

插入结点20，首先是对父结点30和祖父结点50变色，然后对祖父结点50右旋的过程：

• 父结点30由红色变成黑色；
• 祖父结点50由黑色变成红色；
• 对祖父结点50右旋操作。

插入结点20过程，如图6所示：

父结点30和祖父结点50变色之后，变成连续的红色结点，需要对祖父结点50进行右旋操作：

【情景4.2.2：插入结点是其父结点的右子结点】

插入结点40，首先是对父结点30左旋，然后对插入结点40和祖父结点50变色，最后对祖父结点50右旋的过程：

• 对父结点30进行左旋操作；
• 插入结点40由红色变成黑色；
• 祖父结点50由黑色变成红色；
• 对祖父结点50进行右旋操作。

插入结点40，过程如图8所示：

对插入结点40和祖父结点50进行变色操作：

对祖父结点50进行右旋操作：

【情景4.3：叔叔结点不存在或为黑色，并且插入结点的父结点是祖父结点的右子结点】

该情景和情景4.2类似，也分为两个子情景，只是方向相反。

【情景4.3.1：插入结点是父结点的右子结点】

插入结点58，首先是对父结点55和祖父结点50变色，然后对祖父结点50左旋的过程：

• 父结点55由红色变成黑色；
• 祖父结点50由黑色变成红色；
• 对祖父结点50左旋操作。

插入结点58，过程如图11所示：

【情景4.3.2：插入结点是父结点的左子结点】

插入结点53，首先是对父结点55右旋，然后对插入结点53和祖父结点50变色，最后对祖父结点50左旋的过程：

• 父结点55右旋操作；
• 插入结点53由红色变成黑色；
• 祖父结点50由黑色变成红色；
• 对祖父结点50左旋操作。

插入结点53，对父结点55右旋，如图13所示：

对插入结点53和祖父结点50进行变色操作：

对祖父结点50进行左旋操作：

在情景4.1中，图4和图5中的结点经过变色后并没有恢复红黑树的平衡状态，需要通过左旋和右旋的操作才能恢复红黑树的平衡状态。对于图4、5来说，需要对根结点66进行右旋操作，右子树结点进行变色，如图16所示：

删除操作

红黑树也是一棵二叉查找树，其删除结点的过程比较复杂，但也分为4种情景：

情景1：删除结点时叶子结点。

情景2：删除结点只有左子结点，没有右子结点。

情景3：删除结点只有右子结点，没有左子结点。

情景4：删除结点既有左子结点，又有右子结点。

下面对每种情景进行详细分析。

【情景1：删除节点为叶子节点】

该情景中删除的结点可能是黑色，也可能是红色，因此要分成两个子情景，其中删除黑色结点过程复杂。

【情景1.1：删除结点为红色】

该情景删除红色结点并不影响红黑树的平衡性质，因此删除结点后不需要调整红黑树。如图17所示：

【情景1.2：删除结点为黑色】

假设结点D是删除结点，兄弟结点S，父结点P，兄弟结点S的左右子结点分别为SL、SR。当删除结点D为黑色时，会出现以下五种情景（灰色表示红色或者黑色）：

【情景1.2.1：兄弟结点为黑色，无左右子结点】

删除操作：1）删除结点D；2）兄弟结点S变成红色；3）父结点P变黑色。过程如图所示：

例子，如图结点50删除后，平衡性将被破坏，因此需要将结点62变红色，父结点60变黑色。

【情景1.2.2：兄弟结点为黑色，有左子结点且为红色】

删除操作：1）删除结点D；2）兄弟结点S右旋；3）左子结点SL变成父结点P的颜色，父结点P变成黑色；4）父结点P左旋。过程如图所示：

例子，结点50删除过程如图所示：

【情景1.2.3：兄弟结点为黑色，有右子结点且为红色】

删除操作：1）删除结点D；2）兄弟结点S变成父结点P的颜色；3）右子结点SR和父结点P变成黑色；4）父结点P左旋。过程如图所示：

例子，结点50删除过程如图所示：

【情景1.2.4：兄弟结点为黑色，有左右子结点且都为红色】

删除操作：1）删除结点D；2）父结点P左旋；3）兄弟结点S变成父结点P的颜色；4）右子结点SR和父结点P变成黑色。过程如图所示：

例子， 结点50删除过程如图所示：

【情景1.2.5：兄弟结点为红色，有左右子结点且都为黑色】

该情景中父结点P一定是黑色，因为不能出现连续的红结点。删除操作：1）删除结点D；2）父结点P左旋；3）兄弟结点S变成黑色；4）左子结点SL变红色。过程如图所示：

例子，结点50删除过程如图所示：

【情景2：删除节点只有左子节点，没有右子结点】

删除操作：1）用左子结点DL的值替换删除结点D的值；2）删除左子结点DL。如图所示删除结点62，将结点61替换结点62，然后删除原红色结点61。

【情景3：删除节点只有右子节点，没有左子结点】

删除操作：1）用右子结点DR的值替换删除结点D的值；2）删除右子结点DR。如图所示删除结点62，将结点65替换结点62，然后删除原红色结点65。

【情景4：删除节点有左子节点和右子结点】

操作：1）用删除结点D的前驱结点的值（左子树的最大值）或后继结点的值（右子树的最小值）替换删除结点D的值；2）删除前驱结点或后继结点，此时将删除过程转换成前3种情景。

以上情景中删除结点D都是父结点的左子结点，右子结点删除过程与左子结点删除过程是镜像关系，这里不再详解。

代码实现

完整的代码可以参考Github源码：

https://github.com/MrYuxiangZhu/DataStructure/blob/master/06.%20Tree/09.%20RedBlackTree.h