algorithm - 按等级联合的目的？

Question

关于不相交集数据结构，按等级进行联合有什么意义？在将数据结构实现为链表（每个联合要更新的对象更少）时，我得到了“加权联合”的目的。

但是，当按等级联合与树实现有关时。在这里，您在合并两棵树时更新根的父母。因此，如果x并且y是树并且您调用union(x,y)了 ，则包含树的根的父级x将链接到包含 的树的根y。这需要恒定的时间 - 那么有什么可以优化的呢？就像如果您只需要更新指针，为什么按等级联合会给出更好的结果？

标签： algorithmdata-structures