Stores a collection of disjoint sets. Provides operations for finding, and merging sets. These are typically implemented as a disjoint-set forest.
Finding:
- Find the representative of a set of a given element.
- The representative is the root of the tree.
Union:
- Takes two elements and finds representatives of their sets using
Find. Then puts either one of the trees under the root node of the other.
Disjoint Union Set in 5 minutes
Complexity
The height of the tree is on the order of O(logn). Which is the time complexity of both functions since they both involve traversing up the tree. The space complexity is O(n)