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 has at least nodes. Maximum rank is .