Quick Union: Exercise
Suppose you have singleton sets with the values $0$ through $6$. We apply the following operations.
union(0,5)
union(1,4)
union(2,3)
union(3,6)
union(4,6)
union(0,4)
Exercise Using both tree and array forms, show the result of each of the operations listed above, applying union-by-size and path compression heuristics.
Solution
Here is the start:
After union(0,5):
After union(1,4):
After union(2,3):
After union(3,6): notice the size of the component containing $6$ is smaller than the size of the component containing $3$. Therefore, the component containing $6$ is added to the root of the component containing $3$.
After union(4,6): notice the size of the component containing $4$ is smaller than the size of the component containing $6$. Therefore, the component containing $4$ is added to the root of the component containing $6$.
After union(0,4): notice as we find the root of the component containing $4$, we apply path compression.
Then, as the size of the component containing $0$ is smaller than the size of the component containing $4$, the component containing $0$ is added to the root of the component containing $4$.
