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

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()方法中实现。为什么我们在路径压缩后不更新排名？

我的理由：每当调用find时，由于路径压缩，每个中间节点都会变成叶节点。假设如果那是父树的最长子树，它的高度现在已经改变。但是我们不更新 parent/root 节点的排名。

这可能会在联合操作中造成差异。例如，两个元素的并集将导致通过比较它们的等级使一棵树成为另一棵树的子树。但是由于调用 find().

，等级可能不代表树的最大高度

Answer 1

您不能在路径压缩后更新等级，因为可能有其他路径到该根，这些路径比新路径长度更长。

而且你不需要在路径压缩后更新等级，因为它只需要表示一个上限路径长度。

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

Why don't we update rank for disjoint set after path compression?

c++

algorithm

time-complexity

disjoint-sets