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

Question

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

Answer 1

“等级”是理论计算机科学中那些严重超载的术语之一。正如 Wikipedia 所指出的，在具有路径压缩的不相交集数据结构的上下文中，排名不是当前森林拓扑的固有属性——没有好的方法可以使每个节点的高度保持最新。然而，正如联合序列所定义的，秩在证明涉及逆阿克曼函数的运行时间界限方面很有用。

Answer 2

等级不是树的实际深度，而是一个上限。因此，在find操作中，允许排名与深度不同步。