路径压缩和按秩联合如何相互补充？

Question

我一直在阅读有关联合查找问题的信息。两个主要的改进是路径压缩和按等级联合。据我了解，按等级联合用于确定如何组合不相交的树。如果我们有两个不相交的树 T1 和 T2，那么我们将具有较小秩的树的根附加到具有较高秩的树上。如果我们不使用路径压缩，那么等级就是树的深度。这是有道理的，因为我们不想增加输出树的深度，因为它直接影响发现和联合。

我的问题是当我们也使用路径压缩时。我一直读到这两种优化相互补充，但我没有看到。由于路径压缩，秩不再是树的深度（它成为深度的上限）。假设 T1 有 2 个分支（令 T1 的秩为 3），T2 的深度为 2，秩为 2。现在假设我们对下面标有“*”的 T1 的叶子执行查找操作（带有路径压缩）。现在，如果我们联合 T1 的根和 T2 的根，那么 T2 将附加到 T1 的根上（因为 rank 没有被 find 更新）。结果树的深度为 3。但是如果我们将 T1 附加到 T2，我们可以获得更好的性能。

T1:   o   (Rank = 3)    T2:   o  (Rank = 2)
     / \                      |
    o   o                     o
    |                         |
    o                         o
    |   
    *   

在 T1("*") 的叶子上找到后，然后在 T1 和 T2 的根上的联合我们得到

T1:    o       (Rank = 3)      T2: o  (Rank = 2)       
     /| |\                         |
    * o o o                        o
                                   |
                                   o
Result of T1 union T2
       o
   / | | |\
  * o o o  o   Rank = 3 and Max Depth = 3
           |
           o
           |
           o

Am i missing something here? How do path compression and union by rank complement each other? I know rank is just an upper bound on depth of a tree but I don't see how union by rank is improving the overall performance of the structure. How is this better than a union that combines the roots randomly?

Thanks for the help in advance.

Answer 1

Union by rank 确保树的最大深度为 log N，因此它在每个操作上都设置了 O(log N) 的最坏情况上限。

没有任何特殊联合的路径压缩规定每个操作的摊销成本的上限为 O(log N) ，但不限制最坏情况成本。（甚至可能对摊销成本有更严格的限制，但 O(log N) 是我知道如何证明的）

将两者结合使用，您会在最坏情况下获得 O(log N) 限制，并且摊销界限改进为 O((N))，这实际上是常数。通过这种方式，这两种优化是互补的。

您是对的，有些操作序列按等级联合并不是绝对最优的，但是保证比没有它时得到的要好，这才是最重要的。我们通常不会花费精力优化最佳案例性能。我们优化最坏或平均情况。