红黑树

红黑树的性质

1. 红黑树的根节点都是黑色的

2. 不能重现连续的红色(红色节点的子节点必须是黑色)

3. 所有叶子节点（NIL / null）被视为黑色

4. 从任一节点到其所有后代叶子节点的路径上，包含相同数目的黑色节点

5. 节点要么是红色要么是黑色

记法：左根右(二叉搜索树)，根叶黑，不红红，黑路同

插入规则

插入节点和正常的二叉树一样插入(默认插入的是红色的节点，红色比黑色更不容易破坏平衡)，插入之后可能破坏了平衡，所以需要从下到上调整。

可能出现三种情况

parent = cur.parent，grand = parent.parent，uncle = grand

插入节点是根节点

直接染成黑色

插入节点的叔叔是红色

parent和uncle设为黑，grand设为红色，将cur指向grand,继续向上修复

插入节点的叔叔是黑色

LL：

parent和cur都是左节点

LR：

parent和cur一左一右

RR：

parent和cur都是右节点

RL：

parent和cur一右一左

LL

grand右旋，对旋转点(grand)和中心点(parent)进行变色

旋转前

      G(B?)
     /
   P(R)
  /
 z(R)

旋转+变色

     P(B)
    /   \
  z(R)  G(R)

LR

parent左旋，grand右旋。对旋转点(grand)和中心点(z)进行变色

旋转前

    G
   /
  P
   \
    z

旋转+变色

     z(B)
    /   \
  P(R)  G(R)

RR

grand左旋，对旋转点(grand)和中心点(parent)进行变色

旋转前

 G
  \
  P(R)
   \
   z(R)

旋转+变色

   P(B)
  /   \
 G(R) z(R)

RL

parent右旋，grand左旋。对旋转点(grand)和中心点(z)进行变色

旋转前

  G
   \
    P
   /
  z

旋转+染色

     z(B)
    /   \
  G(R)  P(R)

总结：LL和RR都是G向反方向(R/L)旋转，LR和RL都是P先L/R旋转，G再R/L旋转

删除规则

左右都有孩子

• 后继：“中序遍历中，紧跟在当前节点之后的那个节点”，即 比 x 大的最小值。

• 前驱：“中序遍历中，紧挨在当前节点之前的那个节点”，即 比 x 小的最大值。

规则：先找到“中序后继”或“中序前驱”来替换它的值，然后再删除那个后继/前驱节点。一般默认为后继

没有孩子

红节点：直接删除即可

⭐黑节点：将null设置为双黑节点(这个节点是黑色，并算两个)

• 兄弟节点是黑色

  • 兄弟至少有一个红孩子:(LL,LR,RR,RL)变色+旋转

    • LL：兄弟在父节点左侧并且至少有左孩子是红色

      处理前

              P
             / \
         (B)S   D(BB)
           /
          R(R)

      R 变成 S 的颜色

      S 变P

      P 变黑

      对 P 执行 右旋

      双黑变单黑

      处理后：

             S(原P色)
            / \
         R(B)  P(B)
                 \
                 D(B)

    • RR：兄弟在父节点右侧并且至少有右孩子是红色

      处理前

          P
         / \
      D(BB)  S(B)
               \
                R(R)
      

      R 变成 S 的颜色

      S 变P

      P 变黑

      对 P 执行 左旋

      双黑变单黑

      处理后

              S(原P色)
             / \
          P(B)  R(B)
         /
       D(B)

    • LR：兄弟节点在左侧并且至少有右孩子是红色

      处理前

              P
             / \
          (B)S   D(BB)
             \
              R(R)

      R 变成 P 原来的颜色
      P 变黑
      对 S 左旋，再对 P 右旋
      双黑变单黑
      处理后：

              R(原P色)
             / \
          S(B)  P(B)
                  \
                  D(B)

    • RL：兄弟节点在右侧并且至少有左孩子是红色

      处理前

              P
             / \
          D(BB)  S(B)
                 /
               R(R)

      R 变成 P 原来的颜色

      P 变黑

      对 S 右旋，再对 P 左旋

      双黑变单黑

      处理后

              R(原P色)
             / \
          P(B)  S(B)
         /
       D(B)

  • 兄弟的孩子都是黑色：兄弟变黑，双黑上移(遇红或根变单黑)

            P
           / \
        S(B)   D(BB)
       / \
     L(B) R(B)

    1. 将 S 染成 红色
    2. 将 D(BB) 的双黑“向上转移”：即把 P 作为新的双黑节点处理（D = P）

    如果 P 原来是红色，则：

    • 把 P 染黑（双黑消除，修复结束）

    如果 P 原来是黑色，则：

    • 把 P 当作新的 D(BB)，继续向上修复（递归或循环）

• 兄弟节点是红色：兄父变色，朝双黑旋转

      P
     / \
  D(BB)  S(R)
         / \
      L(B) R(B)
  

  交换颜色：P 染红，S 染黑

  如果兄弟在右，则对 P 左旋；兄弟在左，则对 P 右旋。

  旋转后，新的兄弟一定是黑色，问题转化为前面的“兄弟为黑色”情况，继续处理。

只有左孩子/只有右孩子

孩子代替，然后变黑即可

总结

图片