Union by Rank

Union by rank attaches the shorter tree under the taller tree:

class UnionFind:
    function init(n):
        this.parent = array of [0, 1, ..., n-1]
        this.rank = array of n zeros

    function union(x, y):
        rootX = this.find(x)
        rootY = this.find(y)
        if rootX == rootY:
            return
        if this.rank[rootX] < this.rank[rootY]:
            this.parent[rootX] = rootY
        else if this.rank[rootX] > this.rank[rootY]:
            this.parent[rootY] = rootX
        else:
            this.parent[rootY] = rootX
            this.rank[rootX] += 1

Rank is an upper bound on tree height. When two trees have equal rank, the resulting tree's rank increases by 1.

This guarantees trees stay balanced: a tree with rank $r$ has at least $2^r$ nodes. Maximum rank is $O(\log n)$.