Union-Find执行Union时是否需先做Find？路径压缩后秩是否一致？

• 首先要明确：路径压缩不会修改集合根节点的rank值。rank的定义是记录树的历史高度（或近似高度），它是用来指导合并操作的标记，而非实时的当前树高。
• 举个实际场景：
  假设集合A的根节点rank为2（原始树高度是2），集合B的根节点rank为3（原始树高度是3）。当对集合A中的某个节点执行Find操作时，路径压缩会把该节点到根的路径扁平化，所有路径上的节点直接指向根，但根节点的rank依然保持为2，不会被更新。
• 这时候执行Union操作，两个集合根节点的rank仍然是2和3，并不相同，所以依然需要按秩合并的逻辑——把rank小的树挂到rank大的树的根节点下，以此保证整个森林的树高度增长最慢，维持并查集的高效性能。
• 为什么路径压缩不更新rank？因为路径压缩的核心目标是加速后续的Find操作，如果每次压缩都去更新rank，会额外增加操作开销，而保留原始rank已经足够满足合并时的决策需求，不会影响整体近似O(α(n))的时间复杂度（α是阿克曼函数的反函数，增长极慢）。

内容的提问来源于stack exchange，提问作者PKuhn