数据结构树详解数据结构与算法-基础

俬亽専署 2023-04-09 12:02:40

摘要

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

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

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

红黑树的 5 条性质：

节点必须是 RED 或者 BLACK；

根节点是 BLACK；

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

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

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

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

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

添加的节点是 parent 的左子节点，存在 parent 的右子节点；
添加的节点是 parent 的右子节点，存在 parent 的左子节点；
添加的节点是 parent 的左子节点，不存在 parent 的右子节点；
添加的节点是 parent 的右子节点，不存在 parent 的左子节点；

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

这种情况需要在添加节点之后，做相应的处理，让它重新达到红黑树的平衡（满足红黑树的 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，需要做的处理是：parent 染成 BLACK，grand 染成 RED；对 grand 进行单旋操作，即若是 LL 就右旋转，RR 就是左旋转。
若失衡情况是 RL\LR，需要做的处理是：自身染成 BLACK，grand 染成 RED；进行两次旋转，如果是 RL，parent 右旋转，grand 左旋转，如果是 LR，parent 左旋转，grand 右旋转。

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

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

所以根据红黑树的性质 4 需要做的处理是：
parent 和 uncle 染成 BLACK；
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); } }
,