Generic implementation of the Quick-Union algorithm with Path Compression Working my way through Algorithms, Fourth edition by Robert Sedgewick &amp; 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&lt;T&gt; {
    private final Map&lt;T, T&gt; components = new HashMap&lt;&gt;();
    private final Map&lt;T, Integer&gt; treeSizes = new HashMap&lt;&gt;();

    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 &lt; 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) {
        Objects.requireNonNull(leftComponent);
        Objects.requireNonNull(rightComponent);
        return find(leftComponent).equals(find(rightComponent));
    }
}
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
    }

    …
}