Path Compression

定义 Definition

路径压缩：一种用于并查集（Disjoint Set Union / Union-Find）的优化技巧。在执行 find（查找代表元）操作时，把访问路径上的节点直接连接到根节点，从而显著降低后续查找的时间开销（常与按秩合并/按大小合并一起使用）。

发音 Pronunciation (IPA)

/pæθ kəmˈprɛʃən/

例句 Examples

Path compression makes repeated find operations much faster.
路径压缩会让重复的查找操作快得多。

With union by rank and path compression, the disjoint-set structure runs in nearly constant time per operation in practice.
结合按秩合并与路径压缩，并查集在实际中几乎可以做到每次操作接近常数时间。

词源 Etymology

这是计算机科学领域的术语组合：path（路径）指在并查集中从某个节点到根节点的父指针链；compression（压缩）指把这条“长路径”在一次查找后“压短”，让节点更直接地指向根，从而减少后续访问的层级。该方法因其直观效果被称为“路径压缩”。

相关词 Related Words

• Disjoint-set
• Union-find
• Find
• Union
• Root
• Rank
• Heuristic
• Amortized

文学作品与名著用例 Literary Works

• Robert E. Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm（1975）：经典论文之一，系统分析了路径压缩等策略的效率。
• Thomas H. Cormen et al., Introduction to Algorithms（常称 CLRS，《算法导论》）：在并查集章节讲解路径压缩与按秩合并，并给出近似常数时间的摊还分析结论。
• Robert Sedgewick & Kevin Wayne, Algorithms：在动态连通性/并查集内容中介绍路径压缩作为关键优化手段。