Assume a Disjoint Set data structure has initially 20 data 6. (20 points) Disjoi

Question

Assume a Disjoint Set data structure has initially 20 data

6. (20 points) Disjoint Set Assume a Disjoint Set data structure has initially 20 data items with each in its own disjoint set (one node tree). Show the final result (only show the array P for parts a, b & c below; no need to draw the trees) of the following sequence of unions (the parameters of the unions specified in this question are data elements; so assume that the find operation without path compression is applied to the parameters to determine the sets to be merged): union (16,17), union(18,16), union (19,18), union (20,19), union (3,4), union (3,5), union (3,6), union(3,10), union(3,11), union (3,12), union(3,13), union (14,15), union (14,3), union (1,2), union (1,7), union (8,9), union(1,8), union (1,3), union (1,20) when the unions are: a. Performed arbitrarily. Make the second tree the child of the root of the first tree. 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Explanation / Answer

a.Performed arbitarily. Make the second tree, child of first tree

1

b. Performed By Height

1

c. Performed by size

1

d. Performing path compression on deepest node for the solution in part(a)

1

1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 14 3 3 3 1 1 8 3 3 3 3 1 14 18 16 19 20 1

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.