Path Compression

Path compression makes every node on the find path point directly to the root:

function find(x):
    if this.parent[x] != x:
        this.parent[x] = this.find(this.parent[x])
    return this.parent[x]

After calling find(x), every node from $x$ to the root now points directly to the root. Future finds on these nodes are $O(1)$.

Example: chain $1 \to 2 \to 3 \to 4$ (4 is root). After find(1):

• $1 \to 4$
• $2 \to 4$
• $3 \to 4$
• $4 \to 4$ (root)

The tree flattens completely. You see the power of path compression. Even if trees get tall temporarily, find operations flatten them.