按秩合并的加权快速并查集仅对等秩子集增秩的原因求解

首先明确：此处代码中的rank数组存储的是每个根节点对应集合树的高度的上界，按秩合并的核心目标是尽可能压低合并后集合树的高度，避免树退化为链表，保障后续find查询操作的近似常数时间复杂度。

秩的更新逻辑完全是为了准确反映集合树的高度变化，分三种合并场景解释：

• 当rank[rootx] > rank[rooty]时：说明rootx对应的树更高，我们将更矮的rooty树整体挂到rootx的根节点下。此时矮树的所有节点深度最多加1，但整个合并后的新树的最大高度和原来高树的高度完全一致，没有增长，因此不需要修改rank[rootx]的取值。
• 当rank[rootx] < rank[rooty]时：逻辑和上面完全一致，将更矮的rootx树挂到更高的rooty树下，新树高度和原来rooty的树高一致，不需要修改秩。
• 当rank[rootx] == rank[rooty]时：两个待合并的树高度完全相同，不管将哪棵树挂到另一棵的根节点下，都会导致被挂的那棵树的所有节点深度+1，最终合并后的新树高度比原来的树高高出1，因此必须将新根的秩加1，才能准确反映新树的高度上界。

如果不遵守这个规则，比如任意合并都给根节点加秩，会导致秩的取值远大于实际树高，后续合并时就无法准确选择更矮的树作为挂载节点，失去按秩合并的优化效果，甚至可能出现树高度快速增长、查询性能退化的问题。

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