Quick Union: Exercise

Suppose you have singleton sets with the values 00 through 66. 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 66 is smaller than the size of the component containing 33. Therefore, the component containing 66 is added to the root of the component containing 33.

After union(4,6): notice the size of the component containing 44 is smaller than the size of the component containing 66. Therefore, the component containing 44 is added to the root of the component containing 66.

After union(0,4): notice as we find the root of the component containing 44, we apply path compression.

Then, as the size of the component containing 00 is smaller than the size of the component containing 44, the component containing 00 is added to the root of the component containing 44.