Question

Give the state of the disjoint-sets data structure after the following sequence of operations, starting from singleton sets $\left\{1\right\},\dots ,\left\{8\right\}$. Usepath compression. In the case of ties, always make the lower numbered root point to the higher numbered ones.

$union\left(1,2\right),union\left(3,4\right),union\left(5,6\right),union\left(7,8\right)$

$,union\left(1,4\right),union\left(6,7\right),union\left(4,5\right),find\left(1\right)$

Short answer

The state of the disjoint-sets data structure using path compression.

Step-by-step solution

Explain the data structure for disjoint sets. 

Disjoint sets can be stored as the directed tree arranged in no particular order.

Parent pointer $\pi$ and rank are the components of the disjoint set data structure. The union of the disjoint set from the singleton sets can be done by the path compression method.

Step 2:Give the state of the disjoint-sets data structure using path compression. 

Consider the properties to perform union of the sets.

Property 1: For $rank\left(x\right)<rank\left(\pi \left(x\right)\right)$, Create a root node with rank K by merging the two trees with roots of rank $k-1$ .

Property 2: Any root node of rank K has at least $2^k$nodes in its tree.

Property 3: If there are n elements overall, there can be at most $\frac{n}{2^k}$ nodes of rank .

Consider the singleton sets $\left\{1\right\},\dots ,\left\{8\right\}$. Represent the singleton sets as the nodes with the rank 0 .

Perform ,by using properties.

The node with the lowest number points to the highest number, and the number of nodes or subtrees are represented as degree.

Perform $union\left(1,4\right)$as follows,

The node 4 has two sub nodes, the degree of the node is updated as 2.

Perform $union\left(6,7\right)$

By the property 1, node 6 points to the node7 and the degree of the 7 is updated to 2 and the degree of 8 is updated to 3.

Perform $union\left(4,5\right)$

By the property 1, the node 4 points to 5 and the degrees of node 6,7, and 8 are updated accordingly. The tree has now has the root with larger degree, by applying properties 1 and 2 , merge the tree as follows.

Perform $find\left(1\right)$,

Disassociate the nodes with the highest degrees and make them pointed to the higher numbered root as follows.

Therefore, the state of disjoint set data structure is found by the path compression method