algorithm - 红黑树删除未知行为

Question

我在红黑树上输入了几个数字。(41; 38; 31; 12; 19; 8) 删除 8 和 12 (第一个截图) 后进入第二个截图的类型。我不明白为什么 31 变成红色。请帮帮我？如果您可以请提及与此相关的案例。谢谢 ！

Answer 1

如果您查看Wikipedia上对删除算法的说明，您可以将它们的节点命名映射到您的树，如下所示：

M = 0012，要移除的黑色节点
C = 0012 以下的 NIL 叶（NIL 总是被认为是黑色的）

文章接着说你的实际情况：

复杂的情况是M和C都是黑色的。[...] 我们首先将M替换为其子C。[...] 我们将重新标记这个孩子C（在它的新位置）N，以及它的兄弟姐妹（它的新父母的另一个孩子）S [...] 我们还将使用P表示N的新父母，S _L表示S的左孩子，S _R代表S的右孩子

所以现在我们在移除之后，但在重新着色之前：

P = 0019（红色）
N = NIL 叶子，0019 的左孩子
S = 0031，0019 的右孩子

该描述确定了几种情况，手头的情况如下：

情况 4：S和S的孩子是黑色的，但P是红色的。在这种情况下，我们只需交换S和P的颜色。

这种颜色交换的原因解释如下：

这不会影响经过S的路径上黑色节点的数量，但它确实会在经过N的路径上的黑色节点数量上加一，从而弥补这些路径上已删除的黑色节点。

回想一下，在红黑树中，这个不变量必须保持（属性 5）：

从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。

如果省略上述颜色交换，则将违反此不变量。