红黑树~1个孩子删除

Question

红色父节点是否有可能只有一个黑色子节点？我一直在网上玩Red/Black Tree模拟器,我无法设法解决这个问题.

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

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

感谢您的反馈!!

Answer 1

不,这是不可能的.

请记住,在红色/黑色树中,树的根部之外的所有路径都必须通过相同数量的黑色节点(这是红色/黑色树不变量之一).

如果你有一个x带有一个黑色孩子的红色节点y,它就不能有另一个红色孩子(因为它打破了红色/黑色不变量,红色节点不能有红色孩子).

这意味着通过x丢失的孩子的路径将通过至少少于路径的黑色节点x,然后通过,然后y从那里离开树,打破红色/黑色树不变量.