To omptimize the complexity of the find operation, we want to prevent the items from getting too deep in the tree.

At each root, we record the size of the tree. (Even though the size is not always equivalent to depth, we’ll use size as an approximation.)

For the union operation, we make the smaller tree be a subtree of the larger one.

To represent the tree as an array, we make as assumption that the items in the universe are integers from $0$ to $n - 1$.

We use an array of size $n$ and each item $i$ is represented by the element in the array at index $i$. If an item has a parent, we record the parent of that item in the array. Otherwise, the item is a root and we record the size of the tree as a negative number.

With an array representation, the code for the union operation becomes as simple as

void union(int root1, int root2) {
    if (array[root2] < array[root1]) {
        // root2 has a larger tree
        array[root2] += array[root1];
        array[root1] = root2;
    } else {
        // root1 has a larger tree
        array[root1] += array[root2];
        array[root2] = root1;
    }
}

We observe that when we perform the find operation on an item, we traverse the tree by following the parent pointers up to the root.

To optimize future find operation, we will change the parent pointer to the root of tree for each item on which we perform the find operation.

The code for the find operation is now just

void find(int x) {
    if (array[x] < 0) {
        // x is root
        return x;
    } else {
        array[x] = find(array[x]);
        return array[x];
    }
}

The union operation takes $\Theta(1)$ time.

The find operation takes $\Theta(\log u)$ time in the worst case, where $u$ is the number of union operation. Average running time is close to constant.

A sequence of $f$ find operations and $u$ union operations takes $\Theta(u + f \alpha (f + u, u))$ time in the worst case. $\alpha$ is the inverse Ackermann function that is extremely slow-growing.