一、红黑树定义及性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

• 性质1：每个结点要么是黑色，要么是红色。
• 性质2：根结点是黑色。
• 性质3：每个叶子结点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：

• 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

下图就是一颗简单的红黑树，其中Nil为叶子结点(红色结点H和M同样存在叶子子结点)，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)

红黑树.png

红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树自平衡靠的是三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

左旋.png

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

右旋.png

变色：结点的颜色由红变黑或由黑变红。

二、红黑树查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：

1. 从根结点开始查找，把根结点设置为当前结点；
2. 若当前结点为空，返回null；
3. 若当前结点不为空，用当前结点的key跟查找key作比较；
4. 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
5. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
6. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；

三、红黑树插入

1、确定插入位置

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

插入位置找到后，把插入结点放到正确的位置，插入结点的颜色是红色。因为红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

2、自平衡

所有插入情景如下图

红黑树插入情景.png

根据二叉树的性质，除了情景2，所有插入操作都是在叶子结点进行的。这点应该不难理解，因为查找插入位置时，我们就是在找子结点为空的父结点的

在开始每个情景的讲解前，我们还是先来约定下，如下图。

插入结点叫法约定.png

插入情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根结点是黑色。还需要把插入结点设为黑色。

处理：把插入结点作为根结点，并把结点设置为黑色。

插入情景2：插入结点的Key已存在

插入结点的Key已存在，既然红黑树总保持平衡，在插入前红黑树已经是平衡的，那么把插入结点设置为将要替代结点的颜色，再把结点的值更新就完成插入。

处理：

• 把I设为当前结点的颜色
• 更新当前结点的值为插入结点的值

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

由于插入的结点是红色的，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

处理：直接插入。

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

再次回想下红黑树的性质2：根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。

情景4又分为很多子情景，下面将进入重点部分，各位看官请留神了。

插入情景4.1：叔叔结点存在并且为红结点

从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。

处理：

• 将P和S设置为黑色
• 将PP设置为红色
• 把PP设置为当前插入结点

插入情景4.1_1.png

插入情景4.1_2.png

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。

试想下PP刚好为根结点时，那么根据性质2，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。

我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。

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

单纯从插入前来看，也即不算情景4.1自底向上处理时的情况，叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5。
但是在自底向上处理的时候，叔叔结点不一定为叶子结点。

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

处理：

• 将P设为黑色
• 将PP设为红色
• 对PP进行右旋

场景4.2.1插入.png

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

这种情景显然可以转换为情景4.2.1

处理：

• 对P进行左旋
• 把P设置为插入结点，得到情景4.2.1
• 进行情景4.2.1的处理

插入场景4.2.2.png

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

该情景对应情景4.2，只是方向反转

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

处理：

• 将P设为黑色
• 将PP设为红色
• 对PP进行左旋

插入场景4.3.1.png

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

处理：

• 对P进行右旋
• 把P设置为插入结点，得到情景4.3.1
• 进行情景4.3.1的处理

插入场景4.3.2.png

四、红黑树删除

删除的结点类型从大的方面来说，只有两种：

1. 单个的叶子结点（不是指NULL结点，就是二叉排序树中的叶子结点的概念）
2. 只有右子树（或只有左子树）的结点

为什么这样呢？
我们知道，对于一棵普通的二叉排序树来说，删除的结点情况可以分为3种：

1. 叶子结点
2. 只有左子树或只有右子树的结点
3. 既有左子树又有右子树的结点

我们知道对于一棵普通二叉树的情况3来说，要删除既有左子树又有右子树的结点，我们首先要找到该结点的直接后继结点，然后用后继结点替换该结点，最后按1或2中的方法删除后继结点即可

所以情况3可以转换成情况1或2。

同样，对于红黑树来讲，我们实际上删除的结点情况只有两种

对于情况2，也就是待删除的结点只有左子树或这有右子树的情况，有很多组合在红黑树中是不可能出现的，因为他们违背了红黑树的性质

情况2中不存在的情况有（其中D表示要删除的结点，DL和DR分别表示左子和右子）：

不存在情况1.png

上述四种情况违背了性质5

不存在情况2.png

上述两种情况违背了性质4

删除场景1 删除的结点是红色结点

可分两种情况

删除场景1.1 删除红色的叶子结点（D表示待删除的结点，P表示其父亲结点）

删除场景1.1.png

处理：直接删除D

删除场景1.2 删除的红色结点只有左子树或只有右子树

经上述分析不会出现该场景

删除场景2 删除的结点是黑色结点

可以分2种情况

删除场景2.1 删除的黑色结点仅有左子树或者仅有右子树

去掉前面已经分析的不存在的情况。这种情况下结点的结构只可能是

删除场景2.1.png

处理：

• 用D的孩子（左或右）替换D
• 并将D孩子的颜色改成黑色即可（因为路径上少了一个黑结点，所已将红结点变成黑结点以保持红黑树的性质）

删除场景2.2 删除的黑色结点为叶子结点

删除场景2.2.1 待删除节点D的兄弟节点S为红色

删除场景2.2.1.1 D是左节点的情况

删除场景2.2.1.1.png

调整做法是将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行AVL树种的RR型操作，结果如下图

删除场景2.2.1.1处理后.png

这个时候我们会发现，D的兄弟节点变成了黑色，这样就成后面要讨论的情况

删除场景2.2.1.2 D是右节点的情况

删除场景2.2.1.2.png

将P和S的颜色互换，也就是将P变成红色，将S变成黑色，然后对P进行类似AVL树的LL操作。结果如下图

删除场景2.2.1.2处理后.png

删除场景2.2.2 兄弟节点为黑色，且远侄子节点为红色

删除场景2.2.2.1 D为左孩子对的情况，这时D的远侄子节点为S的右孩子

删除场景2.2.2.1.png

没有上色的节点表示黑色红色均可，注意如果SL为黑色，则SL必为NULL节点。

处理

• 将P和S的颜色对调
• 对P树进行类似AVL树RR型的操作
• 最后把SR节点变成黑色，并删除D

删除场景2.2.2.1处理后.png

删除场景2.2.2.2 D为右孩子的情况，此时D的远侄子为S的左孩子

删除场景2.2.2.2.png

同样，将P和S的颜色对调，然后再对P树进行类似AVL树RL型的操作，最后将SR变成黑色，并删掉D即可。结果如下图

删除场景2.2.2.2处理后.png

删除场景2.2.3 兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色

删除场景2.2.3.1 D为左孩子的情况，此时近侄子节点为S的左孩子

删除场景2.2.3.1.png

处理

• SL右旋
• S和SL的颜色互换
• 变成删除场景2.2.2.1

删除场景2.2.3.1处理后.png

删除场景2.2.3.2 D为右孩子的情况，此时近侄子节点为S的右孩子

删除场景2.2.3.2.png

处理

• 将S和SR颜色对调
• 对SR进行左旋操作
• 变成了删除场景2.2.2.2

删除场景2.2.3.2处理后.png

删除场景2.2.4 父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色的情况

删除场景2.2.4.png

如果删除D，那经过P到D的子节点NULL的路径上黑色就少了一个，这个时候我们可以把P变成黑色，这样删除D后经过D子节点（NULL节点）路径上的黑色节点就和原来一样了。但是这样会导致经过S的子节点（NULL节点）的路径上的黑色节点数增加一个，所以这个时候可以再将S节点变成红色，这样路径上的黑色节点数就和原来一样了

处理

• 父亲节点P改成黑色
• 将兄弟节点S改成红色，然后删除D

删除场景2.2.4处理后.png

删除场景2.2.5 父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色的情况

删除场景2.2.5.png

方法是将兄弟节点S的颜色改成红色，这样删除D后P的左右两支的黑节点数就相等了，但是经过P的路径上的黑色节点数会少1，这个时候，我们再以P为起始点，继续根据情况进行平衡操作（这句话的意思就是把P当成D（只是不要再删除P了），再看是那种情况，再进行对应的调整，这样一直向上，直到新的起始点为根节点）。结果如下图

删除场景2.2.5处理后.png