weighted quick union 的时间复杂度如何为 O(lgN)？请尽量通俗易懂的回答，我看了很多答案都看不懂

Question

我正在学习普林斯顿大学的加权快速联合算法。我坚持这个算法如何具有 O(lgN) 的时间复杂度的数学证明？我知道它比在大树下合并小树的普通快速联合更好，但它们是如何产生时间复杂度 lgN 的，这是我无法理解的。如果你能帮助我理解这一点，那将会很有帮助。这是我正在处理的代码：

public class WeightedQuickUnionUF {

    private int[] id;
    private int[] sz; //an extra array `enter code here`to count the number of objects in the tree rooted at i.

    public WeightedQuickUnionUF(int N){
        sz = new int[N];


        id = new int[N];
        for(int i = 0 ; i<N ; i++){
            id[i] = i;
            sz[i] = 1;
        }
    }

    public int root(int i){
        while(id[i] != i)
            i = id[i];

        return i;
    }//will keep searching until the index and the value at the index are equal

    public boolean connected(int p , int q){
        return root(p) == root(q);
    }//identical to quick union

    public void union(int p , int q){
        int i = root(p);
        int j = root(q);

        if(i == j )
            return;
        if(sz[i] < sz[j]){
            id[i] = j;
            sz[j] += sz[i];
        }
        else{
           id[j]= i;
           sz[i] += sz[j];
        }

        System.out.println(p + " and " + q + " are now connected.");

    }/*Link smaller tree to root of larger tree
    and update the sz[]array */


    public void print(){
        System.out.println("0 1 2 3 4 5 6 7 8 9");
        System.out.println("-------------------");
        for (int j : id) {
            System.out.print(j + " ");
        }
    }

}

Answer 1

如果将较小的树附加到较大的树的根部，则总高度 只会增加 （如果两个高度相同）。

因此，以尽可能少的节点获得尽可能高的树（对应于最坏情况）的策略是仅制作等高的树并将它们合并。

下图是高度从1到4的树，节点数最少。很明显，它们包括n=2^(h-1)个节点。

重要的是要认识到使用“加权”规则，不可能用相同的节点数构建更高的树，因此 h=1+lg(n) 是最坏的情况。（当然，在最坏的情况下，运行查找时间与树高成正比。）

weighted quick union 的时间复杂度如何为 O(lgN)？请尽量通俗易懂的回答，我看了很多答案都看不懂

How does time complexity for weighted quick union is O(lgN)? Please answer in a way as simple as possible, I saw many answers but couldn't grasp them

algorithm

time-complexity

data-structures