作者热门文章
- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
有没有可能一个红色的父节点只有一个黑色的子节点?我一直在网上玩红/黑树模拟器,但我无法设法让这种情况发生。
问这个问题的原因是我相信我的代码中有一个不必要的 IF...
if (temp_node->color == BLACK && node->color == RED)
{
node->color = BLACK;
global_violation = false;
}
感谢您的任何反馈!
最佳答案
不,这是不可能的。
请记住,在红/黑树中,从树根到树的所有路径都必须经过相同数量的黑色节点(这是红/黑树不变量之一)。
如果你有一个红色节点 x
和一个黑色 child y
,它不能有另一个红色 child (因为这打破了红色节点不能的红/黑不变量'没有红色的 child )。
这意味着通过 x
到丢失的 child 的路径将比通过 x
然后到 y< 的路径至少少一个黑色节点
,然后从那里离开树,打破红/黑树不变量。
关于c++ - 红黑树~1子删除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35262353/
我正在实现红黑 SOR 的并行版本。 我想获得每个进程的最大误差的 MPI_Allreduce 部分不起作用。它永远不会改变,即使只有一个过程,它也会给出高于 2.0 的值。怎么回事?? 这是代码,有
我为拉普拉斯方程(一个简单的加热板问题)在我的红黑 Gauss-Seidel 求解器中添加了 OpenACC 指令,但是 GPU 加速的代码并不比 CPU 快,即使对于大问题也是如此。 我还编写了一个
我是一名优秀的程序员,十分优秀!