Disjoint Set

Question 1

Disjoint set purpose

Answer 1

To identify mutually exclusive groups. Each member is identified by the group “leader”.

Question 2

Disjoint set methods

Answer 2

1. Make-Set(x): crate a new set that has only x.
2. Union(x,y): joint all of the members of x and y groups.
3. Find-Set(x): return the leader of x’s group.

Question 3

Disjoint set using an array (idea and cost)

Answer 3

Idea: use an array to save the team leader of each element. When doing union, change the leader for elements in one of the sets.
Runtime: Make-Set O(1), Find-Set O(1), Union O(n)

Question 4

Disjoint set using a linked list (idea and run time)

Answer 4

Idea: use an array to save the set members like before. Utilize a circle linked list for each set. Save a set size field. For union, change the smaller group’s leader.
Runtime: Make-Set O(1), Find-Set O(1), Union O(logn)

Question 5

Disjoint set using a tree

Answer 5

Idea: Each node points to its team leader. When doing union, just make the team leader point to the other team leader. Optional: every find-set, make the entire path point directly to the leader.
Cost: Make-Set O(1), Find-Set O(1), Union O(logn) (using optional: O(Ackerman(n) <= 4)