为什么我们不在路径压缩后更新不相交集的等级？

Question

我制作了一个带有秩启发式和路径压缩的不相交集模板。

template <typename T>
class disJSet
{
    map<T,T> parent;
    map<T,int> rank;
    public:
    //Linear time complexity 
    void makeSet(vector<T> it)
    {
        for(T i:it)
        {
            parent[i]=i;
            rank[i]=0;
        }
    }

    //Time complexity of O(log*n)
    T find(T el)
    {
        if(el!=parent[el])
            parent[el]=find(parent[el]);
        
        return parent[el];
    }

    //Time complexity of O(log*n)
    bool unionOp(T a,T b)
    {
        T a_id=find(a);
        T b_id=find(b);

        if(a_id==b_id)
            return false;

        if(rank[a_id]<rank[b_id])
            parent[a_id]=b_id;
        else
        {
            parent[b_id]=a_id;
            if(rank[a_id]==rank[b_id])
            {
                rank[b_id]=rank[b_id]+1;
            }
        }
        return true;    
    }
};

路径压缩是在find()方法中实现的。为什么我们在路径压缩后不更新排名？

我的原因：每当有调用查找时，由于路径压缩，每个中间节点都会成为叶节点。并假设如果这是父级最长的子树，那么它的高度现在已更改。但是我们不更新父/根节点的等级。

这可能会在联合操作中产生差异。例如，两个元素的联合将导致通过比较它们的等级使一棵树成为另一棵树的子节点。但是由于调用 ，ranks 可能不代表树的最大高度find()。

Answer 1

您无法在路径压缩后更新排名，因为到该根的其他路径可能比新路径长度长。

而且路径压缩后不需要更新排名，因为它只需要表示路径长度的上限。