红黑树删除未知行为
Red black tree deletion unknown behaviour
我给红黑树输入了几个数。 (41; 38; 31;
12; 19; 8）删除8和12（第一个截图）后，它进入了第二个截图的类型。我不明白为什么 31 变成红色。请帮我解决这个问题？如果可以，请提及与此相关的案例。
谢谢！
如果你在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, SL for S's left child, and SR for S's right child
所以现在我们有删除之后，但之前 re-colouring:
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.
如果省略上述 colour-swap，将违反此不变量。
我给红黑树输入了几个数。 (41; 38; 31; 12; 19; 8）删除8和12（第一个截图）后，它进入了第二个截图的类型。我不明白为什么 31 变成红色。请帮我解决这个问题？如果可以，请提及与此相关的案例。 谢谢！
如果你在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, SL for S's left child, and SR for S's right child
所以现在我们有删除之后，但之前 re-colouring:
P = 0019（红色）
N = 一片NIL叶子，0019
的左边child
S = 0031,0019
描述确定了几个案例，手头的案例是以下一个：
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.
如果省略上述 colour-swap，将违反此不变量。