1. 红黑树（red black tree）

关于自平衡的二叉查找树，AVL树是比较经典的一种，前面也对其实现原理做了比较详细的介绍。当然，相关的数据结构肯定不止这一种，历史上AVL树流行的另一种变种是红黑树。

红黑树通过给节点着色，将相关操作的时间复杂度被控制在了O(log2N)，它的定义如下：

1. 每一个节点要么是黑色的，要么是红色的（也与红黑树这一名字相符）；
2. 根节点是黑色的；
3. 约定null引用都是黑色的；
4. 如果一个节点是红色的，那么它的子节点必须是黑色的；
5. 从一个节点到一个null引用的任意一条路径必须包含相同数目的黑色节点。

通过着色法则可以给出一个结论：红黑树的高度最多是2log(N+1)。因此，查找操作的时间复杂度就被控制在了O(logN)。下面给出了一个红黑树的示例：

与AVL树类似的，红黑树的查找操作是简单的，其难点在于如何将一个新的节点插入到树中，以及如何从树中删除指定的节点，也就是我们通常所说的插入和删除操作。

2. 插入操作

遵循二叉查找树中的规则，通常我们会把新插入项作为叶子节点放入到树中。如果新插入的节点是黑色的，那么必然会违反条件5（该路径上黑色节点增加了，其他路径却不变），因此，新插入的叶子节点必须是红色的。 然而这又会引入一个新的问题，将新插入的节点着色为红色，虽然符合了条件5，但是如果它的父节点也是红色的，那就违反了条件4。 在这种情况下，就需要通过变色和旋转操作，以使其满足条件4。

假设目标节点为X（目标节点是会变的，不一定总是叶子节点，修改后上层被改变的节点可能不符合红黑树规则，需要将其重新设为目标节点），可以分为以下几种情况：

1. 如果X是根节点，则将其变为黑色，流程结束；
2. X的父节点是黑色的，符合红黑树规则，流程结束；
3. X的父节点P是红色的，且父节点P的兄弟节点S也是红色的（变色）；
4. X的父节点P是红色的，且父节点P的兄弟节点S是黑色的，注意，null也为黑色（旋转）。

2.1 情况3

对于情况3，其祖父-父-子三代的关系如下图所示（镜像情况类似）：

由红黑树的规则可知（插入新节点之前是一颗符合规定的红黑树），红色节点的父节点肯定是黑色的，因此情况3中新插入节点X的祖父节点G一定是黑色的。 仔细观察上图的子树可以发现，如果将父代和祖父代的颜色互换，两条支路的黑色节点数依旧保持不变，且互换后节点X符合条件4。我们将此操作称为变色，其示意图如下所示：

经过变色操作后，子树部分已经完全符合红黑树的定义，且相关路径上的黑色节点数保持不变。但由于节点G由黑转红了，因此节点G处可能引入了新的问题（违反的条件4），这时候只需要将G节点设为目标节点，重新判断G节点属于四种情况中的哪种，并进行相应的操作即可。

2.2 情况4

对于情况4，其祖父-父-子三代的关系如下图所示（镜像情况类似）：

同样的，在情况4中，X节点的祖父节点G一定是黑色的。 此时，如果依旧像前面那样进行变色操作，右边路径上的黑色节点数将会减1，会破坏整个支路。因此，针对情况4，无法使用变色操作，需要通过旋转来使其重新符合红黑树的规则。

此处的旋转与AVL树中的旋转操作十分类似，除了需要对节点的颜色做一些修改，其它方面可以说是完全一样。依旧将其分为单旋转和双旋转，其流程分别如下（如果看过AVL树的旋转操作，应该不难理解）。

2.2.1 单旋转

单旋转操作的示例如下所示：

简化版理解图如下：

2.2.2 双旋转

和AVL树中的旋转操作类似，针对需要双旋转的情况（当前面的X节点为P的右节点时就需要双旋转），先通过一次旋转将其转化为单旋转的情况，然后进行一次和前面一样的旋转即可。

双旋转的第一次旋转主要针对P节点和X节点：

如上图所示，在旋转了一次之后，就回到了单旋转可以解决的情况。 由于前面已经给出了单旋转的示例，在此就不再赘述，大家可以对照单旋转操作完成第二次旋转。

上述的例子只给出了目标节点X在G的左子树的情况，关于目标节点X在右子树中该如何旋转，根据镜像对称的原则，参照在左子树的情况，可以对应的给出镜像的解决方法，再次便不再赘述。

3. 删除操作

相对来说，删除操作会比插入操作更为复杂一些，可以将其分为两个部分：

• 找到要删除的节点并删除；
• 删除后的自平衡。

针对目标节点的删除，一般会先将其转移到叶子节点上，然后再进行删除，具体的删除过程可以参照二叉查找树的删除操作。这里重点讲一下删除后的自平衡操作。

由于删除操作相当于是先将目标节点与特点的叶子节点互换，这里的互换指的是只互换“内容”（key、value），节点的颜色并不互换（事实上被替换的叶子节点也不需要修改成被删除节点的值，因为它最终总归是要被删除的），然后再删除该节点，也就是说，从结果来看，可以将所有的删除操作都等价于删除叶子节点。

对于删除叶子节点而言，如果被删除叶子节点D是红色节点，则直接删除它，并不会影响红黑树的平衡；如果被删除的叶子节点D是黑色节点，则需要重新平衡，这时候可以根据其兄弟节点的颜色，分为以下两种情况（这里将要删除的叶子节点作为目标节点X）：

1. X是黑色，X的兄弟是红色；
2. X是黑色，X的兄弟是黑色。

3.1 情况1（X是黑色，X的兄弟是红色）

对于情况1，由于X的兄弟节点S是红色的，由红黑树的规则可知，X的父节点必然是黑色的，且S的子节点不为null且为黑色。在这种情况下，只需要通过一次旋转操作，就可以恢复红黑树的平衡：

从左图中可以看到，目标节点X被删除后，右边到null的路径上黑色节点是数目减1，平衡条件遭到破坏。在经过上图所示的旋转操作后（还伴随着节点颜色的改变），左边路径上的黑色节点数不变，且在节点X被删除前右边的路径也符合红黑树的规则。此时，删除操作就被转化为了情况2——X是黑色，X的兄弟也是黑色。

3.2 情况2（X是黑色，X的兄弟是黑色）

对于情况2，由于X和兄弟节点都是黑色的，所以无法确定X父节点的颜色；同时，由于X是叶子节点，所以其兄弟节点S的子节点要不就是红色的叶子节点，要不就为null。

首先根据X的父节点的颜色，可以分为两种子情况。

3.2.1 X的父节点为红色

1. S没有孩子节点：

   当X的父节点为红色，且S没有孩子节点时，只需要简单的变色操作即可恢复平衡，具体流程如下所示：
   

2. S有左孩子：

   当X的父节点为红色，且S有左孩子时（孩子节点必为红色），则需要通过单旋转操作恢复平衡（带有部分节点的变色）：
   
   此时，无论SL为红色节点或者null引用，都不影响黑色节点的计数值，即删除X节点后就达到了平衡状态。

3. S没有左孩子，但有右孩子：

   此时，需要通过双旋转恢复平衡（与AVL的旋转以及插入操作中的旋转有很多类似的地方，可自行体会）：
   
   如上图所示，进过第一次旋转之后，就回到了S有左孩子的情况，再进行第二次旋转操作就可以恢复平衡。

3.2.2 X的父节点为黑色

1. S没有孩子节点：

   当S没有孩子节点时，删除操作仿佛遇到了瓶颈，这时候整个这部分的子树只存在3个黑色节点（X删除前），在X被删除后无论如何都无法由剩下的2个节点构造出两段包含2个黑色节点的路径。

   这时候需要将目光“往上层看”，首先将X的兄弟节点S标红（这样子树所有路径都只有1个黑色节点，后续只需要在P与P的父节点之间“增加”一个黑色节点即可），然后将节点P作为目标节点，重新递归进行“删除操作”即可（P最终并不会被删除，只是让其作为目标节点进行平衡操作；如果P已经是根节点，则结束流程）。
   

2. S的有左孩子：

   此时的情形其实和3.2.1节中X的父节点为红色时十分类似，进行相似的旋转操作即可恢复平衡（只是颜色变换上有所区别）：
   

3. S没有左孩子，但有右孩子：

   同样的，与3.2.1节中X的父节点为红色时类似的进行双旋转操作，第一次旋转如下所示：