c++ - 红黑树 ~ 1 个子删除

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

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

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

感谢您的任何反馈!!

最佳答案

不，这是不可能的。

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

如果您有一个红色节点 x 和一个黑色子节点 y ，则它不能有另一个红色子节点(因为这打破了红色节点不能有红色子节点的红色/黑色不变量)。

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

关于c++ - 红黑树 ~ 1 个子删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35262353/