原书出处
Introduction to Algorithms, Fourth Edition
19 第19章 不相交集合的数据结构
ompression. In order to prove this bound, we first prove some simple properties of ranks.
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.
Proof The proof is a straightforward induction on the number of operations, using the imp
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter019.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea