Generic implementation of the Quick-Union algorithm with Path Compression

Working my way through Algorithms, Fourth edition by Robert Sedgewick & Kevin Wayne. I implemented a generic version of the Quick-Union algorithm and added Path Compression (not described in the book) to it.

Mainly I'm looking for feedback on these two aspects and whether I might have overlooked a side effect.

```
public class WeightedQuickUnionWithPathCompression {
private final Map components = new HashMap<>();
private final Map treeSizes = new HashMap<>();

public WeightedQuickUnionWithPathCompression(T[] components) {
for (T component : components) {
this.components.put(component, component);
this.treeSizes.put(component, 1);
}
}

public void connect(T leftComponent, T rightComponent) {
Objects.requireNonNull(leftComponent);
Objects.requireNonNull(rightComponent);

if (areConnected(leftComponent, rightComponent)) {
return;
}

T leftComponentTree = find(leftComponent);
T rightComponentTree = find(rightComponent);

int leftTreeSize = getTreeSize(leftComponentTree);
int rightTreeSize = getTreeSize(rightComponentTree);
if (leftTreeSize < rightTreeSize) {
components.put(leftComponentTree, rightComponentTree);
treeSizes.put(rightComponentTree, leftTreeSize + rightTreeSize);
} else {
components.put(rightComponentTree, leftComponentTree);
treeSizes.put(leftComponentTree, leftTreeSize + rightTreeSize);
}
}

private T find(T component) {
while (!component.equals(components.get(component))) {
components.put(component, components.get(components.get(component))); // Path compression
component = components.get(component);
}
return component;
}

private int getTreeSize(T component) {
return treeSizes.get(component);
}

public boolean areConnected(T leftComponent, T rightComponent) {
O

In find() and areConnected(), you should be able to use == rather than .equals() since you are comparing references, not contents.

Your find() loop is a bit inefficient:

• You do components.get(component) once during the while condition test, and again during path compression.

• You do components.put(component, …) during path compression, then immediately lookup components.get(component) to advance the loop.

The remedy is to introduce two temporary variables, which I call parent and grandparent.

I've chosen to write it as a for loop with side-effect assignments, but of course you can choose to use a while loop without side-effect assignments.

private T find(T c) {
    // Lookup with path compression
    for (T parent, grandparent; (parent = components.get(c)) != c; c = grandparent) {
        components.put(c, grandparent = components.get(parent));
    }
    return c;
}

connect() calls areConnected(), which performs redundant work. I suggest…

public void connect(T leftComponent, T rightComponent) {
    Objects.requireNonNull(leftComponent);
    Objects.requireNonNull(rightComponent);

    T leftComponentTree = find(leftComponent);
    T rightComponentTree = find(rightComponent);

    if (leftComponentTree == rightComponentTree) {
        return;     // Already connected
    }

    …
}

StackExchange Code Review Q#49186, answer score: 2