7. Union-Find Data Structure Using Pointers

In the last lecture, we saw an array based implementation of the union find data structure, in which the find operation takes 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, amortized over the entire sequence. Now we will see a more sophisticated implementation which has even better complexity.

So, recall that the union find data structure keeps track of a partition of a set S and supports three operations: one is make union find which creates a trivial partition, where each element belongs to its own, each element is in a single term partition named by itself. Find tells us which partition a given element belongs to and union combines two components or two partitions into a single one.

The Union-Find data structure is used to manage a partition of a set into distinct subsets. This structure enables two main operations:

1. Find: Determines which subset a particular element is in.
2. Union: Merges two subsets into a single subset. Earlier, we discussed an array-based implementation where the Find operation takes constant time, while the Union operation's average time complexity can be logarithmic when analyzed over multiple operations. We are now transitioning to a more efficient representation using pointers to improve these operations further.

Imagine organizing a group of friends at a party where each friend represents an element. Initially, friends are in separate groups (their own partitions). When two friends decide to hang out together, we need to merge their separate groups into one larger group, just like the Union operation does. The Find operation is like asking a friend which group they belong to at the party.

The array based implementation uses an array called component to tell us which component each element belongs to. It keeps an array of lists to tell us which elements belong to each component. So, it is a kind of reverse mapping, for each component k it tells us which members of the set belong to that. Finally, it tracks the size of each component, because we merged components by taking smaller ones and relabeling them with the name of the bigger ones. So, make union find was an order n operation, find was an order one operation and the amortized complexity of the union operation was log m for a sequence of m operations.

In the array-based structure, we utilize three main components:

• Component Array: This array indicates which component each element is part of.
• List Array: Keeps track of which elements belong to each component, creating a reverse mapping.
• Size Array: Tracks the sizes of each component for efficient merging. Merging operations are done by relabeling smaller components with the label of larger components, ensuring efficient union processes. The time complexity for the Union operation was amortized to log m when considering multiple operations, while Find could be performed in constant time.

Consider a filing cabinet where each drawer represents a component and the files inside represent elements. The component array tells us which drawer a particular file is in, the list array shows the contents of each drawer, and the size array indicates how many files are in each drawer. When we combine two drawers (unions), we move files around and relabel as necessary (tracking size for efficiency).

Now, we will 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. Now, remember that the names of the components are the names of the elements. So, if we have a name here for example, we have name j it says that this node represents the element j and its label points back to itself, so it says this is j belongs to the component j.

In the pointer-based implementation, each element is represented by a node consisting of two fields:

1. Name Field: Represents the actual element (e.g., element 'j').
2. Label Field: Acts as a pointer that indicates to which component the element belongs. Initially, the label points back to itself, indicating that the node is its own root. This structure allows a more dynamic representation of components as nodes can point to other nodes as they are merged.

Think of a family tree where each person is a node (with their name) and the pointer indicates who their parent is. Initially, each person points to themselves (they are their own root), but as families merge (like unions), some people will end up pointing to others, similar to how nodes will point to their new components.

When we do union, we basically do this merging of the smaller one to the larger one. 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 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 based on their sizes. For instance, if we have component j (size 3) and component i (size 2), we will attach the smaller component (i) to the larger one (j). This involves making the root of i point to the root of j, effectively merging them into a single component and updating the size of j to reflect the new total size.

Imagine two companies merging. If Company A has 3 employees and Company B has 2 employees, when they merge, we take the smaller company (B) and make its employees part of the larger company's (A's) staff list. A's staff list then reflects the new total (5 employees) after the merger.

Find on the other hand requires us to start from the value that we want to check and work our way up to them. Supposing we say find of u, then remember that we will start there and 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. This takes time proportional to the path that we traverse from the node to the root.

The Find operation starts from a specific element and traces up the pointers to reach the root of its component. The time it takes depends on how many nodes are in the path, termed as the tree's height. If the path is long, the operation can be slow. With path compression, we can optimize this process by making nodes point directly to the root as we traverse, flattening the tree structure to make future Find operations faster.

Returning to our family tree analogy, imagine you are tracing your lineage. Each time you find out who your parent is, you could save this info for future references by noting the direct link to your ancestor instead of going through all the parents again. This makes it quicker next time!

So, by moving to this pointer based structure, we have actually achieved a considerable saving compared to the more direct array based implementation. Although in principle it is n log n for n operations, it is n alpha n for n operations if we use path compression.

Using path compression drastically improves the efficiency of the Find operation. While a naïve implementation could take up to n log n for n operations, utilizing the path compression technique reduces it to near linear time, expressed as n times a slow-growing function called alpha(n). This function grows extremely slowly, which practically means operations remain efficient even for large sets.

Think of a town with a network of roads. Initially, it might take a long time to drive from one side to another because you have to navigate all the streets (n log n). However, if road signs were placed to guide you directly to the destination through shortcuts, you would travel much faster every time you drive (n alpha n).

--