Union-Find problem, Path Compression Recall the algorithms developed for the Uni

Question

Union-Find problem, Path Compression

Recall the algorithms developed for the Union-Find problem on disjoint sets from a set of n elements. Find uses path compression and Union uses ranking. Also, Union of two trees of the same rank chooses the root associated with 2nd argument as the new root. Start with a set S= {1,2,..., 10} and 10 disjoint subsets, each containing a single element. Draw the final set of trees after executing: Union(1,2), Union(3,4), Union{5,6), Union(1,5), Union(1,3). Show the content of the P (parent) array and Rank array at the end of (a).

Explanation / Answer

following link could be useful: http://wwwisg.cs.uni-magdeburg.de/ag/lehre/WS1112/GDS/slides/S15.pdf

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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