路徑壓縮（path compression）

並查集（互斥集）結構把一群項目分割成數個群組，並透過沿父指標的樹往上走到群組的根來回答「x 在哪一群？」。若這些樹長得高，每次查詢就慢，因為上行很長。路徑壓縮是在一次 find 期間施用的微小、幾乎免費的技巧：當你從 x 走到它的根 r 之後，你回頭把那條路徑上的每個節點直接改指向 r，使日後對它們任何一個的 find 都只要一跳。

具體地，Find(x) 沿父指標 x -> p -> q -> ... -> r 走到根 r（以自己為父的節點），然後第二趟把 x 以及途中每個節點的父都設為 r。剛才花力氣走過的路徑被壓平，於是結構會自我改善：現在花的工絕不浪費，因為它永久縮短了未來的路徑。這是攤還分析的完美場景——單一次 Find 若爬一條高路徑仍可能慢，但它替之後所有人留下更矮的樹。單獨的路徑壓縮（不配合按秩合併）已能把一次 Find 的攤還成本降到約 O(log n)，而這份改善正是它壓平的未來路徑在回報。

路徑壓縮是著名的近乎常數並查集的一半。與按秩合併（總把較矮的樹掛在較高的樹下）結合，每個操作的攤還成本降到 O(alpha(n))，其中 alpha 是反阿克曼函數——對任何可想像的輸入實質上是個小常數。兩個誠實的重點：第一，分析之所以微妙正因為結構不斷自我改變，這也是為何它需要位勢法而非簡單求和；第二，單靠路徑壓縮而不配合按秩，給出的是 O(log n) 攤還，不是 O(alpha(n))——要得到反阿克曼界，你需要兩個啟發法一起用。