In this project, you will run some empirical tests to determine if some variations on path compression in the UNION/FIND algorithm will lead to improved performance. You should compare the following four implementations:

(a) Standard UNION/FIND with path compression and weighted union.

(b) Path compression and weighted union, except that path compression is done after the UNION, instead of during the FIND operation. That is,

make all nodes along the paths traversed in both trees point directly to the root of the larger tree.

(c) Weighted union and a simplified form of path compression. At the end of every FIND operation, make the node point to its tree’s root (but don’t change the pointers for other nodes along the path).

(d) Weighted union and a simplified form of path compression. Both nodes in the equivalence will be set to point directly to the root of the larger tree after the UNION operation. For example, consider processing the equivalence (A, B) where A0 is the root of A and B' is the root of B.

Assume the tree with root A0 is bigger than the tree with root B0. At the end of the UNION/FIND operation, nodes A, B, and B' will all point directly to A'.