Union by Size

定义 Definition

“union by size”指并查集（Union-Find/DSU）中的一种合并策略：在合并两个集合时，把元素数量较少（size较小）的集合挂到元素数量较多的集合下面，以尽量保持树的高度更低，从而加快后续查找（find）操作。常与路径压缩（path compression）一起使用。

发音 Pronunciation (IPA)

/ˈjuːnjən baɪ saɪz/

例句 Examples

We use union by size to keep the DSU trees shallow.
我们使用按大小合并来保持并查集的树尽量“矮”。

With path compression and union by size, most operations run in almost constant time.
配合路径压缩和按大小合并，大多数操作的时间复杂度几乎接近常数。

词源 Etymology

“union”原意是“联合、合并”，“by”表示“按照/依据”， “size”是“大小、规模”。在算法语境里，这个短语专门用来描述并查集的启发式（heuristic）合并方法：按集合规模决定父子关系。该策略与“union by rank（按秩合并）”属于同一类思想，目标都是降低树高、提升效率。

相关词 Related Words

• Disjoint Set Union
• Union-Find
• Path Compression
• Union by Rank
• Heuristic
• Amortized
• Tree Height

文学与著作中的用例 Literary & Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称CLRS）中讲解不相交集合数据结构与按秩合并/路径压缩时，相关思想与“按大小合并”密切对应。
• Algorithms（Robert Sedgewick & Kevin Wayne）在并查集与动态连通性（dynamic connectivity）章节中讨论加权合并（weighted union），常见实现即按大小合并。
• Competitive Programming（Steven & Felix Halim）等竞赛算法教材在DSU优化部分常直接使用或提及“union by size”这一术语。