Union by Rank and Path Compression: Mastering Efficient Data Structures 🎯

Welcome to our comprehensive guide on Union by Rank and Path Compression, two essential techniques for optimizing data structures! In this lesson, we'll learn how to handle a collection of objects (also known as sets) efficiently, providing practical examples to help you understand the concepts effectively.

What are Data Structures and Algorithms? 📝

Data structures are organizational schemes that define how data is stored and manipulated in a computer program. Algorithms, on the other hand, are step-by-step procedures to solve a problem. Data structures and algorithms work hand in hand to ensure efficient program performance.

Introduction to Union by Rank 💡

Union by Rank is a technique used in Disjoint Set Data Structures to combine multiple sets (or groups) into a single one. This technique helps in reducing the overall time complexity by minimizing the number of times we need to perform operations like union and find.

Union-by-Rank Algorithm Steps 📝

Initialize each element as its own set with a rank of 0.
When merging two sets, make the root of the set with the higher rank the parent of the other set's root.
If the ranks of the merged sets are equal, increment the rank of one of them.

Introduction to Path Compression 💡

Path Compression is another technique used in Disjoint Set Data Structures to further optimize the Union by Rank algorithm. It reduces the height of the tree representing the disjoint sets, improving the time complexity for find operations.

Path Compression Algorithm Steps 📝

During the find operation, move up the tree until reaching the root, and make each node on the path point to its parent directly.

Union by Rank and Path Compression Example 💡

Let's consider an example where we have the following sets:

Set A: {1, 2, 3}
Set B: {4, 5, 6}
Set C: {7, 8, 9}

We'll perform the following union operations:

union(1, 4)  // Merge Set A and Set B, making Set A the parent of Set B
union(2, 5)  // Merge Set A (now containing {1, 4, 2, 5}) and Set B again, making Set A the parent of the combined Set A and Set B
union(3, 6)  // Merge Set A (now containing {1, 4, 2, 5, 3, 6}) and Set C

After the union operations, we have a single set containing all elements:

Set D: {1, 2, 3, 4, 5, 6, 7, 8, 9}

Union by Rank and Path Compression Implementation in Python ✅

python

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.rank[root_y] += self.rank[root_x]
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += self.rank[root_y]

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

# Creating the disjoint set object with 9 elements
ds = DisjointSet(9)

# Performing union operations
ds.union(1, 4)
ds.union(2, 5)
ds.union(3, 6)

# Checking if all elements are in the same set
print(ds.is_connected(1, 9))  # Output: True

Quiz Time 🎯

By learning Union by Rank and Path Compression, you'll be well-equipped to handle complex data structures efficiently, making your code faster and more optimized. Happy coding! 🚀💻📚