数据结构与算法-基础(2)

13、数据结构与算法 - 基础：红黑树（2）添加元素

摘要

红黑树添加元素后，需要根据红黑树的 5 条性质判断是否满足，如果不满足就需要做相应的处理使其依然满足红黑树。分析逻辑和实现代码上面有一些比较巧妙的处理点，很值得学习。

若添加元素时，可以先设置添加的元素为 RED，这样就满足红黑树的性质 1、2、3、5。这样只需要想办法满足性质 4 就可以了。

注意：如果添加的元素是根节点，那么就直接把这个节点染成 BLACK 就好。

红黑树的 5 条性质：

节点必须是 RED 或者 BLACK；

根节点是 BLACK；

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

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

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

下面图中是一个红黑树，接下来给这个红黑树中添加元素。
注意：新添加的元素都是添加到叶子节点中。

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

这里先说简单的情况，添加为叶子节点时，它的 parent 是 BLACK。这种情况直接满足性质 4，是不需要做任何处理的。这样的情况有 4 种：

1、添加的节点是parent的左子节点，存在parent的右子节点；
2、添加的节点是parent的右子节点，存在parent的左子节点；
3、添加的节点是parent的左子节点，不存在parent的右子节点；
4、添加的节点是parent的右子节点，不存在parent的左子节点；

剩下的情况就是添加的节点的 parent 是 RED，总共有 8 种情况，如下图：

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

这种情况需要在添加节点之后，做相应的处理，让它重新达到红黑树的平衡（满足红黑树的 5 条性质）。一般有两种处理方式，分别是旋转修复和向上合并。

当节点的 uncle 是 RED 时，做旋转修复，否则就是向上合并。那么为什么用 uncle 作为判断呢？

uncle：称为叔父节点，是 parent 的 sibling

sibling：称为兄弟节点，若自身节点是 parent 的左子节点，那么 sibling 就是 parent 的右子节点，反之亦然。

比如：序号 8 节点的 sibling 是序号 7 节点，uncle 是元素 88 节点。

再比如：序号 1 节点的 sibling 是序号 2 节点，uncle 是元素 46 节点。

首先当前节点是添加到 RED 节点的，那么它的 parent 是 RED 节点，按照红黑树的性质推出，parent 的 sibling 若存在，就必须是 RED。但节点是 BLACK，则 sibling 是不存在的，就会有 LL\RR（比如序号 7\6）或者 LR\RL（比如序号 8\5）的情况出现。

若parent 的 sibling 是红色节点，即存在该节点，这种情况就需要把祖父节点向上合并，保证平衡。向上合并会出现上溢的情况，这个在后面再详细说明。

由上面分析可以解释，需要用 uncle 是否是 RED 来作为判断。下面对这两种情况分别处理。

若uncle 不是 RED，如下图图序号 5、序号 6、序号 7 和序号 8（空节点是 BLACK 节点）。

这里失衡的情况就是如上面这 4 种。根据不同的失衡情况处理如下：

若失衡情况是 LL\RR，需要做的处理是：

1、 parent染成BLACK，grand染成RED；
2、对grand进行单旋操作，即若是LL就右旋转，RR就是左旋转；

若失衡情况是 RL\LR，需要做的处理是：

1、自身染成BLACK，grand染成RED；
2、进行两次旋转，如果是RL，parent右旋转，grand左旋转，如果是LR，parent左旋转，grand右旋转；

若uncle 是 RED，如下图序号 1、序号 2、序号 3、序号 4。

这4种情况不需要旋转操作，但是会出现上溢（第十二期 B 树有解释上溢），需要向上合并解决上溢。

所以根据红黑树的性质 4 需要做的处理是：

1、 parent和uncle染成BLACK；
2、 grand向上合并；

grand 向上合并的操作就是将 grand 染成 RED，然后当作新添加的节点进行处理。grand向上合并之后，可能会继续发生上溢，如果上溢到根节点，将根节点染成 BLACK 就可以了。

接下来按照分析的逻辑来实现代码，这里再次说明，需要先添加节点之后，再做修复红黑树的处理逻辑。所以定义和实现的方法就是 afterAdd。

void afterAdd(Node<E> node) {
   
     
	// 实现代码
  ...
}

首先要通过判断添加节点的 parent 是否为 null，如果是 null，则认为添加的节点是根节点，只需要把这个节点染成 BLACK 就可以了。

Node<E> partner = node.parent;
// 添加的节点是 root 节点, 或者上溢到达了根节点
if (partner == null) {
   
     
  black(node);
  return;
}

接下来判断 parent 的颜色，如果是 BLACK，就不用做处理：

// 父节点是黑色,不做任何处理
if (isBlack(partner)) {
   
     
  return;
}

到这里就需要用 uncle 来处理剩下的处理，通过分析可以发现，当 uncle 为 RED 时，处理的逻辑都是一样的，所以先处理 uncle 为 RED 的情况：

// 叔父节点
Node<E> uncle = partner.sibling();
// 祖父节点
Node<E> grand = red(partner.parent);
if (isRed(uncle)) {
   
      // 叔父节点是红色【B 树节点上溢】

  // 叔父节点和父亲节点染成黑色
  black(uncle);
  black(partner);

  // 把祖父节点染成红色，进行递归操作。当作一个新的 B 数来处理
  afterAdd(grand);
  return;

}

看上面代码，在染色之后就调用了 afterAdd(grand)，就是将 grand 当作新添加的节点来处理，获取 grand 的时候就把它染成 RED。

最后实现 uncle 不是 RED 的情况，这种情况除了染色，还需做旋转处理：

if (isRed(uncle)) {
   
      // 叔父节点是红色【B 树节点上溢】
	// 代码逻辑
} else {
   
      // 叔父节点不是红色

  if (partner.isLeftChild()) {
   
      // L

    if (node.isLeftChild()) {
   
      // LL
      black(partner);
    } else {
   
      // LR
      black(node);
      rotateLeft(partner);
    }
    rotateRight(grand);
  } else {
   
      // R

    if (node.isLeftChild()) {
   
      // RL
      black(node);
      rotateRight(partner);
    } else {
   
      // RR
      black(partner);
    }
    rotateLeft(grand);
  }
}