数据结构与算法-基础(十五)红黑树(3)删除元素

摘要

红黑树删除节点，和 B 树删除节点的情况非常的接近。理解红黑树删除节点之后的恢复操作前，再过一下 B 树的删除逻辑，这样会更好的理解红黑树的删除逻辑。各种处理操作就不会离开一个主要思想，就是红黑树的 5 条性质。

在 B 树中，最后真正需要删除的一定是叶子节点，就算删除的不是叶子节点，也可以先和它的前驱或者后继交换位置之后，删除被交换到叶子的节点。红黑树可以简单的移动一下节点的位置，就能变成 B 树（如下图所示），所以红黑树的删除就可以转换为对 B 树的删除。

红黑树的节点被删除之后，就要判断是否还符合红黑树性质，若不符合性质时，就要做恢复红黑树的处理。判断的依据就是红黑树的 5 条性质，尤其是性质 4。

红黑树的 5 条性质：

节点必须是 RED 或者 BLACK；

根节点是 BLACK；

叶子节点都是 BLACK，这里要特别留意，叶子节点存在两个空节点，只有一个子树的节点，另外一个不存在的子树也是一个空节点。

RED 节点的子节点都是 BLACK，RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上，不会出现 2 个连续的 RED 节点。

从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。

首先看删除的叶子节点是 RED，那么就不需要做任何处理，依然满足红黑树的性质。比如删除元素 17、33、55 和 72。如下图所示：

接下来，删除的叶子节点是 BLACK，就有 3 种情况，首先第一种就是有两个 RED 子节点（如下图元素 25），因为有两个叶子节点，所以若要删除也是找子节点替换，然后删除与它交换的叶子节点，不可能直接删除的，所以不考虑。第二种呢，是有一个 RED 子节点（比如元素 46、76），这种情况就可以直接拿这个 RED 子节点替换 BLACK 节点，然后将这个 RED 子节点染成 BLACK，依然满足红黑树的性质。

第三种就是它既是 BLACK，也是叶子节点（比如元素 88），删除这个节点会造成 B 树下溢出。那么就要做调整来消除下溢的影响。

这里要拿它的兄弟节点（sibling）来帮助处理。如果它的 sibling 是 BLACK时，若 sibling 至少有一个 RED 的子节点，就可以根据它的失衡情况做旋转，旋转之后的中心节点染成 parent 的颜色，他的左右节点就染成 BLACK。

若 sibling 一个 RED 节点都没有，而 parent 是 RED 时，就直接将 sibling 染成 RED，parent 染成 BLACK，就满足了红黑树的性质。但是 parent 是 BLACK 时，就会导致 parent 下溢，那么就把 parent 当作被删除的节点去处理即可。

若 sibling 是 RED，那么就需要将 sibling 染成 BLACK，parent 染成 RED，进行旋转之后，就会回到 sibling 是 BLACK 的情况。然后继续按照 sibling 是 BLACK 的情况继续处理。

现在开始代码实现删除红黑树的节点之后的处理：

删除节点之后，当前节点位置要不就是不存在，为 null，要不就是其他节点被替换到当前节点。所以下面函数中传递的参数就是删除位置的节点：

void afterRemove(Node<E> node) { }

这里要判断当前节点的颜色，如果是红色，那么就染黑处理。下溢情况会再次调用 afterRemove 函数。

// 如果删除的节点是红色
// 或者 用于取代删除节点的子节点是红色
if (isRed(node)) {
  black(node);
  return;
}

接下来就是要判断，删除的节点是否是根节点，如果是，就根节点，也可以不用操作：

Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;

下面就是被删除的节点是黑色节点，那么这时候就要看它的兄弟节点是否可以拿出来一个节点来补位。这里先以兄弟节点是当前节点的右侧来处理，兄弟节点是当前节点的左侧刚好与前面情况相反。

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;
}

经过这一番处理之后，剩下的过程必然是处理兄弟节点是黑色的情况了。

这时就只有两种情况了，第一种就是兄弟节点没有子节点可以借出，那只能把父节点向下合并了，向下合并之后可能产生下溢。所以就需要把父节点重新走一遍 afterRemove 函数。

// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {  
  // 兄弟节点没有一个红色子节点，父节点要向下跟兄弟节点合并  
  boolean parentBlack = isBlack(parent);  
  black(parent);
  red(sibling);  
  if (parentBlack) {
    afterRemove(parent);
  }
} else {
  // 实现
}

第二种情况，就是兄弟节点中有子节点可以借出，那就借节点：

// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {  
  // 实现  
} else {
  // 兄弟节点至少有一个红色节点，向兄弟节点借元素  
  // 兄弟节点的右边是黑色，兄弟要先旋转  
  if (isBlack(sibling.right)) {    
    rotateRight(sibling);    
    sibling = parent.left;  
  }  
  color(sibling, colorOf(parent));  
  black(sibling.right);  
  black(parent);  
  rotateLeft(parent);
}

最后就是要处理兄弟节点是当前节点的左侧情况，它和上面的情况正相反：

// 删除的是黑色叶子节点【下溢出】
// 判断删除的 node 是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) { 
  // 被删除的节点在左侧，兄弟节点在右侧    
  // 实现
} else { 
  // 删除的节点在右边，兄弟节点在左边  
  if (isRed(sibling)) {
    // 兄弟节点是红色    
    black(sibling);    
    red(parent);    
    rotateRight(parent);    
    // 更换兄弟    
    sibling = parent.left;  
  }  
  // 兄弟节点必然是黑色  
  if (isBlack(sibling.left) && isBlack(sibling.right)) {    
    // 兄弟节点没有一个红色子节点，父节点要向下跟兄弟节点合并    
    boolean parentBlack = isBlack(parent);    
    black(parent);    
    red(sibling);    
    if (parentBlack) {      
      afterRemove(parent);    
    }  
  } else { 
    // 兄弟节点至少有一个红色节点，向兄弟节点借元素    
    // 兄弟节点的右边是黑色，兄弟要先旋转    
    if (isBlack(sibling.left)) {      
      rotateRight(sibling);      
      sibling = parent.right;    
    }    
    color(sibling, colorOf(parent));    
    black(sibling.left);    
    black(parent);    
    rotateRight(parent);  
  }
}

这这里已经全部梳理完红黑树删除节点之后恢复的处理了。删除节点要加入 B 树的思维在里面才能更好的理解它的删除。