YouTip

Following the approach from the previous section, we perform the union(4,9) operation on the Union-Find structure shown in the diagram below.

The structure after the merge operation is:

It can be seen that the tree in this structure is relatively tall. If the number of elements increases, the cost incurred will be relatively high. The solution to this problem is actually quite simple: before performing the specific pointer operation, make a judgment. Point the root node of the set with fewer elements to the root node of the set with more elements. This has a higher probability of generating a tree with fewer levels.

When constructing the Union-Find, an additional parameter is needed: the sz array. sz represents the number of elements in the set with i as the root.

// Constructor

public UnionFind3(int count) {

    parent = new int;

    sz = new int;

    this.count = count;

    // Initialize, each parent points to itself, indicating each element forms its own set

    for (int i = 0; i < count; i++) {

        parent = i;

        sz = 1;

    }

}

When performing the merge operation, the direction of the merge is determined based on the number of elements in the trees where the two elements are located.

public void unionElements(int p, int q) {

    int pRoot = find(p);

    int qRoot = find(q);

    if (pRoot == qRoot)

        return;

    if (sz < sz) {

        parent = qRoot;

        sz += sz;

    } else {

        parent = pRoot;

        sz += sz;

    }

}

After optimization, the merge result is as follows, with 9 pointing to its parent node 8.

Java Example Code

Source Code Package Download: Download

UnionFind3.java File Code:

package .union;

/**

 * Union-Find size optimization

 */

public class UnionFind3 {

    // parent represents the parent node that the first element points to

    private int[] parent;

    // sz represents the number of elements in the set with i as the root

    private int[] sz;

    // Number of data elements

    private int count;

    // Constructor

    public UnionFind3(int count) {

        parent = new int;

        sz = new int;

        this.count = count;

        // Initialize, each parent points to itself, indicating each element forms its own set

        for (int i = 0; i = 0 && p < count);

        // Continuously query its parent node until reaching the root node

        // Characteristic of the root node: parent == p

        while (p != parent)

            p = parent;

        return p;

    }

    // Check if element p and element q belong to the same set

    // O(h) complexity, h is the height of the tree

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);

    }

    // Merge the sets to which element p and element q belong

    // O(h) complexity, h is the height of the tree

    public void unionElements(int p, int q) {

        int pRoot = find(p);

        int qRoot = find(q);

        if (pRoot == qRoot)

            return;

        // Determine the merge direction based on the number of elements in the trees where the two elements are located

        // Merge the set with fewer elements into the set with more elements

        if (sz < sz) {

            parent = qRoot;

            sz += sz;

        } else {

            parent = pRoot;

            sz += sz;

        }

    }

}