知识卡片

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

父链上的秩严格递增

理解等级:中级

按秩合并与路径压缩保持每个非根节点的秩严格小于父节点秩,因此沿任一节点向根走,秩严格递增。

节点一旦不再是根,其秩保持不变;父节点秩可继续上升。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第19章 不相交集合的数据结构 · 查看原书依据

      Lemma 19.4 For all nodes x, we have x.rank ≤ x.p.rank, with strict inequality if x ≠ x.p (x is not a root). The value of x.rank is initially 0, increases through time until x ≠ x.p, and from then on, x.rank does not change. The value of x.p.rank monotonically increases over time.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[20000,30000))。 - 结论依据:原文引理19.4和推论19.5给出非根父子秩关系与路径单调性。 - 原始内容:Lemma 19.4 For all nodes x , we have x . rank ≤ x . p . rank , with strict inequality if x ≠ x . p ( x is not a root). The value of x . rank is initially 0, increases through time until x ≠ x . p , and from then on, x . rank does not change. The value of x . p . rank monotonically increases over time.