为什么路径压缩不会改变UnionFind中的排名？

Question

我正在通过这里的排名和路径压缩来查看UnionFind与union的实现http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests(它与CLRS中的伪代码几乎相同)并且不明白为什么路径压缩不会改变排名.如果我们find从根开始调用最长路径的端点,则等级应该下降,如果不是,则下一个union操作将选择不正确的根.

Answer 1

"等级"是理论计算机科学中那些可怕的超载术语之一.正如维基百科所指出的那样,在具有路径压缩的不相交集数据结构的上下文中,秩不是当前森林拓扑的固有属性 - 没有什么好方法可以使每个节点的高度保持最新.然而,如由联合序列所定义的,秩在证明涉及逆Ackermann函数的运行时间界限方面是有用的.

Answer 2

等级不是树的实际深度，而是上限。这样，在find操作上，允许等级与深度不同步。