二叉树 - 红黑树

0. 定义

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。(注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！)
4. 如果一个节点是红色的，则它的子节点必须是黑色的。(没有两个连续的红色节点)

5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

   
   红黑树示例

1. 添加节点

注意：新添加的节点均为红色

1. 如果插入的是根节点，直接涂黑

2. 如果插入节点的父节点是黑色，不用调整
   此时并未破坏原有的树的特性。

3. 如果插入节点的父节点是红色
   这时看叔叔节点

• 如果叔叔节点是红色
  将父节点和叔叔节点变为黑色，祖父节点变为红色，然后将祖父节点看做当前节点继续处理
• 如果叔叔节点是黑色
  • 如果父节点是祖父节点的左孩子，当前节点是其父节点的左孩子，则做LL旋转，互换父节点和祖父节点的颜色
  • 如果父节点是祖父节点的左孩子，当前节点是其父节点的右孩子，则做LR旋转，第二次旋转时互换祖父节点和新的父节点的颜色
  • 如果父节点是祖父节点的右孩子，与上面两种情况互为镜像

2. 删除节点

删除节点和普通二叉查找树删除节点一样，都是删除其后继节点。

以下当前节点均是指其后继结点

1. 如果当前节点是红色，直接删除即可

2. 如果当前节点是黑色，且为根节点，直接删除即可

3. 如果当前节点是黑色（由红黑树的性质可以推断，黑色节点必定有兄弟节点）

• 如果兄弟节点是红色（则兄弟节点的孩子为黑色）
  可以对父节点进行左旋，交换父节点和兄弟节点的颜色，使当前节点的兄弟节点变为黑色，继续进行处理
• 如果兄弟节点是黑色，并且当前节点是父节点的左孩子
  • 如果兄弟节点的两个孩子都是黑色
    交换兄弟节点和父节点的颜色，把父节点当做当前节点，继续处理
  • 如果兄弟节点的右孩子为红色
    交换兄弟节点和父节点的颜色，右孩子变黑，父节点左旋
  • 如果兄弟节点的左孩子为红色
    交换兄弟节点和左子的颜色，兄弟节点右旋，此时变为右子为红色的情况
• 如果兄弟节点是黑色，并且当前节点是父节点的右孩子
  与上面左孩子情况互为镜像

3. 练习

跟着这篇文章操作一遍，基本能全部掌握：数据结构之红黑树插入与删除全程演示

4. 参考

1. 《算法导论》
2. 最容易懂得红黑树
3. 【数据结构和算法05】 红-黑树（看完包懂~）
4. 数据结构之红黑树插入与删除全程演示