Implementing a Union-Find (Disjoint Set) Data Structure in JavaScript

The Union-Find data structure, also known as Disjoint-Set, is a powerful tool for efficiently tracking a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It's commonly used in algorithms like Kruskal's algorithm for finding the minimum spanning tree, connectivity problems, and detecting cycles in graphs. Your task is to implement a Union-Find data structure in JavaScript.

Problem Description

You are required to implement a UnionFind class in JavaScript. This class should provide the following methods:

• constructor(n): Initializes the Union-Find data structure with n elements, where each element is initially in its own set. Elements are numbered from 0 to n-1.
• find(x): Finds the representative (root) of the set that element x belongs to. Path compression should be implemented to optimize future find operations.
• union(x, y): Merges the sets containing elements x and y. Union by rank (or size) should be implemented to keep the tree relatively flat and optimize performance.

Key Requirements:

• Path Compression: During the find operation, update the parent of each node along the path to the root to point directly to the root. This flattens the tree structure.
• Union by Rank (or Size): When merging two sets, attach the tree with smaller rank (or size) under the root of the tree with larger rank (or size). This helps prevent the creation of tall, unbalanced trees. You can use rank as a proxy for height.
• Error Handling: Handle invalid input gracefully. If x or y are out of bounds (less than 0 or greater than or equal to n), throw an Error with a descriptive message.

Expected Behavior:

The find method should return the representative of the set containing the given element. The union method should merge the sets containing the two given elements. After a series of union operations, calling find on any two elements within the same set should return the same representative.

Edge Cases to Consider:

• n = 0: The constructor should handle the case where n is zero without errors.
• x or y out of bounds in find or union.
• x and y already in the same set in union.
• Large number of union and find operations to test performance.

Examples

Example 1:

Input:
UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
uf.union(1, 3);

Output:
uf.find(0) === uf.find(3) // true
uf.find(0) === uf.find(2) // true
uf.find(4) === uf.find(4) // true

Explanation: Initially, each element is in its own set. union(0, 1) merges the sets containing 0 and 1. union(2, 3) merges the sets containing 2 and 3. union(1, 3) merges the sets containing 1 and 3, effectively merging the sets containing 0, 1, 2, and 3. Element 4 remains in its own set.

Example 2:

Input:
UnionFind uf = new UnionFind(10);
for (let i = 0; i < 5; i++) {
    uf.union(i, i + 1);
}
for (let i = 5; i < 10; i++) {
    uf.union(i, i + 1);
}
uf.union(0, 5);

Output:
uf.find(0) === uf.find(9) // true

Explanation: This example demonstrates merging multiple sets sequentially and then merging two larger sets.

Example 3:

Input:
UnionFind uf = new UnionFind(3);
try {
    uf.find(5);
} catch (e) {
    console.log(e.message); // "Index out of bounds: 5"
}

Explanation: This demonstrates error handling when an invalid index is provided to the find method.

Constraints

• 1 <= n <= 100000 (The number of elements initialized in the UnionFind structure)
• 0 <= x, y < n (The elements passed to find and union methods)
• The number of union and find operations can be up to 500,000.
• The time complexity of find and union operations should be close to O(α(n)), where α(n) is the inverse Ackermann function, which grows extremely slowly and can be considered almost constant for practical input sizes.

Notes

• Consider using an array to store the parent of each element.
• The rank array can be initialized with all values set to 0.
• Path compression significantly improves the performance of the find operation.
• Union by rank helps to keep the trees relatively flat, which also improves performance.
• Focus on writing clean, readable, and well-documented code. Comments are encouraged to explain your logic.
• Test your implementation thoroughly with various test cases, including edge cases.