#
红黑树（下）
一、删除调整发生的前提
- 删除红色节点，不会对红黑树的平衡产生影响
- 度为1的黑色节点，唯一子孩子，一定是红色
- 删除度为1的黑色节点，不会产生删除调整
- 删除度为0的黑色节点，会产生一个双重黑的 NIL 节点
- 删除调整，就是为了干掉双重黑
二、删除调整
-
双重黑节点的兄弟节点是黑色，兄弟节点下面的两个子节点也是黑色，父节点增加一重黑色，双重黑与兄弟节点，分别减少一重黑色。
- 兄弟节点是黑色，并且，兄弟节点中有红色子节点
- R（兄弟）R（右子节点），左旋，新根改成原根的颜色，将新根的两个子节点，改成黑色
- R（兄弟）L（左子节点），先小右旋，对调新根与原根的颜色，转成上一种情况
- LL 同理 RR
- LR 同理 RL
- 兄弟节点是红色，通过旋转，转变成兄弟节点是黑色的情况
三、代码演示
- 进行 LR/RL 类型判断的时候，不能判断 LL 子树是否为黑色，LL 子树有可能是 NIL 节点，在某些特殊情况下，读到的颜色可能是双重黑，取而代之的判断方法就是【LL 子树不是红色】。