Data structure experiment – merge and find the root of the tree with a high height as the new root + find uses folding rules to implement the union and set experiment

Merge and find the root of the tree with the highest height when merging as the new root Experiment

1.1 Experimental content

When the union search is merged, the root node of the tree with a higher height is used as the root node of the new tree to generate a new tree. After merging, the height of the new tree can be reduced and the efficiency of find can be improved.

1.2 File structure description

Development environment version

Visual Studio 2022

Project file name

c6-ufsets.sln

Number of header files

Number of source program files

file name	file type	Function introduction	Remark
UFSets.h	head File	And search the class template header file, including the declaration and definition of data members and member functions
elemnode.h	head File	And search the element node class template header file, including the declaration and definition of data members and member functions	data field + parent field
Assistance.h	head File	Auxiliary packages
text.cpp	Source File	test file

1.3 Implementation Technology

1. Declare the function HeightUnion(ElemType a, ElemType b) in the union-find set UFSets, and use the root of the tree with a high height as the new root.

//Union search
template <class ElemType>
class UFSets
{
protected:
//And check the data members of the set:
ElemNode <ElemType> *sets; // Store the parents of the node
int size; //Number of nodes
int *rank; //Storage the number of levels of the tree

// helper function
    //int Find(ElemType e) const; //Find the root of the equivalence class where element e is located
    int CollapsingFind(ElemType e) const; // Find the root of the equivalence class where element e is located

public:
//Union and find the function members of the set:
UFSets(ElemType es[], int n); //Construct sz single-node trees (equivalence classes)
virtual ~UFSets(); // destructor
ElemType GetElem(int p)const; // Get the subscript of the specified element in the array
int GetOrder(ElemType e)const; // Get the element value according to the specified subscript
void Union(ElemType a, ElemType b); // Merge the equivalence classes of a and b
void HeightUnion(ElemType a, ElemType b);//The root of the tree with high height is used as the new root
    bool Differ(ElemType a, ElemType b); // Determine whether elements a and b are in the same equivalence class
UFSets(const UFSets & amp;copy); // copy constructor
UFSets & amp;operator =(const UFSets & amp;copy); // assignment operator
};

2. The function HeightUnion is defined outside the template to use the tree with a high height as the new root.

Call the CollapsingFind() function to find the root of the equivalence class where a and b are located. If the serial numbers of the nodes where the roots are located are not equal, if rank[r2] is greater than rank[r1], set r2 as the parent domain of r1, otherwise r1 is set as the parent domain of r2.

template <class ElemType>
void UFSets<ElemType>::HeightUnion(ElemType a, ElemType b)
//Operation result: According to the height, the root of the tree with the highest height is used as the new root.
{
int r1 = CollapsingFind(a); // Find the root of the equivalence class where a is located
int r2 = CollapsingFind(b); // Find the root of the equivalence class where b is located
if (r1 != r2 & amp; & amp; r1 != -1) {
int temp = sets[r1].parent + sets[r2].parent;
if (rank[r1] <= rank[r2])
{
sets[r1].parent = r2;
sets[r2].parent = temp;
}
else
{
sets[r2].parent = r1;
sets[r1].parent = temp;
}
}
}

3. Test code

int main(void)
{
try // Use try to encapsulate code that may cause exceptions
{
const int n = 10;
char c[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
int a[] = { 'a', 'g', 'i', 'c', 'a', 'h', 'f', 'f' };
int b[] = { 'b', 'd', 'j', 'b', 'c', 'i', 'e', 'd' };
UFSets<char> e(c, n);
int i;
for (i = 0; i < 8; i + + )
e.Union(a[i], b[i]); // Merge equivalence classes

bool out[n]; // The output node value is true, otherwise the value is false

for (i = 0; i < n; i + + )
out[i] = false;
int p = 0; // current node
while (p < n) { // For the current node that has no output, output its equivalence class
cout << "{" << e.GetElem(p);
out[p] = true;
for (i = p + 1; i < n; i + + ) { // Output equivalence class
if (!e.Differ(e.GetElem(p), e.GetElem(i))) { // p and i are in the same equivalence class
cout << "," << e.GetElem(i);
out[i] = true;
}
}
cout << "}" << endl;
while (p < n & amp; & amp; out[p]) p + + ;
}

}
catch (Error err) // Catch and handle exceptions
{
err.Show(); // Display exception information
}

system("PAUSE"); // Call library function system()
return 0; // Return value 0, return to the operating system
}

1.4 Test situation

Test Data:

char c[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
int a[] = { 'a', 'g', 'i', 'c', 'a', 'h', 'f', 'f' };
int b[] = { 'b', 'd', 'j', 'b', 'c', 'i', 'e', 'd' };

Test Results:

findUse folding rules to implement union search Experiment

1.1 Experimental content

Using folding rules to complete a search requires more time than the Find() function, but it can improve the performance of the tree and reduce the time required for subsequent search operations.

1.2 File structure description

Development environment version	Visual Studio 2022	Project file name	c6-ufsets.sln
Number of header files	3	Number of source program files	1

file name	file type	Function introduction	Remark
UFSets.h	head File	And search the class template header file, including the declaration and definition of data members and member functions
elemnode.h	head File	And search the element node class template header file, including the declaration and definition of data members and member functions	data field + parent field
Assistance.h	head File	Auxiliary packages
text.cpp	Source File	test file

1.3 Implementation Technology

1. Declare the function CollapsingFind(ElemType e) const in the union-find set UFSets and define the function outside the class:

Suppose j is a node in the tree with i as the root, then for each node p on the path from j to root i, if p’s parents (sets[p].parent) are not equal to i, then i is set to the parent of p (sets[p].parent = i).

template <class ElemType>
int UFSets<ElemType>::CollapsingFind(ElemType e) const
// Operation result: With compression path function, find the root of the tree where element e is located
{
    int i, k, p = 0;
    while (p < size & amp; & amp; sets[p].data != e)
        p + + ;
if (p == size)
return -1; // element e does not exist in the collection
    for(i = p; sets[i].parent >= 0; i= sets[i].parent); //Find the serial number i of the root node of p
    while (sets[p].parent!=i & amp; & amp; i!= p ) {//Start from p and compress layer by layer upwards
        k = sets[p].parent;
        sets[p].parent = i;
        p = k;
    }
    return i;
}

The complete code can be found in the resource area, in the c6-ufsets folder of Experiment 1

It’s not easy to create~Please give me a like~~Thank you everyone~~~