红黑树.md

红黑树是一种含有红黑节点并能自平衡的二叉搜索树。 性质：

• 每个结点要么是黑色，要么是红色
• 根结点是黑色
• 每个叶子结点（NIL）是黑色
• 每个红色结点的两个子结点一定都是黑色
• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点 从性质5可以推出，如果一个结点存在黑子结点，那么该结点肯定有两个子结点。 红黑树并不是一个完美平衡二叉搜索树，但由于任一结点到叶子结点的路径都包含数量相同的黑结点，因此一个结点的左子树和右子树的黑结点层数相同（黑色完美平衡）。

在从根结点通往任一结点的沿途，黑结点都不少于红结点，除去根结点本身，沿途所经黑结点的总数称作该结点的黑深度（black depth）——根结点的黑深度为 0 ，其余以此类推。最后一个性质也可等效理解为“所有外部结点的黑深度统一”。

---

红黑树通过 左旋、右旋、变色 三种操作保持自平衡。

• 左旋，以某个结点作为支点（旋转结点），其右子节点变为旋转结点的父结点，右子节点的左子结点变为旋转结点的右子结点，左子结点保持不变。 ![[红黑树左旋.png]]
• 右旋，以某个结点作为支点（旋转结点），其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。 ![[红黑树右旋.png]]
• 变色，结点颜色由红变黑或由黑变红。

---

查找 s_key（与二叉搜索树类似，复杂度O(log n)）

• 1. 从根结点开始查找，把根结点设为当前结点
• 2. 若当前结点为空，返回 null
• 3. 若当前结点非空，比较当前结点 c_key 和 查找的s_key
  • 若 c_key == s_key，返回当前结点
  • 若 c_key > s_key，把当前结点的左子结点设置为当前结点，重复步骤2
  • 若 c_key < s_key，把当前结点的右子结点设置为当前结点，重复步骤2 ![[红黑树查找流程图.png]]

---

插入 s_key，包含两部分工作，一是查找插入的位置； 二是插入后自平衡。 查找插入的父结点：

• 1. 从根结点开始查找
• 2. 若根结点为空，那么插入结点作为根结点，结束
• 3. 若根结点不为空，那么把根结点作为当前结点
• 4. 若当前结点为 null ，返回当前结点的父结点，结束
• 5. 若当前结点 c_key 等于 s_key ，那么该结点就是插入结点，更新结点的值，结束
• 6. 若当前结点 c_key 大于 s_key ，把当前结点的左子结点设置为当前结点，重复步骤4
• 7. 若当前结点 c_key 小于 s_key ，把当前结点的右子结点设置为当前结点，重复步骤4 找到插入位置后，插入红色结点（红色结点在父结点为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作；如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多 1 ，必须做自平衡） ![[红黑树插入场景.png]] 除了情景2，所有插入操作都是在叶子结点进行的。在查找插入位置时，实际上在找子结点为空的父结点。 ![[红黑树插入结点约定.png]] 插入情景1：红黑树为空树 直接把插入结点作为根结点（并把结点设为黑色） 插入情景2：插入结点的 key 已经存在 插入前红黑树已是平衡的，把插入结点设置为将要替代结点的颜色，再结点的值更新就完成插入 插入情景3：插入结点的父结点为黑结点 由于插入的结点是红色的，并不会影响红黑树的平衡，直接插入即可，无需做自平衡 插入情景4：插入结点的父结点为红结点 由于根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

插入情景4.1：叔叔结点存在且为红结点 由于红结点的子结点是黑色的。父与叔结点均为红，祖父结点肯定为黑结点。因此，此时插入子树的红黑层数情况为：黑红红。最简单的处理方式是把其改为：红黑红。（与插入结点处于父结点左右无关） ![[红黑树插入之叔叔存在且为红.png]] 可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色。（红黑树不再平衡），需要把PP当作新插入的结点，继续做插入操作自平衡处理，直到平衡为止。 试想下，PP刚好为根结点时，（但根结点需为黑色），因此必须把 PP 重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。——唯一一种会增加红黑树黑色结点层数的插入情景。 同时，可以看到，不同于普通的二叉搜索树自顶向下递归查找插入位置插入，而红黑树的生长是自底向上从叶子结点开始，然后向上调整树的结构。

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点。 插入情景4.2.1：插入结点是其父结点的左子结点 将 P 设为黑色；然后将 PP 设为红色；对 PP 进行右旋。 ![[Linux/images/红黑树之插入结点是其父结点的左子结点.png]] 将 P 设为红色，I 和 PP 设为黑色的处理也是可以的，但这样的话又需要将 P 作为当前结点自底向上处理。 插入情景4.2.2：插入结点是其父结点的右子结点 首先对 P 进行左旋；然后把 P 设置为插入结点，得到情景4.2.1；接着进行情景4.2.1的处理 ![[Linux/images/红黑树之插入结点是其父结点的右子结点.png]]

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点。 插入情景4.3.1：插入结点是其父结点的右子结点 将 P 设为黑色；将 PP 设为红色；对 PP 进行左旋 ![[红黑树之插入结点是其父结点的右子结点 1.png]] 插入情景4.3.2：插入结点是其父结点的左子结点 对 P 进行右旋；把 P 设置为插入结点，得到情景4.3.1；进行情景4.3.1的处理 ![[红黑树之插入结点是其父结点的左子结点 1.png]]

---

删除，删除也包括两部分工作，一是查找目标结点；二是删除后自平衡。 查找目标结点可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就需要做自平衡处理。删除了结点后还需要找结点来替代删除结点的位置，不然子树和父辈结点断开了，除非删除结点刚好没子结点。

二叉树删除结点找替代结点有3种情景：

• 情景1：若删除结点无子结点，直接删除
• 情景2：若删除结点只有一个子结点，用子结点替换删除结点
• 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点

红黑树删除 ![[红黑树删除情景.png]] 删除操作删除的结点可以看作删除替代结点，而替代结点最后总在树末。（删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点） ![[红黑树删除结点与替代结点.png]]

![[红黑树之删除约定.png]] 灰色结点表示它可以是红色也可以是黑色的。 R 是即将被替换到删除结点的位置的替代结点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除结点的位置，才算删除完成。

删除情景1：替换结点是红色结点 把替换结点换到删除结点的位置时，由于替换结点是红色，删除了也不会影响红黑树的平衡，只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。

删除情景2：替换结点是黑结点 当替换结点是黑色时，需要进行自平衡处理。而且要考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。 删除情景2.1：替换结点是其父结点的左子结点 删除情景2.1.1：替换结点的兄弟结点是红结点 若兄弟结点是红结点，兄弟结点的父结点和子结点肯定为黑色，不会有其他子场景。按下图处理，得到删除情景2.1.2.3 处理：

• 将 S 设置为黑色
• 将 P 设置为红色
• 对 P 进行左旋，得到情景2.1.2.3
• 进行情景2.1.2.3的处理 ![[红黑树之替换结点的兄弟结点是红结点.png]] 删除情景2.1.2：替换结点的兄弟结点是黑结点 当替换结点的兄弟结点为黑时，无法确定其父结点和子结点的具体颜色（如果不考虑自底向上的情况，子结点飞红即为叶子结点NIL） 删除情景2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色 即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又有红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。如下图所示。 处理：
• 将S的颜色设为P的颜色
• 将P设为黑色
• 将SR设为黑色
• 对P进行左旋 ![[红黑树删除情景2.1.2.1.png]] 平衡后的图怎么不满足红黑树的性质？前文提醒过，R是即将替换的，它还参与树的自平衡，平衡后再替换到删除结点的位置，所以R最终可以看作是删除的。

删除情景2.1.2.2：替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点 兄弟结点所在的子树有红结点，我们总是可以向兄弟子树借个红结点过来，显然该情景可以转换为情景2.1.2.1。 处理：

• 将S设为红色
• 将SL设为黑色
• 对S进行右旋，得到情景2.1.2.1
• 进行情景2.1.2.1的处理 ![[红黑树删除情景2.1.2.2.png]]

删除情景2.1.2.3：替换结点的兄弟结点的子结点都为黑结点 好了，此次兄弟子树都没红结点“借”了，兄弟帮忙不了，找父母呗，这种情景我们把兄弟结点设为红色，再把父结点当作替代结点，自底向上处理，去找父结点的兄弟结点去“借”。但为什么需要把兄弟结点设为红色呢？显然是为了在P所在的子树中保证平衡（R即将删除，少了一个黑色结点，子树也需要少一个），后续的平衡工作交给父辈们考虑了，还是那句，当每棵子树都保持平衡时，最终整棵总是平衡的。 处理：

• 将S设为红色
• 把P作为新的替换结点
• 重新进行删除结点情景处理 ![[红黑树删除情景2.1.2.3.png]]

删除情景2.2：替换结点是其父结点的右子结点 右边的操作是方向相反 删除情景2.2.1：替换结点的兄弟结点是红结点
处理：

• 将S设为黑色
• 将P设为红色
• 对P进行右旋，得到情景2.2.2.3
• 进行情景2.2.2.3的处理 ![[红黑树删除情景2.2.1.png]]

删除情景2.2.2：替换结点的兄弟结点是黑结点
删除情景2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
处理：

• 将S的颜色设为P的颜色
• 将P设为黑色
• 将SL设为黑色
• 对P进行右旋 ![[红黑树删除情景2.2.2.1.png]]

删除情景2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
处理：

• 将S设为红色
• 将SR设为黑色
• 对S进行左旋，得到情景2.2.2.1
• 进行情景2.2.2.1的处理 ![[红黑树删除情景2.2.2.2.png]]

删除情景2.2.2.3：替换结点的兄弟结点的子结点都为黑结点
处理：

• 将S设为红色
• 把P作为新的替换结点
• 重新进行删除结点情景处理 ![[红黑树删除情景2.2.2.3.png]]

综上，红黑树删除后自平衡的处理可以总结为：

1. 自己能搞定的自消化（情景1）
2. 自己不能搞定的叫兄弟帮忙（除了情景1、情景2.1.2.3和情景2.2.2.3）
3. 兄弟都帮忙不了的，通过父母，找远方亲戚（情景2.1.2.3和情景2.2.2.3）

练习：

1. 黑结点可以同时包含一个红子结点和一个黑子结点吗？ ![[红黑树之黑结点子结点问题.png]]

2. 画出下图插入自平衡处理过程 ![[红黑树插入自平衡示例.png]]

答案： ![[红黑树插入自平衡示例答案.png]]

3. 画出下图删除自平衡处理过程 ![[红黑树之删除示例.png]]

答案： ![[红黑树删除示例答案.png]]