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:
![](/img/30/graph05.png)
After union(0,5)
:
![](/img/30/graph06.png)
After union(1,4)
:
![](/img/30/graph07.png)
After union(2,3)
:
![](/img/30/graph08.png)
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$.
![](/img/30/graph09.png)
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$.
![](/img/30/graph10.png)
After union(0,4)
: notice as we find the root of the component containing $4$, we apply path compression.
![](/img/30/graph11.png)
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$.
![](/img/30/graph12.png)