知识卡片

普通读书笔记卡 · 3634.a.6.e

伪距离沿父链求原树深度

理解等级:高级

深度维护题允许并查集森林的形状不同于原树。

给每个节点保存伪距离,使从节点到集合根路径的伪距离之和等于该节点在原树中的深度;路径压缩时必须同步修正这些值,具体算法仍待设计。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[40000,45000))。 - 结论依据:原文明确伪距离的路径求和不变量,后续实现作为题目提出。 - 原始内容:The key idea is to maintain in each node v a “pseudodistance” v . d , which is defined so that the sum of the pseudodistances along the simple path from v to the root of its set S i equals the depth of v in T i .