知识卡片

普通读书笔记卡 · 5593.b

区域更新需分裂并向上合并

理解等级:初级

向混合图中设一点时,遇到与目标值不同的整块叶可先展开为四个同色子区,再下降到目标;回溯时若四个子区统一,便合并为一个叶。清除操作按相反颜色处理。

这需要保留父路径、更新实际父链接并将坐标映到子区。图11-20只用回边移动node,没有完整画出递归返回与父链接更新,不能据“Done返回”就当合并实现已经齐备。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 11.3 递归细分 · 查看原书依据

      在沿着树向上回去的过程中,所有子节点都为黑的节点将被一个黑色节点替换。当有三个黑色子节点,且第四个子节点也设置为黑色时,就会发生如图11-21所示的情况。 图11-21 合并节点 合并节点不仅可以减少树占用的内存,还可以使树上的许多操作更快,因为合并节点让树并

    参考来源

    - 位置:《计算机系统解密》11.3 递归细分(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0122.html) - 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。 - 原始内容:在沿着树向上回去的过程中,所有子节点都为黑的节点将被一个黑色节点替换。当有三个黑色子节点,且第四个子节点也设置为黑色时,就会发生如图11-21所示的情况。 图11-21 合并节点 合并节点不仅可以减少树占用的内存,还可以使树上的许多操作更快,因为合并节点让树并