Java programming

$1.$ Implement the Node class, as follows:

$```$

class Node

int value

int size

int depth

Node parent

$```$

$2.$ Implement the tree$-$based union$-$find data structure, which should contain three basic methods:

a$.$ Implement the makeSet $()$ algorithm, which should take an int X and return an instance of the Node class, which should have X as its value, itself as a parent, a depth of $0,$ and a size of $1.$

$```$

makeSet$($int x$)$

v $=$ new Node

vvalue $=$ x

vparent $=$ v

v$.$depth $=0$

ysize $=1$

return v

$```$

b$.$ Implement the union$()$ algorithm, which should take two Nodes X and Y and join them together.

$```$

union$($node X$,$ node Y$)$

X$.$parent $=$ Y

Y$.$size $+=$ X$.$size

return Y

$```$

c$.$ Implement the find$()$ algorithm, which should take a node X and return the root of the set that it is a member of $($and will also calculate the current depth of X in doing so$).$

$```$

find$($node X$)$

node R $=$ X

while R$.$parent $!=$ R

R $=$ R$.$parent

X$.$depth $+=1$

return R

$```$

$3.$ The above pseudocode will function as a union$-$find data structure, but is lacking two key heuristics that will optimize its performance:

$-$ Union$-$by$-$size: within union$(\backslash (\backslash$mathrm$\{$x$\},\backslash$mathrm$\{$y$\})\backslash ),$ check which of the two sets is smaller, and set that one to become a subset $($child$)$ of the other.

$-$ Path compression: within find$($X$),$ before returning R$,$ iterate through each node $\backslash ($ Z $\backslash )$ on the path between $\backslash ($ X $\backslash )$ and $\backslash ($ R $\backslash ),$ and set $\backslash ($ Z $\backslash )\text{'}$s parent to equal $\backslash ($ R $\backslash )$

a$.$ Implement a new version of union$(),$ called union$2(),$ that will do the same thing as union$()$ but also satisfies the union$-$by$-$size heuristic

b$.$ Implement a new version of find$(),$ called of find$20,$ that will do the same thing as find$()$ but also satisfies the path compression heuristic.

$4.$ Test your implementation with this process:

a$.$ Create an array of $50$ singleton sets $($i$.$e$.$ instances of the Node class$),$ each with a value equal to its index in the array $($e$.$g$.$ array$[5]$ should be a Node with value$=5)$

b$.$ Create a copy of this array

c$.$ Call the operation union$($find$($array$[$i$]),$ find$($array$[$i$+5])),$ for all values of i from $0$ to $44$ within your first array

d$.$ Iterate through each node in this array and print its value, root, and depth

e$.$ Call the operation union$2($find$2($array$2[$i$]),$ find$2($array$2[$i$+5])),$ for all values of i from $0$ to $44$ within the second array

f$.$ Iterate through each node in this array and print its value, root, and depth

E$.$g$.$ for the two disjoint sets to the right, the node$($root$,$ depth$)$ format would be:

$\backslash (1(1,0)$ ; $2(2,0)$ ; $3(2,1)$ ; $4(1,1)$ ; $6(2,1)$ ; $7(1,1)$ ; $9(2,2)\backslash )$