When elements are repeatedly joined into groups, a disjoint set needs a reliable way to identify an element’s current group. `findPartition(x)` does that lookup. `areDisjoint(x, y)` compares two results; `merge(x, y)` uses them to identify the groups to join. The returned identifier is mainly useful inside the data structure and need not mean anything to its caller. section 5.3 section 5.4.1
The lookup changes with the representation:
- With a hash map from each element to its partition, validate the element and return its mapped partition. Assuming constant-time hashing, lookup takes constant time, but merging can take linear time because mappings must be updated. section 5.4.1 section 5.5
- With parent links, each partition is a tree. Follow an element’s parents until reaching a root, identified by being its own parent; return that root as the partition identifier. Lookup depends on tree height: it is logarithmic on average in the unbalanced version, but can be linear in the worst case. section 5.5.1 section 5.5.2
- With path compression, save the root found by the recursive lookup directly in each visited element’s record. Subsequent lookups can then follow shorter paths; merging by tree size helps prevent tall trees. section 5.6.2
Listing 5.9 Tree-with-heuristics solution, findPartition
function findPartition(elem) #1
throw-if (elem == null or not parentsMap.has(elem))) #2
info ← this.parentsMap[elem] #3
if (info.root == elem) then #4
return elem
info.root ← this.findPartition(info.root) #5
return info.root
The path-compressing implementation shows both the stopping condition—an element is its own root—and the parent update made while recursion returns. section 5.6.2
Keep callers dependent on the operation, not its representation: `areDisjoint` can compare two `findPartition` results whether those results are partition objects or tree roots. Tree links make merging simpler than updating every element’s partition mapping, but without balancing they move the cost into lookup. Balancing and path compression address that trade-off. section 5.4.1 section 5.5.1 section 5.6.2
