algorithm - 红黑树删除未知行为

Question

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

Answer 1

如果你在Wikipedia上查看删除算法的解释，您可以将它们的节点命名映射到您的树，如下所示:

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

文章接着说了你的实际情况:

The complex case is when both M and C are black. [...] We begin by replacing M with its child C. [...] We will relabel this child C (in its new position) N, and its sibling (its new parent's other child) S [...] we will also use P for N's new parent, S_L for S's left child, and S_R for S's right child

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

P = 0019(红色)
N = NIL 叶子，0019 的左 child
S = 0031，0019的右 child

描述确定了几个案例，手头的案例是以下一个:

Case 4: S and S's children are black, but P is red. In this case, we simply exchange the colors of S and P.

解释了这种颜色交换的原因:

This does not affect the number of black nodes on paths going through S, but it does add one to the number of black nodes on paths going through N, making up for the deleted black node on those paths.

回想一下，在红黑树中必须维护这个不变量(property 5):

Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

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