Union by rank attaches the shorter tree under the taller tree:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def union(self, x, y):
rootX, rootY = self.find(x), self.find(y)
if rootX == rootY:
return
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.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 .