15 红黑树的删除
1. 我们将"删除红黑树中的节点"大致分为两步，
在第一步中"将红黑树当作一颗二叉查找树，将节点删除"后，可能违反"特性(2)、(4)、(5)"三个特性。
第二步需要解决上面的三个问题，进而保持红黑树的全部特性。
为了便于分析，我们假设"x包含一个额外的黑色"(x原本的颜色还存在)，这样就不会违反"特性(5)"。为什么呢？
删除节点y之后，x占据了原来节点y的位置。 既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。这样，当我们假设"x包含一个额外的黑色"，就正好弥补了"删除y所丢失的黑色节点"，也就不会违反"特性(5)"。 因此，假设"x包含一个额外的黑色"(x原本的颜色还存在)，这样就不会违反"特性(5)"。
现在，x不仅包含它原本的颜色属性，x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑"，它违反了"特性(1)"。
补充
补充：红黑树删除通常按以下 4 步处理（x 为"顶替位置的节点"，w 为兄弟节点）：
- x 是红色 —— 直接染黑即可，简单。
- x 是黑色，w 是红色 —— 父染红、w 染黑、对父做左旋/右旋，转为后三种情形。
- x 是黑色，w 是黑色，w 的两个孩子都是黑色 —— w 染红，x 上移至父节点继续处理。
- x 是黑色，w 是黑色，w 的左孩子红、右孩子黑（或对称情况） —— 对 w 做反向旋转，转化为情形 5。
- x 是黑色，w 是黑色，w 的右孩子红（或左孩子红，对称情况） —— w 染成父节点颜色，父染黑、w 对应孩子染黑，再对父旋转，结束。
与插入相比，删除的实现细节更繁琐，工业级实现（如 Java TreeMap）通常依赖现成的库，而不是手写。
来源整理自：我的有道云笔记
