Question1: Perform the following sequence of Union operations on the set ofeleme

Question

Question1:                                        

Perform the following sequence of Union operations on the set ofelements {1,2,3,……….,17}

Union(1,2)

Union(3,4)

Union(3,5)

Union(1,7)

Union(3,6)

Union(8,9)

Union(1,8)

Union(3,10)

Union(3,11)

Union(3,12)

Union(3,13)

Union(14,15)

Union(16,17)

Union(14,16)

Union(1,3)

Union(1,14)

When the unions are performed

a)      by height

b)      by size

Question2:                                                

For both trees in the Question 1, perform a Findoperation with path compression on the deepest node.

Explanation / Answer

Hi there, I think the trees could look somwhere along thees lines. I don'tknow how Deitel describes path compression - the way I know it itwas to point every node along the ?nd path to root, but it could bejust the deepest node. Here is an example, union by size, height andfindWithPathCompression tries to find the id 10 in the twotrees. Let me know if I am off track - send me a PM. By height0 1 2 7 8 9 3 4 5 6 10 11 12 13 14 15 16 17Find id 10 with path compresion0 1 14 15 16 17 2 7 9 8 4 5 6 10 3 11 12 13By size0 3 4 5 6 10 11 12 13 1 2 7 8 9 14 15 16 17Find id 10 with path compresion0 3 11 12 13 1 2 7 8 9 14 15 16 17 4 5 6 10 Her is the program used to output the trees: #include #include #include using namespace std;class Node {protected: int id; list children;public: Node() { // Noop }; Node(int id) { this->id = id; } // Return the height of the tree int height(){ int maxHeight = 0; for(list::iterator i = children.begin(); i != children.end(); i++) { int childHeight = (*i).height(); if(childHeight>maxHeight) maxHeight = childHeight; } return ++maxHeight; }; // Return the number of elements in this tree int size() { int size = 0; for(list::iterator i = children.begin(); i != children.end(); i++) size += (*i).size(); return ++size; }; // Display the datastructure void display(int depth) { for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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