Part 5: Coding and the PAs (8 points) use to implement the disioint set A Consid
ID: 3571638 • Letter: P
Question
Part 5: Coding and the PAs (8 points) use to implement the disioint set A Consider the following tree linked data structure that you will up tree up- struct DSNode the parent in the DSNode parenti pointer to subtree int size size of this on your answer sheet, write union and find by ordering the statements below by their letters so that employs the weighted union dy tree size) and find employs path and a You should use the linked compression. (SEE NEXT PAGE FOR CoDE the caller of union ven above without modification in your implementation. the eners thar produce find somehow to the relevant DSNodes, ordering of use letters Yow miehr warmed ase all the enters to wrine the cade you might "alid more than onceExplanation / Answer
DSNode* union(DSNode* X, DSNode* Y){
if(X->parent != nullptr || Y->parent != nullptr){
cerr << "Nodes to the union must be root nodes";
return nullptr;
}
// Check the size of the trees and change the parent pointer and return.
if (Y->size > X->size){
X->parent = Y;
return X;
}
else{
Y->parent = X;
return Y;
}
// The below code is required to complete the code for union.
// However it was not in the list of options, so I have commented it below.
// if the size of X and Y are same then make either X or Y as child of another
// and increase the size of the parent by 1.
/*if(Y->size <= X->size && X->size <= Y->size){
X->parent = Y;
Y->size += 1;
return Y;
}*/
}
DSNode* find(DSNode* x){
if(!x) return nullptr;
// Check if the parent of the current node is NULL.
// If not then recursively repeat with the parent pointer until the
// parent pointer is NULL.
if(x->parent != nullptr){
x = find(x->parent)
}
return x;
}