c++ - 等级和路径压缩算法联合中“等级”的重要性是什么？

Question

我对算法的理解是这样的......

• 路径压缩有助于缩短查找操作的时间，并且超时路径压缩的时间复杂度平均为 O(1)。
  

• 我们决定两者中的哪一个是父节点（在联合操作期间）查看排名。

但是我永远无法理解等级联盟的作用，我不相信我正确理解等级在这里的含义。我也不明白为什么在联合期间，如果要联合的两组的等级相同，则父级的等级增加 1。

Answer 1

https://en.wikipedia.org/wiki/Disjoint-set_data_structure中的段落开头“第一种方法，称为按等级联合，总是将较小的树附加到较大树的根部”表明即使没有路径压缩，按等级联合足以将连接操作的成本降低到最坏情况 O(log n)。

它还解释了，在没有路径压缩的情况下，等级反映了迄今为止生成的树的最大深度，这解释了为什么只有在等级相同时才会增加 - 因为较小的树被添加到较大树的根部，这是最大深度实际增加的唯一情况。