红黑树~1子删除

Question

红色父节点有可能只有一个黑色子节点吗？我一直在网上玩 Red/Black 树模拟器，但我无法设法让这种情况发生。

问这个问题的原因是我相信我的代码中有一个不必要的 IF...

if (temp_node->color == BLACK && node->color == RED)
{
    node->color = BLACK;
    global_violation = false;
}

感谢任何反馈！！

Answer 1

不，这不可能。

请记住，在 red/black 树中，从树根到树的所有路径都必须经过相同数量的黑色节点（这是 red/black 树不变量之一).

如果你有一个红色节点 x 和一个黑色 child y，它不能有另一个红色 child（因为这打破了 red/black红色节点不能有红色的不变量 children).

这意味着通过x到缺失的child的路径将比通过x然后到y的路径至少少经过一个黑色节点，然后从那里离开树，打破 red/black 树不变量。

Answer 2

视情况而定。

目前（2021 年 10 月）维基百科中至少有一张图有一个黑色节点。

如果这是一个混淆，明确排除单节点案例作为新规则可能会有所帮助。