7.7. Union Operation Complexity

In the last lecture, we saw an array based implementation of the union find data structure, in which the find operation to 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 helps manage a partition of a set, allowing us to efficiently union components and find which partition an element belongs to. We previously examined an array-based implementation where the find operation takes constant time, making it very efficient. However, the union operation's complexity was amortized to logarithmic time due to the way we analyzed the performance over many operations. In this newer method, we will explore a more advanced setup, which promises improved performance.

Think of this array-based union-find like a library system where each book (element) is kept on its own shelf (partition), and finding a specific book is quick (constant time). However, when merging shelves to create bigger sections (union operation), it took a while as you needed to rearrange books and update the catalog based on the size of the new sections.

So, we will now have a different representation, we will use nodes with pointers. So, 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 implementation, each element in our collection becomes a node that contains two fields: its name (the actual element) and a pointer to the root of its component. This structure allows us to use pointers to represent connections between elements, enabling efficient merging and searching.

Consider each node like a person at a social gathering where each individual (element) introduces themselves (name) and points to a common leader (component root). Each person links directly to their group leader, making it clear who they belong to, and connections can be easily modified when groups merge.

So, 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 s in a partition called S each small s.

The initialization phase of the union-find structure creates separate components for every element. Each element points to itself, indicating that initially, every element is its own root. This sets up a basis for future unions.

Imagine setting up a new social network where each person (element) creates their own account (component) and is distinguished by their unique username (name). In the beginning, all users are independent, having their personal profile pointing to themselves without any connections.

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.

During the union operation, we identify two components and link the smaller one under the larger one. This merging involves finding the roots of both components and changing the pointer of the smaller root to point to the larger root. This is done so that the tree remains balanced, minimizing the height and maintaining efficiency for future operations.

Think of two teams in a company. Suppose Team A (larger component) absorbs Team B (smaller component). Instead of creating new names for each employee, Team B’s members are directly integrated into Team A, with all operations now running under Team A's leadership. This keeps the organization streamlined and efficient.

Now, the find operation requires us to start from the value that we want to check and work our way up to them. Find of u, then remember that will have this node array...

To find which component an element belongs to, we start at that element and follow its pointers up to the root node. The time for this operation depends on the length of the path we traverse. Essentially, this may take longer as the data structure evolves, with path lengths potentially increasing each time we perform a union.

If you’re searching for a person in a large organization, you might have to ask several colleagues (following pointers) to reach the department head (root). Each ask may take time, and if many people have joined the organization or changed departments (unions), it might take longer to get to the right person than it would at the start when everyone was at their desks.

So, we can 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.

In addition to the find operation, we implement path compression. As we traverse the path to the root, we make each node we visit point directly to the root. This flattening of the structure means that future find operations will be faster, as they will involve fewer steps.

Imagine that after you navigate through a big building to reach the director's office, you decide to leave a sign on every door you pass by indicating that each leads directly to the director's office. Next time you come to the building, you'll have a much clearer and faster route all laid out!

So, to summarise if we implement union find using nodes with pointers, then we can do of course, the initial set of the make union find and linear time, union now becomes a order 1 operation.

Through the use of nodes and path compression, we vastly improve our time complexity. The union operation remains efficient (constant time), and while the find operation was logarithmic, it can now be reduced to almost linear time thanks to path compression. This adaptation dramatically increases our efficiency for a series of operations.

Upon expanding the social network, not only can you quickly add new users (union operation), but now when someone searches for a friend, the search process is streamlined—people can quickly access the mutual connections thanks to the signage (path compression) set up in prior searches.

--