知识卡片
父链上的秩严格递增
按秩合并与路径压缩保持每个非根节点的秩严格小于父节点秩,因此沿任一节点向根走,秩严格递增。
节点一旦不再是根,其秩保持不变;父节点秩可继续上升。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.