Appearance
红黑树
1. 红黑树定义性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树，它满足以下性质：
- 性质 1：每个结点要么是黑色，要么是红色；
- 性质 2：根结点是黑色；
- 性质 3：每个叶子结点（Nil）是黑色；
- 性质 4：每个红色结点的两个子结点一定都是黑色；
- 性质 5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点；
图 1 就是一颗简单的红黑树，其中 Nil 为叶子结点。
红黑树并不是一个完美平衡二叉查找树，从图 1 可以看到，根结点 P 的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点（性质 5）。所以我们叫红黑树这种平衡为黑色完美平衡。
2. 红黑树自平衡操作
红黑树通过三种操作：左旋、右旋和变色达成自平衡：
左旋：以某个结点作为支点（旋转结点），其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变；
如下图以 P 结点作为支点进行左旋（先忽略前后结点颜色的变化）：
旋转前 旋转后 
图 2 P 结点左旋前 
图 3 P 结点左旋后 通过左旋，可以达到将右半边的结点往左半边挪的效果。
右旋：以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变；
如下图以 B 结点作为支点进行右旋：
旋转前 旋转后 图 4 B 结点右旋前 图 5 B 结点右旋后 通过右旋，可以达到将左半边的结点往右半边挪的效果。
变色：结点的颜色由红变黑或由黑变红；
变色能够影响该结点所在树的黑色层高。
Note：不论是左旋还是右旋都不会影响到旋转结点的父结点。
关于在什么时候考虑时候使用变色什么时候使用旋转，在后续的案例分析中我们可以归纳总结出以下经验：
- 优先考虑变色，不行再使用旋转；
- 能自己处理就自己处理，自己处理不了的就找兄弟帮忙，兄弟也搞不定再丢给老子；
3. 红黑树结点名称约定
4. 红黑树查找结点
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
- 从根结点开始查找，把根结点设置为当前结点；
- 若当前结点为空，返回 null；
- 若当前结点不为空，用当前结点的 key 跟查找 key 作比较；
- 若当前结点 key 等于查找 key，那么该 key 就是查找目标，返回当前结点；
- 若当前结点 key 大于查找 key，把当前结点的左子结点设置为当前结点，重复步骤 2；
- 若当前结点 key 小于查找 key，把当前结点的右子结点设置为当前结点，重复步骤 2；
由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为 O(2lgN)，也即整颗树刚好红黑相隔的时候。
5. 红黑树插入结点
插入操作包括两部分工作：一查找插入的位置，二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：
- 从根结点开始查找；
- 若根结点为空，那么插入结点作为根结点，结束；
- 若根结点不为空，那么把根结点作为当前结点；
- 若当前结点为 null，返回当前结点的父结点，结束；
- 若当前结点 key 等于查找 key，那么该 key 所在结点就是插入结点，更新结点的值，结束；
- 若当前结点 key 大于查找 key，把当前结点的左子结点设置为当前结点，重复步骤 4；
- 若当前结点 key 小于查找 key，把当前结点的右子结点设置为当前结点，重复步骤 4；
找到插入位置后，我们还需要考虑插入结点的颜色，我们通常将插入结点的颜色设置为红色。因为插入红色结点不影响其父结点的左右黑色平衡，但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多 1，必须再进行自平衡。
实际上所有插入操作都是在叶子结点进行的，这点应该不难理解，因为查找插入位置时，我们就是在找子结点为空的父结点。
5.1. 空树
处理步骤：
- 把插入结点作为根结点；
- 根据性质 2，我们需要把结点设置为黑色；
5.2. Key 已存在
处理步骤：更新 Key 结点的值。
5.3. P：Black
处理步骤：插入结点是红色的，不影响红黑树的平衡，直接插入即可。
5.4. P：Red
再次回想下红黑树的性质 2：根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。再从红黑树性质 4 可以知道祖父结点肯定为黑结点，因为不可能同时存在两个相连的红结点。
也就是如果 P 结点为红结点，则必然存在黑色的 PP 结点。
接下来我们还需要根据叔叔结点来区分不同情况：
5.4.1. U：Red
5.4.1.1. C 是 P 的左子结点
处理步骤：
- 插入 C 结点后，C、P 结点同为红色，违反了性质 4，所以我们需要将 P 结点设置为黑色；
- 将 P 结点设置为黑色后会导致 PP 左子树的黑色层高增加，因此我们需要将 U 结点也设置为黑色进而保持左右的黑色平衡；
- 不过需要注意的是，此时 PP 整棵树的黑色层高也有增加了，所以我们还需要将 PP 结点设置为红色以此来保持 PP 树整体的黑色层高不变，于此同时需要将 PP 视作新的插入结点，做自底向上处理；
| 处理前 | 处理后 | 自底向上 |
|---|---|---|
 |  | 将 PP 视作新的插入结点 …… |
试想下 PP 刚好为根结点时，那么根据性质 2，我们必须把 PP 重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。
我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。
5.4.1.2. C 是 P 的右子结点
处理步骤同 C 是 P 的左子结点的处理方式大致相同，这里就不再做过多的说明了。
| 处理前 | 处理后 | 自底向上 |
|---|---|---|
 |  | 将 PP 视作新的插入结点 …… |
5.4.2. NO U / U：Black
从纯插入的情况来看（即，非自底向上变红的情形），叔叔结点非红即为叶子结点（Nil），因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质 5。
前文说了，需要旋转操作时，肯定一边子树的结点多了或少了，需要租或借给另一边。插入显然是多的情况，那么把多的结点租给另一边子树就可以了。
5.4.2.1. C 是 P 的左子结点
处理步骤：
- 插入 C 结点后，C、P 结点同为红色，违反了性质 4，所以我们需要将 P 结点设置为黑色；
- 将 P 结点设置为黑色之后 PP 左子树的黑色层高增加了，此时 U 不存在或为黑结点，为了保持平衡，只能对 PP 进行右旋；
- 右旋后，P 结点的左子树黑色层高没有增加，而 PP 变成了 P 结点的右子树，而 PP 此时是黑色的会增加 P 结点右子树黑色层高，所以需要将 PP 更改为红色；
| 处理前 | 处理后 |
|---|---|
 |  |
不过可以把 P 设为红色 C 和 PP 设为黑色吗？答案是：可以！看过《算法：第 4 版》的同学可能知道，书中讲解的就是把 P 设为红色，C 和 PP 设为黑色。但把 P 设为红色，显然又会出现情景 4.1 的情况，需要自底向上处理，做多了无谓的操作，既然能自己消化就不要麻烦祖辈们啦。
5.4.2.2. C 是 P 的右子结点
处理步骤：
- 对 P 进行左旋，把 P 设置为插入结点，得到情景 C 是 P 的左子结点；
- 按 C 是 P 的左子结点的情况进行处理；
| 处理前 | 预处理 | 处理后 |
|---|---|---|
 |  |  |
6. 红黑树删除结点
红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。
二叉树删除结点找替代结点有 3 种情情景：
- 情景 1：若删除结点无子结点，直接删除；
- 情景 2：若删除结点只有一个子结点（由性质 5 可知该子结点一定是红色结点），用子结点替换删除结点（相当于回到了情景 1）；
- 情景 3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点；
补充说明下，情景 3 的后继结点是大于删除结点的最小结点，也是删除结点的右子树中最左结点。那么可以拿前继结点（删除结点的左子树最右结点）替代吗？可以的。但习惯上大多都是拿后继结点来替代，后文的讲解也是用后继结点来替代。另有种找前继和后继结点的直观的方法：把二叉树所有结点投射在 X 轴上，所有结点都是从左到右排好序的，所有目标结点的前后结点就是对应前继和后继结点。如图 13 所示：
接下来，讲一个重要的思路：删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！如图 14。在不看键值对的情况下，图 14 的红黑树最终结果是删除了 Q 所在位置的结点！这种思路非常重要，大大简化了后文讲解红黑树删除的情景！
| 处理前 | 处理后 |
|---|---|
 |  |
综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。有了这结论，我们讨论的删除红黑树的情景就少了很多，因为我们只考虑删除树末结点的情景了。
Note：在以下说明中 C 表示替代结点。
6.1. C：Red
处理步骤：由于替换结点是红色的，删除也了不会影响红黑树的平衡，直接删除替换结点即可。
Note：在删除替换结点前，需要先将替换结点的值赋值给原删除结点，后续不再做重复说明。
6.2. C：Black
当替换结点是黑色时，我们就不得不进行自平衡处理了，同时替换结点是黑色的话，那么也必然有兄弟结点，我们需要针对不同颜色的兄弟结点做不同处理。
6.2.1. B：Red
若兄弟结点是红结点，那么根据性质 4，兄弟结点的父结点和子结点肯定为黑色，并且根据性质 5，兄弟结点肯定有两个子结点，不会有其它情景：
处理步骤：
- P 左子树的黑色层高减少了，右树没法通过简单的变色自降层高，所以需要对 P 结点进行左旋，从右子树匀点结点过来；
- 旋转后 B 成为新的父结点，我们需要将 B 设置为黑色以保持父结点的颜色不变，并将 P 设置为红色也就是 B 原先的颜色；
- 此时我们需要将 P 重新设为黑色，BL 设为红色以维持局部整体的黑色平衡；
| 处理前 | 预处理 | 步骤 1 | 步骤 2 | 步骤 3 |
|---|---|---|---|---|
 |  |  |  |  |
6.2.2. B：Black
6.2.2.1. B 无子结点 & P：Red
处理步骤：将 B 设为红色、P 设为黑色，此时局部整体满足黑色平衡并且黑色层高不变，无需再做自底向上处理。
| 处理前 | 预处理 | 处理后 |
|---|---|---|
 |  |  |
6.2.2.2. B 无子结点 & P：Black
处理步骤：
- 将 B 设为红色、P 设为黑色；
- 此时局部整体满足黑色平衡，但是黑色层高降低了，需要将 P 视作新的删除结点，做自底向上处理；
| 处理前 | 预处理 | 处理后 | 自底向上 |
|---|---|---|---|
 |  |  | 将 P 视作新的删除结点 …… |
6.2.2.3. BR：Red
处理步骤：
- 左子树的黑色层高减少了，兄弟结点有子结点，尝试从右子树借点结点过来，对 P 进行左旋；
- 将 B 设置为 P 的颜色，以保持父结点的颜色不变，并将 P、BL 结点设置为黑色，此时局部整体满足黑色平衡并且黑色层高不变，无需再做自底向上处理；
| 处理前 | 预处理 | 步骤 1 | 步骤 2 |
|---|---|---|---|
 |  |  |  |
Note
- 这里 P 的颜色只影响 B 最终的颜色；
- 有无 BL 以及 BL 的颜色不影响整个处理流程；
6.2.2.4. BL：Red & BR：Black
在 B 子树中有个红色结点，显然我们可以通过右旋 B 结点将其转换为情景 BR:Red。
处理步骤：
- 对 B 进行右旋；
- 将 BL 设置为 B 的颜色，B 设置为红色，P 右子树对外界而言 “保持不变”，子结点的红色从原先的左边转移到了右边，至此我们得到了情景 BR:Red；
| 处理前 | 步骤 1 | 步骤 2 | 步骤 3 | 步骤 4 |
|---|---|---|---|---|
 |  |  |  |  |
6.2.2.5. BL：Black & BR：Black
此场景实际上与 B 无子结点 & P:Red 或 B 无子结点 & P:Black 类似，这里就不再做过多的说明了。
| 子情景 | 步骤 1 | 步骤 2 | 自底向上 |
|---|---|---|---|
P:Red |  |  | DONE |
P:Black |  |  | 将 P 视作新的删除结点 …… |