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

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节点上升的方向旋转（转化成了“可能性2：P是红色的，X是G的一个外侧子孙点”的情况）；
    • 旋转2：以G节点为顶向X节点上升的方向旋转。
      

• 其他情况分析

  • 若X节点有兄弟节点S
    • 若P节点为黑色，则X节点直接连接到P节点（根据红-黑规则④，S节点一定是红色，但对X节点的插入无影响）。
    • 若P节点为红色，根据红-黑规则③S节点一定是黑色的。已知插入前和插入后树一定是平衡且符合红-黑规则的，但是插入前P节点却有单个黑色子节点S，不符合红-黑规则④，因此这种情况是不存在的。
  • 若P节点有兄弟节点U
    • 若P节点为黑色，则X节点直接连接到P节点（根据红-黑规则④，U节点一定是黑色，但对X节点的插入无影响）。
    • 若P节点是红色，根据红-黑规则④U节点一定是红色的。但是有两个红色子节点的黑色父节点在沿着路径向下的时候就颜色变换了，因此这种情况是不存在的。
  • 综上，上面讨论的三种可能性情况（可能性1、可能性2和可能性3）是全部可能存在的插入情况。

(2) 向下路途中的旋转

• “向下路途中的旋转”是用来解决“向下路途中的颜色变换”可能带来的红色父节点与红色子节点连接的违规问题，有“X节点是外侧子孙节”点和“X节点是内侧子孙节点”两种情况。
  此时不必纠结“X节点”是什么，下文将会说明。
• X节点是外侧子孙节点：
  • S1-情形：当前二叉树如下，待插入值3，节点3应该插在节点6的左子节点。
    
  • S2-从根节点向下走，走到节点12发现需要对其及子节点进行颜色变换，变换后发现节点12与其父节点25违反了红-黑规则③。
    
  • S3-此时把节点12记作X，X的父节点25记作P，X的祖父节点50记作G，接下来仿照（4）中的可能性2：P是红色的，X是G的一个外侧子孙点情况进行操作。
    
  • S3-1-将G节点和P节点颜色改变。
    
  • S3-2-以G节点为顶点，进行X节点向上方向的旋转（此处是右旋）。发现树平衡了！
    
  • S4-重新从根节点25向下走，去寻找合适的位置插入节点3。发现根节点25有两个红色子节点，需要进行颜色变换。
    
  • S5-找到合适的位置插入节点3，结束。
    

  注意：上文展示了“X节点是外侧子孙节点”情况下的一个完整的插入过程，其中整个S3部分才是“向下途中的旋转”。

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

  注意：上文展示了“X节点是内侧子孙节点”情况下的一个完整的插入过程，其中整个S3部分才是“向下途中的旋转”。

6 删除

• 删除过程过于复杂，很多程序员都用不同的方法回避它，一种方法是为删除节点做个标记而不实际地删除它。

7 效率

• 查找：O(logN)——查找方法和普通二叉搜索树一样，效率相同。
• 插入和删除：O(logN)——相对于普通二叉搜索树，增加了一个常数因子（颜色变换和旋转的时间消耗），效率略低于普通二叉搜索树。

参考

[1] Java数据结构和算法（第二版）