我给一棵红黑相间的树输入了几个数字。(41;38;31;
12;19;8)删除8和12(第一个屏幕截图)后,它进入第二个屏幕截图的类型我不明白为什么那31号会变成红色。请帮帮我?如果你能提及与此相关的案件。
谢谢您!

最佳答案

如果您在Wikipedia上查看删除算法的说明,则可以将节点的命名映射到树,如下所示:
M=0012,要删除的黑色节点
C=零时12分以下的零叶(零叶始终被视为黑色)
文章接着谈到你的实际案例:
复杂的情况是m和c都是黑色的。[…]我们首先将M替换为其子C[…]我们将重新标记此子C(在其新位置)N及其兄弟(其新父的其他子)s[…]我们还将使用P表示N的新父,SL表示s的左子,SR表示s的右子
所以现在我们在移除之后,但在重新着色之前:
algorithm - 红黑树删除未知行为-LMLPHP
P=0019(红色)
n=无叶,0019的左子
S=0031,0019的右孩子
说明中列出了几个案例,目前的案例如下:
案例4:S和S的孩子是黑色的,而P是红色的。在这种情况下,我们只需交换s和p的颜色。
此颜色交换的原因如下:
这不会影响通过s的路径上的黑色节点的数量,但它会在通过n的路径上的黑色节点的数量上添加一个,以弥补这些路径上已删除的黑色节点。
回想一下,在红黑树中,这个不变量必须保持(property 5):
从给定节点到其任何后代nil节点的每条路径都包含相同数量的黑色节点。
如果省略上述颜色交换,则会违反此不变量。

10-07 19:16
查看更多