数据结构与算法——红-黑树

1 为什么需要红-黑树？

普通二叉搜索树，插入新节点后可能导致树的不平衡。
而平衡的二叉树，才能使搜索效率最高。
红-黑树在插入和删除的时候进行了一些特殊的处理，能使二叉树保持平衡。

2 红-黑规则

红-黑树在插入（删除）一个节点时，只有遵循红-黑规则，树才能始终保持平衡。
即遵循红-黑规则<=>平衡树，把平衡树的问题转变为让树遵循红-黑规则的问题。
① 每一个节点不是红色的就是黑色的。
② 根总是黑色的。
③ 如果节点是红色的，则它的子节点必须是黑色的（反之倒不一定必须为真）。
④ 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即黑色高度相同）。

3 为什么默认插入红色节点？

若默认插入红色节点
- 若父节点是黑节点——>不违反红-黑规则
- 若父节点是红节点——>违法红-黑规则③
若默认插入黑色节点
- 无论父节点是黑或红——>一定违反红-黑规则④

综上，默认插入红色节点违规率50%，默认插入黑色节点违规率100%，所以默认插入红色节点好。

4 如何修正违规？

(1) [三节点]颜色变换

触发：在插入过程中遇到一个黑色节点，并且它还有两个红色子节点，则需要三节点颜色变换。
目的：在不违反红-黑规则④的前提下，一是使连接红色节点更方便，二是保证在进行一次或两次旋转操作后整个树仍是正确的红-黑树，三是保证了插入时若父节点（P节点）是红色节点则不可能有兄弟节点（不可能有一个红色兄弟节点，因为有颜色变换；不可能有一个黑色兄弟节点，因为违背红-黑规则④）。
缺点：若祖父节点为红色节点，则会违反红-黑规则③。
情况
- 情况1：该黑色节点是根节点。
- 情况2：该黑色节点不是根节点。

(2) 单节点颜色改变

触发：插入一个新红色节点后，而它的父节点也是红色节点，则需要单节点颜色改变。（违背了红-黑规则③）
目的：单节点颜色改变和旋转一起修正父节点和子节点都是红色的违规问题，广义的旋转包括“单节点颜色改变”和“旋转”。
情况：

(3) 旋转

触发：插入新节点前或插入新节点后违反红-黑规则③，则需要旋转。
目的：单节点颜色改变和旋转一起修正父节点和子节点都是红色的违规问题
说明：
① 旋转分为左旋转和右旋转，以某个节点为顶点，向左或右“旋转”。
② 顶点的子节点和外侧子孙节点会跟随旋转方向上移或下移。
③ 横向移动节点：顶点的内侧子孙节点若是上移节点，则会断开与父节点的连接并且连接到它以前的祖父节点上；若原来是父节点的右子节点横向移动后会变成祖父节点的左子节点。
注意：红黑规则、三节点颜色变换和单节点颜色改变都只是有助于何时执行旋转，旋转才是平衡树起关键作用的操作。

5 插入一个新节点

步骤：向下路途中的颜色变换——>向下路途中的旋转——>插入新节点——>插入节点之后的旋转
说明：G——祖父节点、P——父节点、X——新插入节点

(1) 向下路途中的颜色变换

即三节点颜色变换
“向下路途中的旋转”是用来解决“向下路途中的颜色变换”可能带来的红色父节点与红色子节点连接的违规问题，把它放到最后分析比较合适

(3) 插入新节点

改变父节点引用即可，不再赘述。

(4) 插入节点之后的旋转

新插入节点有四种指向变化
插入节点三种可能性情况
- 可能性1：P是黑色的（不会违背红-黑规则）
  - 什么都不需要做
- 可能性2：P是红色的，X是G的一个外侧子孙点（出现红色节点与红色节点的连接，违背红-黑规则③）
  - 单节点改变颜色1：改变G节点的颜色
  - 单节点改变颜色2：改变P节点的颜色
  - 旋转1：以G节点为顶向X节点上升的方向旋转
- 可能性3：P是红色的，X是G的一个内测子孙点（出现红色节点与红色节点的连接，违背红-黑规则③）
  - 单节点改变颜色1：改变G节点的颜色
  - 单节点改变颜色2：改变X节点的颜色
  - 旋转1：以P节点为顶向X节点上升的方向旋转（转化成了“P是红色的，X是G的一个外侧子孙点”的情况）
  - 旋转2：以G节点为顶向X节点上升的方向旋转
其他情况分析
- 若X节点有兄弟节点S
  - 若P节点为黑色，则X节点直接连接到P节点（根据红-黑规则④，S节点一定是红色，但对X节点的插入无影响）。
  - 若P节点为红色，根据红-黑规则③S节点一定是黑色的。已知插入前和插入后树一定是平衡且符合红-黑规则的，但是插入前P节点却有单个黑色子节点S，不符合红-黑规则④，因此这种情况是不存在的。
- 若P节点有兄弟节点U
  - 若P节点为黑色，则X节点直接连接到P节点（根据红-黑规则④，S节点一定是红色，但对X节点的插入无影响）。
  - 若P节点是红色，根据红-黑规则④U节点一定是红色的。但是有两个红色子节点的黑色父节点在沿着路径向下的时候就颜色变换了，因此这种情况是不存在的。
- 综上，上面讨论的三种可能性情况是全部可能存在的插入情况。

(2) 向下路途中的旋转

“X节点”是外侧子孙节点：
- S1-情形：当前二叉树如下，待插入值3，节点3应该插在节点6的左子节点
- S2-对节点12及其子节点进行颜色变换，结果如下，发现节点12与其父节点25违反了红-黑规则③
- S3-此时把节点12记作X，X的父节点25记作P，X的祖父节点50记作50，接下来仿照（4）中的可能性2情况进行操作
- S3-1-将G节点和P节点颜色改变
- S3-2-以G节点为顶点，进行X节点向上方向的旋转（此处是右旋）。发现树平衡了！
- S4-从根节点25向下走，寻找合适的位置插入节点3。发现根节点25有两个红色子节点，需要进行颜色变换
- S5-找到合适的位置插入节点3
“X节点”是内侧子孙节点：
- S1-情形：当前二叉树如下，待插入值28，节点28应该插在节点31的左子节点
- S2-对节点37及其子节点进行颜色变换，结果如下，发现节点37与其父节点25违反了红-黑规则③
- S3-此时把节点37记作X，X的父节点25记作P，X的祖父节点50记作50，接下来仿照（4）中的可能性3情况进行操作
- S3-1-将X节点和G节点改变颜色
- S3-2-以P节点为顶点，进行X节点向上方向的旋转（此处是左旋）
- S3-3-再以G节点为顶点，进行X节点向上方向的旋转（此处是右旋）。发现树平衡了！
- S4-从根节点37向下走，寻找合适的位置插入节点28。发现根节点37有两个红色子节点，需要进行颜色变换
- S5-找到合适的位置插入节点28