路径压缩对不相交集合森林已足够，为何仍需采用按秩合并？

Great question! Let's unpack this by looking at how path compression works on its own, where it falls short, and how union by rank fills that gap—using the pseudocode you shared as our guide.

First: What Path Compression Does (and Doesn't Do) #

Path compression is brilliant for speeding up FIND-SET operations. As you can see from the pseudocode:

FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

It flattens the tree structure on-the-fly during a find, making all nodes along the path point directly to the root. This means subsequent FIND-SET calls on those nodes are almost instantaneous.

But here's the catch: path compression only fixes the tree after you perform a find. It doesn't prevent the tree from becoming tall and unwieldy in the first place, during UNION operations.

The Problem with Path Compression Alone #

Imagine we skip union by rank and just naively attach one tree's root to another during UNION. If we consistently attach larger, taller trees to smaller, shorter ones, the tree's height can grow linearly with the number of elements. For example:

• Start with MAKE-SET(1), MAKE-SET(2), ..., MAKE-SET(n)
• Perform UNION(1,2): attach 2's root to 1 (tree height 1)
• Perform UNION(1,3): attach 1's root to 3 (tree height 2)
• Perform UNION(3,4): attach 3's root to 4 (tree height 3)
• ... and so on until UNION(n-1, n)

By the end, the tree has a height of n-1. The first time you call FIND-SET(1), you'll have to traverse every single node from 1 up to n—an O(n) operation. Path compression will fix this for future calls, but if you have multiple such tall trees being created, the initial cost of those first FIND-SET operations adds up quickly.

How Union by Rank Fixes This #

Union by rank is a preventive measure that controls the tree's height during merging, so it never gets that tall in the first place. Looking at the LINK pseudocode:

LINK(x, y)
    if x.rank > y.rank
        y.p = x
    else
        x.p = y
        if x.rank == y.rank
            y.rank = y.rank +1

It always attaches the shorter tree (lower rank) to the root of the taller tree (higher rank). If the trees are the same height, it attaches one to the other and increments the rank of the new root.

This simple rule guarantees that the height of any tree in the forest is at most O(log n). Why? Because a tree with rank k must contain at least 2^k nodes. So for n total nodes, the maximum rank (and thus maximum tree height) is log2(n).

The Synergy of Both Techniques #

When you combine path compression with union by rank, you get the best of both worlds:

• Union by rank keeps trees short from the start, so even the first FIND-SET operation is fast (O(log n) at worst)
• Path compression flattens trees further during finds, making subsequent operations nearly constant time

Together, they give us the almost-linear time complexity bounded by the inverse Ackermann function—this is as close to constant time as you can get for this type of data structure, and it's far better than what you'd get with path compression alone.

In Short #

Path compression fixes the symptoms of tall trees, but union by rank prevents those tall trees from growing in the first place. Using both ensures that every operation (find and union) is as efficient as possible, even in worst-case scenarios.

内容的提问来源于stack exchange，提问作者Damon Hu