disjoint-union - 不相交集 DS

Question

我一直在研究不相交的集合数据结构。

我有一个查询，在同时使用按等级联合和路径压缩时，如果我们跳过使用按等级联合和分配优先级（父）而没有任何等级比较（根/代表元素的等级）的两组（树）会影响运行时间。

尽管在合并两个集合时需要加权联合启发式，但将较小的集合附加到较大的集合以使更新尽可能少以指向代表元素。

Union-by-rank（类似于weighted-union）在合并两个集合时使用。但是如果我们跳过比较排名并随机分配优先级，它不会影响运行时间？那我们为什么要使用它..看不清楚，如果我错了，请帮助我理解它。

//不进行排名比较

联合（x，y）

x.父=y;

通用代码

union(x,y){

if(x.rank>y.rank)
    y.parent=x;
else
    x.parent=y;

if(x.rank==y.rank)
    y.rank=y.rank+1;
 }

Answer 1

如果我们考虑 n 个不相交的单例元素，并以这样的方式对它们应用联合函数，使得一个集合的根（即在表示集合中形成的树的根）总是与一个单例元素联合，那么在所有这些联合中情况下路径压缩没有效果，我们最终可能会创建一个链表。

在这种最坏的情况下，单个查找的复杂度可以是 θ(n)，而排除两个集合的查找的并集仍然是 θ(1)，就像按等级包括并集时一样。因此，集合上单个查询的最坏情况复杂性通过使用按秩并集得到改善，使其保持 θ(lgn)。

如果我们考虑在所有查询之后最终得到 1 或恒定数量的最终集合的情况，那么如果使用路径压缩，则按等级联合会对整体复杂性产生一些影响。