- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我向一棵红黑树输入了几个数字。 (41; 38; 31;12; 19; 8)删除8和12(第一个截图)后,它进入了第二个截图的类型。我不明白为什么 31 变成红色。请帮我解决这个问题?如果可以,请提及与此相关的案例。谢谢!
最佳答案
如果你在Wikipedia上查看删除算法的解释,您可以将它们的节点命名映射到您的树,如下所示:
M = 0012,要移除的黑色节点
C = 0012 以下的 NIL 叶子(NIL 总是被认为是黑色的)
文章接着说了你的实际情况:
The complex case is when both M and C are black. [...] We begin by replacing M with its child C. [...] We will relabel this child C (in its new position) N, and its sibling (its new parent's other child) S [...] we will also use P for N's new parent, SL for S's left child, and SR for S's right child
所以现在我们在移除之后,但在重新着色之前:
P = 0019(红色)
N = NIL 叶子,0019 的左 child
S = 0031,0019的右 child
描述确定了几个案例,手头的案例是以下一个:
Case 4: S and S's children are black, but P is red. In this case, we simply exchange the colors of S and P.
解释了这种颜色交换的原因:
This does not affect the number of black nodes on paths going through S, but it does add one to the number of black nodes on paths going through N, making up for the deleted black node on those paths.
回想一下,在红黑树中必须维护这个不变量(property 5):
Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.
如果省略上述颜色交换,就会违反此不变量。
关于algorithm - 红黑树删除未知行为,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53665271/
我正在实现红黑 SOR 的并行版本。 我想获得每个进程的最大误差的 MPI_Allreduce 部分不起作用。它永远不会改变,即使只有一个过程,它也会给出高于 2.0 的值。怎么回事?? 这是代码,有
我为拉普拉斯方程(一个简单的加热板问题)在我的红黑 Gauss-Seidel 求解器中添加了 OpenACC 指令,但是 GPU 加速的代码并不比 CPU 快,即使对于大问题也是如此。 我还编写了一个
我是一名优秀的程序员,十分优秀!