7.4. Make Union Find Initialization

Make union find is the initialization, so what it does is, it will set up each component as a single term containing an element of the same name. So, i belongs to the components i, so there is a node i which points to itself, then there is a node k which points to itself indicating this is a component called k containing k, this is the components called j containing j. So, we have n such components 1 to n, so we have n such nodes each of which contains the name in the first component and a pointer to itself in the second component saying itself single terms component.

The initialization of the union-find data structure involves creating individual components where each element is its own component. For example, if we have elements i, j, and k, during initialization, element i will be represented as a node pointing to itself, meaning it forms its own component: i. The same goes for elements j and k. Thus, for n elements, we create n nodes and each node (component) initially points to itself, since they contain only themselves.

Imagine a group of friends in a party where each friend initially stands alone. Each friend represents a node, and they each only know themselves (point to themselves). For example, friend i stands alone and only knows 'I am i'. As more friends (nodes) join and form groups later, they might link up, but at the start, everyone is on their own.

So, after a period of time we will see that when we merge nodes, these pointers will point instead of themselves it will point to other things. So, here for example, could be a component containing i, j, k and l and the structures says that the name of the component is actually j. So, this is the component j and it contains i, j, k, l, so you can see that the element i has a pointer not to itself, but to another node. So, if you follow this, we find that it is pointing to an element j which points to itself, so it is name of the component of i is j.

As we perform more unions in the union-find data structure, the pointers of certain nodes begin to point to other nodes rather than themselves. For example, if nodes i, j, k, and l are merged into a component J, the pointer for node i may now point to node j which points to itself (the root). Essentially, this reflects that element i is not its own component anymore but belongs to component j.

Consider the group of friends at a party again. After some time, friends i, j, k, and l decide to form a small group where they all know each other. Now, instead of i just knowing itself, it knows j (the leader of the group). This reflects the component structure where initial solo standers (nodes) combine into larger groups.

So, just to help us navigate this tree a little easier, let us assume that we have the following additional arrays of pointers and numbers. So, we will keep track first of all of where each node is. So, we have an array called node here and each element of the array is a pointer to the node containing that element.

To facilitate easier navigation through the union-find structure, a node array is introduced. Each element in this node array holds a pointer that references the corresponding node in the tree structure. For instance, if we want to find where element i is located, we can directly look up the node array to see the pointer associated with i, helping us to quickly trace back to its component.

Think of the node array like a party invitation list. Each person (element) has a name tag (pointer) that tells you exactly where they are standing in the party area (node). When you look for someone, rather than searching the entire area, you can quickly reference the list to find out where they are, saving you a lot of time.

So, when we do union we basically do this merging of the smaller one to the larger one. So, here we have two components, we have component j which is j, k and m and we have component i which is i and l. So, now we want to do the union of i and j, so now we first will somewhere we will have recorded that the size of i is 2 and the size of j is 3. So, having recorded this, we have to now therefore merge i into j.

The union operation involves merging two components, prioritizing the smaller component into the larger one based on their recorded sizes. For instance, if component j contains elements j, k, and m (size 3) and component i contains elements i and l (size 2), we merge component i into component j, effectively changing the structure of the component linked trees.

Imagine if two clubs at a school decide to merge. Club A with 20 members and Club B with only 10 members will merge, allowing Club B's members to enjoy the resources and activities of the larger Club A. This indicates how smaller groups benefit by merging into larger and more resourceful entities.

Now, find on the other hand as we saw requires us to start from the value that we want to check and work away up to them. So, supposing we say find of you, then remember that will have this node array and so node of you will say that the node containing u is here. So, we will start there and then we will follow this path, so we will say this points here and this points here and this points here and finally, when we reach a node which points to itself that is the name.

To execute the find operation, it is necessary to begin with the specific element whose component membership is being verified. We start by accessing the node array to locate the entry for that element and follow the pointers up to the root node, which gives us the component's name. Ultimately, this traversal identifies the overall component that an element belongs to.

Think of this find operation like an ancestry search. When you want to know your family tree, you start with yourself and trace back through your parents to find your great-great-grandparents. Following the pointers through each generation (nodes), you will eventually arrive at the root of your family lineage, which tells you who you are really connected to.

Now, why don’t we make use of this information and not recompute each time we come back. So, what we will do is, we will do the usual find j, so we will traverse the path and then we will go back from j to the root and say now I know this is j. So, let me bypass is whole in maybe point directly to j.

To enhance the efficiency of the find operation, a technique called path compression is utilized. After finding the root node for a given element, we update the pointers for all nodes traversed in that path to point directly to the root. This results in a more flattened tree structure, drastically reducing the time for future find operations on those elements, as they can directly access their root without traversing the full path.

Imagine if you had to keep running through a maze to reach the exit every time. If someone helps you by marking a shortcut directly from your starting point to the exit after you first figure it out, your next attempts become much quicker! This is similar to how path compression improves performance by shortening the routes in future searches.

--