红黑树最多三次旋转达到平衡

一点基础

五个性质

1. 节点是红色或黑色
2. 根节点是黑色
3. 所有叶子节点是黑色（叶子节点是NIL节点，为了性质5到叶子节点具有相同数目黑色节点）
4. 从每个叶子到根的所有路径上不能有两个连续的红色节点
5. 从任一节点到其叶子的所有路径包含相同数目黑色节点

旋转

左旋

左旋.png

右旋

右旋.png

子节点

• 为了方便后面讲解插入和删除，这里定义个子节点指代非叶子节点（NIL）

插入

• 默认插入的子节点总是红色的，因为插入黑色的，肯定会破坏性质5；下面根据插入子节点的父亲颜色分三种情况讨论

1. 没有父亲节点，父亲节点无颜色，插入子节点作为新的根节点，变为黑色，结束；
2. 父亲节点为黑色，插入子节点未破坏任何性质，结束；
3. 父亲节点为红色，可以分为两种情况讨论
   1. 叔叔节点为红色
   2. 叔叔节点为黑色子节点或叶子节点，可以根据插入子节点是否与父亲节点在同一边，分为两种情况讨论
      1. 和父亲节点不在同一边
      2. 和父亲节点在同一边

• 这就是插入节点所面对的所有情况了，一次插入平衡的流程如下：
  
  插入平衡流程图.PNG

旋转次数

• 从流程图可以看出，一次插入最多2次旋转，是父红叔不红，插入子节点与父节点不在同一边时

父亲为红色子节点的三种情况

父叔都为红

• 将叔叔节点变为黑色，祖父节点变为红色，这样没有破坏任何性质

• 需要协调祖父节点为红色的问题，把祖父节点当成新插入的节点再处理一次即可

  
  
  Red-black_tree_insert_case_3.png

父红叔不为红，插入子节点和父亲不在同一边

• 这种情况思路是把这边多余红色分到另一边去，再同一边时可旋转改变，所以需要把插入子节点旋转到和父亲节点在同一边

  
  
  Red-black_tree_insert_case_4.png

父红叔不为红，插入子节点和父亲在同一边

• 这种情形经过一次旋转变色可以达到把多的红色分到另一边的目的，因为另一边是黑色，加一个红色节点不会破坏性质

  
  
  Red-black_tree_insert_case_5.png

删除

• 删除要复杂些，不能从颜色的层面看所有情况，需要从删除节点的儿子子节点情况来看，同样分为三类
  • 有二个子节点
  • 有一个子节点
  • 没有子节点

有二个子节点

• 思路：找到左边或右边最小或最大的子节点，替换删除节点，没有改变颜色，最小或最大节点之上什么都没被影响，问题被转换为了有一个子节点或没有子节点，因为找的是最小或最大的，至少有一边是没有的；流程如下：
  
  删除有二个子节点流程图.PNG

有一个子节点

• 删除节点不能为红色：因为他有一个子节点，根据性质4这个子节点肯定是黑色，而这会导致删除节点没有子节点的边到叶子节点的黑色节点至少少1，违反性质5，所以删除节点不能为红色
• 删除节点为黑色：同样的，根据性质5，删除节点的这个儿子子节点肯定是红色，不然就违反了性质5；只需要简单的去掉删除节点，再用儿子子节点替代他的位置，变为黑色；结束

没有子节点

1. 删除节点是红色，删除不影响红黑树性质，直接删除

2. 删除节点是黑色

   • 问题：到删除节点这里的叶子节点的路径上少了个黑色节点，违反了性质5

   • 思路

     • 减少一个删除节点父亲节点到叶子节点路径的黑色节点，把父亲节点当做新的填充上去的节点（第一次填充的是叶子节点），递归处理
     • 在不增加另一边父亲节点到叶子节点的黑色节点数量的情况下，将删除节点这边增加个黑色节点

   • 情形（N:代表删除节点被移除后，补上去的节点，最开始是叶子节点（NIL））

     1. N是新的根，结束
     2. 兄弟是红色
     3. 兄弟是黑色
        1. 兄弟的儿子都是黑色
           1. 父亲节点是黑色
           2. 父亲节点是红色
        2. 兄弟的儿子有红色
           1. 兄弟儿子与兄弟同边的是黑色
           2. 兄弟儿子与兄弟同边的是红色

     这就是当删除节点没有子节点并且删除节点是黑色的时候所有的情形了，它的平衡流程图如下：

     
     
     无子节点流程图.PNG

旋转次数

• 从流程图不难看出，删除最多旋转3次，情形为：兄弟是红色->兄弟黑色、兄儿子与兄不同边红色，同边黑色、父亲节点颜色红黑都可->兄弟黑色、兄儿子与兄同边红色，另一边红黑都可、父亲节点颜色红黑都可

兄弟是红色

• 需要转换为填充节点是黑色的情形

• 将红色的兄节点旋转到父亲节点位置，并交换之前父亲节点和兄节点颜色，这样可以保持和之前一致的到叶节点黑色数目，并使填充节点N的新兄节点为黑色

  
  
  Red-black_tree_delete_case_2.png

兄弟黑色、兄儿子黑色、父亲节点黑色

• 没有红色可以做转换，将兄变为红色，以父亲作为新的补充节点N循环处理

  
  
  Red-black_tree_delete_case_3.png

兄弟黑色、兄儿子是黑色、父亲节点是红色

• 直接交换父亲节点和兄节点颜色;颜色满足，到叶子节点的的黑色数目没变，N这边加了1（父亲），兄这边没变,达到平衡

  
  
  Red-black_tree_delete_case_4.png

兄弟黑色、兄儿子与兄同边红色，另一边红黑都可、父亲节点颜色红黑都可

• （白色节点表示红黑都可以，但必须维持和删除钱一样颜色）以父节点旋转，将兄节点旋转到父亲的位置，并将与兄同边的儿子变为黑色，而原父节点变为黑色，在父节点那个位置的子节点颜色与之前保持一致，这样相当于N这边增加了一个黑色，原父节点；而兄那边S节点顶替了父节点位置与颜色，但与兄同边儿子红色节点变为了黑色，加上了1，刚好持平，局部达到了平衡，达到平衡

  
  
  Red-black_tree_delete_case_6.png

兄弟黑色、兄儿子与兄不同边红色，同边黑色、父亲节点颜色红黑都可

• 将兄儿子红色不同边旋转到与兄同边，并交换兄和这个节点颜色，即可以形成兄弟黑色、兄儿子与兄同边红色，另一边红黑都可、父亲节点颜色红黑都可情形
  
  Red-black_tree_delete_case_5.png

小结

• 从上面插入和删除知道：插入最多2次旋转达到平衡、删除最多3次旋转达到平衡；所以红黑树最多三次旋转达到平衡

参考：红黑树-维基百科