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

摘要

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

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-huKQAtRO-1641388184611)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-remove2.png)]

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

红黑树的 5 条性质:

  1. 节点必须是 RED 或者 BLACK;
  2. 根节点是 BLACK;
  3. 叶子节点都是 BLACK,这里要特别留意,叶子节点存在两个空节点,只有一个子树的节点,另外一个不存在的子树也是一个空节点。
  4. RED 节点的子节点都是 BLACK,RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上,不会出现 2 个连续的 RED 节点
  5. 从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。

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

 

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-la1SeISr-1641388184615)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-remove.png)]

第三种就是它既是 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 树的思维在里面才能更好的理解它的删除。