红黑树~1个孩子删除
红色父节点是否有可能只有一个黑色子节点？ 我一直在网上玩Red / Black Tree模拟器，我无法设法解决这个问题。
问这个的原因是我相信我的代码中有一个不必要的IF …
if (temp_node->color == BLACK && node->color == RED) { node->color = BLACK; global_violation = false; } 谢谢你的反馈!!
不，这是不可能的。
请记住，在红色/黑色树中，树的根部之外的所有路径都必须通过相同数量的黑色节点（这是红色/黑色树不变量之一）。
如果你有一个带有一个黑色孩子y的红色节点x ，则它不能有另一个红色孩子（因为它打破红色/黑色不变量，红色节点不能有红色孩子）。
这意味着通过x到丢失的子节点的路径将通过至少比通过x的路径少一个黑色节点，然后到y ，然后从那里离开树，打破红色/黑色树不变量。