• 序言
• 红黑树必须满足以下5条性质
• 添加
• 删除

红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树(Symmetric Binary B-tree)

1.节点是RED或者是BLACK

2. 根节点是BLACK
3. 叶子节点(外部节点，空节点)都是BLACK
4. RED节点的子节点都是BLACK
   4.1 RED节点的parent都是BLACK
   4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

红黑树必须满足以下5条性质

1. 节点是RED或者BLACK
2. 根节点是BLACK
3. 叶子节点（外部节点，空节点）都是BLACK
4. RED节点的子节点都是BLACK
   4.1 RED节点的子节点都是BLACK
   4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

• 红黑树和4阶B树（2-3-4树）具有等价性
• BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
• 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
• 网上有些教程:用 2-3树 与 红黑树 进行类比，这是极其不严谨的，2-3树 并不能完美匹配 红黑树 的所有情况
• 注意:因为PPT界面空间有限，后面展示的红黑树都会省略NULL 节点

红黑树

等价交换后的4阶B树

• parent:父节点
• sibling:兄弟节点
• uncle:叔父节点( parent 的兄弟节点)
• grand:祖父节点( parent 的父节点)

已知

• B树中，新元素必定是添加到叶子节点中
• 4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
• 如果添加的是根节点，染成BLACK 即可

备注：建议新添加的节点默认为 RED，这样能够让红黑树的性质尽快满足(性质 1、2、3、5 都满足，性质 4 不一定)

• 有 4 种情况满足红黑树的性质 4 :parent 为 BLACK

1.同样也满足 4阶B树 的性质
2.因此不用做任何额外处理

• 有 8 种情况不满足红黑树的性质 4 :parent 为 RED( Double Red )

1. 其中前 4 种属于B树节点上溢的情况

判定条件:uncle 不是RED

1. parent 染成 BLACK，grand 染成 RED
2. grand 进行单旋操作
   2.1 LL:右旋转
   2.2 RR:左旋转

判定条件:uncle 不是RED

1. 自己染成BLACK，grand染成RED
2. 进行双旋操作
   2.1 LR:parent 左旋转， grand 右旋转
   2.2 RL:parent 右旋转， grand 左旋转

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理
   2.2 grand 向上合并时，可能继续发生上溢
   2.3 若上溢持续到根节点，只需将根节点染成 BLACK

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，当做是新添加的节点进行处理

B树中，最后真正被删除的元素都在叶子节点中

• 直接删除，不用作任何调整

有 3 种情况

1. 拥有 2 个 RED 子节点的 BLACK 节点
   1.1 不可能被直接删除，因为会找它的子节点替代删除
   1.2 因此不用考虑这种情况

2. 拥有 1 个 RED 子节点的 BLACK 节点

3. BLACK 叶子节点

判定条件:用以替代的子节点是 RED

将替代的子节点染成BLACK 即可保持红黑树性质

1. BLACK 叶子节点被删除后，会导致B树节点下溢(比如删除88)

2. 如果 sibling 至少有 1 个 RED 子节点
   2.1 进行旋转操作
   2.2 旋转之后的中心节点继承 parent 的颜色
   2.3 旋转之后的左右节点染为 BLACK

• 下图是3种需要删除的情况

• 下图对应着删除节点88后，旋转之后的样子

判定条件:sibling 没有 1 个 RED 子节点

• 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

如果 parent 是 BLACK

1. 会导致parent 也下溢
2. 这时只需要把 parent 当做被删除的节点处理即可