Quick Union: Exercise

Suppose you have singleton sets with the values $0$ through $6$. Then, 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$.