红黑树〜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屋!