红黑树〜1子删除

Question

红父节点有可能只有一个黑子节点吗？我一直在玩红/黑树模拟器在线，我无法设法得到这种情况发生。

背后问这个的原因是我相信我有一个不必要的，如果在我的代码...

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

感谢您的反馈！

Answer 1

不，这是不可能的。请记住，在红/黑树中，从树根开始的所有路径必须通过相同数量的黑节点（即红/黑树不变量之一）。

如果你有一个红色节点x与一个黑人孩子y，它不能有另一个红孩子（因为这打破了红/黑不变红色节点不能有红孩子）。

这意味着通过x到丢失孩子的路径将通过比路径至少少了一个黑色节点通过x，然后y，然后过树从那里，打破了红/黑树不变量。