Union by Rank

释义 Definition

按秩合并：一种用于并查集（Disjoint Set Union / Union-Find）的合并策略。合并两个集合时，比较两棵树的“秩”（rank，常近似表示树的高度或深度），把秩较小的根节点挂到秩较大的根节点下面，以减少树变高，从而加快后续查找（find）操作。该术语也常与 path compression（路径压缩）一起出现。

发音 Pronunciation (IPA)

/ˈjuːnjən baɪ ræŋk/

例句 Examples

We use union by rank to keep the union-find structure fast.
我们使用按秩合并来保持并查集结构的高效。

In Kruskal’s algorithm, union by rank (often combined with path compression) helps maintain near-constant amortized time for connectivity checks.
在 Kruskal 算法中，按秩合并（常与路径压缩结合）有助于让连通性检查保持接近常数的均摊时间。

词源 Etymology

“union”在算法语境中指“合并（集合）”，“rank”原义为“等级、秩”。在并查集里，“rank”通常是一个用于估计树高度的辅助指标。union by rank作为一种经典启发式（heuristic）策略，常与路径压缩一起用于提升并查集的效率；相关分析在 20 世纪后期的算法研究与教材中被系统化传播。

相关词 Related Words

• Disjoint Set
• Union-Find
• Path Compression
• Union by Size
• Rank
• Heuristic
• Amortized
• Kruskal’s Algorithm

文学与著名作品 Literary & Notable Works

• Robert Sedgewick & Kevin Wayne，《Algorithms》（算法教材中常在 Union-Find/DSU 章节讲解按秩合并与路径压缩）
• Thomas H. Cormen et al.，《Introduction to Algorithms》（“CLRS”，在并查集/不相交集合森林的讨论中涉及按秩合并思想与复杂度分析）
• Robert E. Tarjan 的相关论文与著作（关于并查集启发式与复杂度分析的经典研究中系统讨论了按秩合并/按秩链接等思想）