This question is related to disjoint set operations. Assume that we are using union by rank and find$-$set with path compression. The state of a disjoint set data structure is given as follow.

A$[1]=-3,$

A$[2]=1,$

A$[3]=1,$

A$[4]=3,$

A$[5]=1,$

A$[6]=5,$

A$[7]=5,$

A$[8]=7,$

A$[9]=-3,$

A$[10]=9,$

A$[11]=9,$

A$[12]=11,$

A$[13]=9,$

A$[14]=13,$

A$[15]=13,$

A$[16]=15.$

After union$(4,16),$ what is the value of A$[1],$ A$[9],$ A$[14],$ A$[15],$ A$[16]?$ Union by rank

Union$($x$,$ y$)$ is accomplished by Link$($Find$-$Set $($x$),$ Find$-$Set $($y$))$;

Find$-$Set with path compression

Find$-$Set$($x$)$ is accomplished by

Find$-$Set$($x$)\{$

$1$: if A$[$x$]<=0$ then$\{$

$2$: return x;

$3$: $\}$else$\{$

$4$: A$[$x$]=$Find$-$Set$($A$[$x$])$;

$5$: return A$[$x$]$;

$\}$

$\}$

Link$($x$,$ y$)\{$

if $(-$A$[$x$]>-$A$[$y$])\{$

A$[$y$]=$x;

$\}$ else if $(-$A$[$x$]=-$A$[$y$])\{$

A$[$x$]=$y;

A$[$y$]=$A$[$y$]-1$;

$\}$ else $\{$

A$[$x$]=$y;

$\}$

$\}$