【数据结构与算法】系列十七 - 红黑树-删除节点

删除红黑树的节点，需要了解二叉搜索树的删除和B树。

强调：4阶B树只是为了更好的理解红黑树，两者没有必然联系。删除是在最后一层处理的。

一、删除节点

B树中，最后真正被删除的元素都在叶子节点中。所以在红黑树中，删除节点一定是在最后一层。

1.1. 删除 - RED节点

直接删除，不用作任何调整。因为删除叶子节点中的红色节点并没有影响红黑树的性质。

例如删除上面树中的节点17、33、50、72，整棵树依然是红黑树。

1.2. 删除 - BLACK节点

有3种情况：

1. 拥有2个RED子节点的BLACK节点（例如：节点25）
   • 不可能被直接删除，因为会找它的前驱或后继替代删除。例如删除节点25，找到节点25的前驱节点17或后继节点33，把节点25的值替换为前驱或后继的值，然后把前驱或后继删除即可（此时的删除参考上面的1.1）。因此不用考虑这种情况。
2. 拥有1个RED子节点的BLACK节点 （例如：节点46和节点76）
3. BLACK是叶子节点

1.2.1. 删除 – 拥有1个RED子节点的BLACK节点

例，删除下图中的节点46和节点76：

如果删除节点46和和节点76，只需要把节点55指向节点50，并把节点50染成黑色即可。删除节点72同理。

删除节点后，还需要把替代的子节点染成BLACK。

如果按照二叉搜索树的角度，需要判断是否是叶子节点。但我们建议按照红黑树的特点（非红即黑）进行判断，节点88没有子节点，意味着用以取代节点88的子节点是空的，也就是用以取代的子节点是黑色。

在红黑树中的判断尽量和颜色有关（例如添加节点的时候判断uncle是否为红色）。

实现思路：

判定条件：用以替代的子节点是RED

将替代的子节点染成BLACK，即可保持红黑树性质。

1.2.2. 删除 – BLACK叶子节点 – sibling为BLACK

例如删除下面红黑树中的节点88，从B树角度看的话，会发生下溢。解决下溢时，优先看删除节点的兄弟节点是否能借一个元素。如果能借，兄弟节点会有以下三种情况：

所以，要想从兄弟节点借一个元素，兄弟节点必须至少要有一个红色子节点。而且兄弟节点一定是黑色，否则从B树角度出发，兄弟节点就会和父节点合并为一个超级节点，此时删除节点和兄弟节点就成父子关系了。

综上分析后，删除BLACK叶子节点，要想从兄弟节点借一个元素，兄弟节点则必须满足下面的条件：

1. 兄弟节点是BLACK
2. 兄弟节点必须含有红色子节点

删除节点后，向兄弟节点借元素解决下溢问题，其实就是兄弟节点的旋转操作。但是旋转之后的的中心节点颜色不能变（比如旋转前中心节点是红色，旋转后也应该还是红色），中心节点的左右子节点染成黑色即可（B树角度出发，左右独立节点必然是黑色）。

上面最后一种情况是LL（80-76-72，让80右旋转），其实还有另外一种情况是LR（80-76-78，先让76左旋，后80左旋）：

虽然结果不一样，但依然是一棵红黑树。

实现思路：

判定条件：如果sibling至少有1个RED子节点

1. 进行旋转操作
2. 旋转之后的中心节点继承parent的颜色
3. 旋转之后的左右节点染为BLACK

上面分析的是向兄弟节点借一个元素的前提下如何删除一个节点保持红黑树的性质，下面就来看下如果兄弟节点不能借，怎么办？

在B树中，如果兄弟节点不能借（借了也会下溢），就会把删除节点的父节点和子节点合并。合并后父节点是黑色，子节点是红色。

实现思路：

判定条件：sibling 没有1个RED子节点。

1. 将sibling染成RED，parent染成BLACK即可修复红黑树性质。

如果parent是BLACK，会导致parent也下溢，这时只需要把parent当做被删除的节点处理即可（如下图）。

从B树角度看，假如兄弟节点只有一个元素并且是黑色，如果被删除节点的父节点是红色，父节点必然至少还有一个黑色子节点（不会产生下溢）。如果父节点是黑色，则可能只有一个元素（会产生下溢）。

1.2.3. 删除 – BLACK叶子节点 – sibling为RED

上图从B树角度看，删除上面树中的节点88会产生下溢，需要看兄弟节点能否借一个元素，如果兄弟节点不能借，需要父节点向下合并。可是节点88的兄弟节点不是76，而是55，所以我们想办法让兄弟节点55的儿子76变成节点88的兄弟，之后也适用1.2.2情况。

• 把46-55-80的80进行右旋转（LL），就可以把节点76变为节点88的兄弟节点：

• 旋转后就可以适用1.2.2的情况了：

实现思路：

判断条件：如果sibling是RED

1. sibling染成BLACK，parent染成RED；
2. 进行旋转后，又回到sibling是BLACK的情况。

二、具体代码

// node是被删除节点，replacement是用以取代的节点
protected void afterRemove(Node<E> node, Node<E> replacement) {
  // 如果删除的节点是红色
  if (isRed(node)) return;
  
  // 用以取代node的子节点是红色
  if (isRed(replacement)) {
    black(replacement);
    return;
  }
  
  Node<E> parent = node.parent;
  // 删除的是根节点
  if (parent == null) return;
  
  // 删除的是黑色叶子节点【下溢】
  // 判断被删除的node是左还是右
  boolean left = parent.left == null || node.isLeftChild();
  Node<E> sibling = left ? parent.right : parent.left;
  if (left) { // 被删除的节点在左边，兄弟节点在右边
    if (isRed(sibling)) { // 兄弟节点是红色
      black(sibling);
      red(parent);
      rotateLeft(parent);
      // 更换兄弟
      sibling = parent.right;
    }
    
    // 兄弟节点必然是黑色
    if (isBlack(sibling.left) && isBlack(sibling.right)) {
      // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
      boolean parentBlack = isBlack(parent);
      black(parent);
      red(sibling);
      if (parentBlack) {
        afterRemove(parent, null);
      }
    } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
      // 兄弟节点的左边是黑色，兄弟要先旋转
      if (isBlack(sibling.right)) {
        rotateRight(sibling);
        sibling = parent.right;
      }
      
      color(sibling, colorOf(parent));
      black(sibling.right);
      black(parent);
      rotateLeft(parent);
    }
  } else { // 被删除的节点在右边，兄弟节点在左边
    if (isRed(sibling)) { // 兄弟节点是红色，转换兄弟节点后就可以统一处理
      black(sibling);
      red(parent);
      rotateRight(parent);
      // 更换兄弟
      sibling = parent.left;
    }
    
    // 兄弟节点必然是黑色
    if (isBlack(sibling.left) && isBlack(sibling.right)) {
      // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
      boolean parentBlack = isBlack(parent);
      black(parent);
      red(sibling);
      if (parentBlack) {
        afterRemove(parent, null);
      }
    } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
      // 兄弟节点的左边是黑色，兄弟要先旋转
      if (isBlack(sibling.left)) {
        rotateLeft(sibling);
        sibling = parent.left;
      }
      
      color(sibling, colorOf(parent));
      black(sibling.left);
      black(parent);
      rotateRight(parent);
    }
  }
}