红黑树〜1孩子删除 [英] Red Black Tree ~ 1 Child Deletes

问题描述

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

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

  if（temp_node-> color == BLACK&& node-> color == RED）
 {
 node-> color = BLACK; 
 global_violation = false; 
} 
  

感谢任何反馈！

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

如果你有一个红色节点 x 与一个黑人 y ，它不能有另一个红色孩子红色节点不能有红色孩子）。

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

Is it ever possible for a red parent node to have just ONE black child node? I have been playing around with the Red/Black Tree simulator online and I can't manage to get a case of this to happen.

The reason behind asking this is I believe I have an unnecessary IF in my code...

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

Thanks for any Feedback!!

解决方案

No, this isn't possible.

Remember, that in a red/black tree, all paths from the root of the tree off of the tree must pass through the same number of black nodes (that's one of the red/black tree invariants).

If you have a red node x with one black child y, it cannot have another red child (since that breaks the red/black invariant that red nodes can't have red children).

This means that a path through x to the missing child will pass through at least one fewer black node than the path through x, then to y, and then off the tree from there, breaking the red/black tree invariants.

这篇关于红黑树〜1孩子删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！