7.5. Merging Components

In the last lecture, we saw an array based implementation of the union find data structure, in which the find operation is constant time, and we use an amortized analysis to claim that the union operation over a sequence of m unions would take m log m time. So, effectively each union was a logarithmic time operation, amortised over the entire sequence. Now, we will see a more sophisticated implementation which has even better complexity.

The union-find data structure, also known as the disjoint-set data structure, is designed to address the problem of merging sets and finding which set a particular element belongs to. In the previous implementation that was based on arrays, we had two crucial operations: 'find', which could determine the root of a set in constant time, and 'union', which was a logarithmic time operation due to the amortized analysis over multiple union operations. The update mentioned introduces a pointer-based implementation which aims to enhance the efficiency of these operations.

Imagine you have a group of friends who form separate cliques. Initially, each friend is in their own clique. Over time, some cliques merge. The 'find' operation is like asking, 'Which clique does Susan belong to?' and getting the answer instantly. The 'union' operation, however, is like deciding to merge two cliques together, which takes longer the more people are involved, but this session aims to do this more efficiently.

We will now have a different representation, we will use nodes with pointers. Each element of the set will now be represented as a node, the node will have two parts, it will have the name which is the element that you are keeping track of and a label part which keeps track of its component, so it is a pointer to the component.

In this new pointer-based approach, each element in the union-find data structure is represented by a node that contains two key attributes: 'name' and 'label'. The 'name' corresponds to the actual element, while the 'label' serves as a pointer to another node representing its component leader (or root). This allows each node to act as a reference point, connecting it to its component without needing an entire array.

Think of this implementation like a family tree. Each box (node) represents a family member (element), and instead of every family member noting their relatives (array), they simply point (pointer) to their parent (root). This structure helps keep track of the family lineage and simplifies understanding relationships.

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. Each node points to itself, indicating they are standalone components.

During the initialization of the union-find structure, each element is created as its own separate component. Essentially, each node points to itself, which means they are viewed as individual sets. For example, if we have elements labeled 1 through n, we create n nodes, each pointing to themselves to signify that they are unique and not yet merged with any other nodes.

Imagine setting up a group of people at a party where each person stands alone in their own space. Each individual has their name (node) on display. At this point, no one is mingling or mixing with others, representing how each component is initially separate.

So, when we do union, we basically do this merging of the smaller one to the larger one. Here we have two components, and we want to do the union of i and j, by merging the smaller into the larger.

The union operation aims to effectively combine two sets. When we identify two components, we compare their sizes and merge the smaller one into the larger one, ensuring the tree remains balanced. This merging is efficient and minimizes the depth of the tree, allowing faster access during the find operation afterward.

Think of two different groups of friends wanting to create a new group photo. If one group has 5 friends and the other has 3, the larger group essentially 'absorbs' the smaller group, combining them into one bigger picture. This keeps things organized and makes it easier to follow who is who.

So, we will do the usual find j, 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 this whole path and point directly to j.

Path compression is a technique used to optimize the find operation. When we locate the root of a component during a find request, we update the pointers of all traversed nodes to point directly to the root instead of their previous parent nodes. This flattening of the tree structure drastically reduces future query times, as it minimizes the number of steps needed to reach the root in subsequent finds.

Imagine a series of office workers in an organization where each employee has to check the hierarchy to reach their director (root). If we note that an employee stops needing to follow multiple managers and can now reach the director directly, the path is shortened. Thereafter, any employee will quickly find their way directly instead of traversing the full chain.

Therefore, now by moving to this pointer-based implementation, we have actually achieved considerable saving compared to the more direct array-based implementation.

By utilizing pointers and path compression, we significantly improve the performance of union-find operations. While the original array-based method required log n time complexity for union operations, the new pointer-based structure allows union in constant time and finds in nearly linear time, making it exceptionally efficient for large datasets.

This improved performance can be likened to upgrading from a physical map to a GPS navigation system. Initially, finding directions may take longer as you consult numerous landmarks (array-based). With GPS (pointers and compression), it provides the quickest routes directly to your destination, making navigation faster.

--