路径压缩和按等级合并如何相辅相成？ [英] How do path compression and union by rank complement each other?

问题描述

我一直在读有关工会发现问题的文章。两个主要的改进是路径压缩和按等级合并。据我所知，按等级合并是用来确定如何组合不相交的树的。如果我们有两棵不相交的树T1和T2，那么我们将排名较小的树的根附加到排名较高的树上。如果我们不使用路径压缩，那么排名就是树的深度。这是有意义的，因为我们不想增加Out树的深度，因为它直接影响Find和UNION。

我的问题是当我们也使用路径压缩时。我一直读到这两个优化是相辅相成的，但我看不到这一点。由于路径压缩，等级不再是树的深度(它成为深度的上限)。假设T1有2个分支(设T1的秩为3)，T2的深度为2，秩为2。现在假设我们在T1的叶子上执行查找操作(带有路径压缩)，下面标有"*"。现在，如果我们并集T1的根和T2的根，那么T2将附加到T1的根(因为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

我是不是漏掉了什么？路径压缩和按等级合并如何相辅相成？我知道等级只是树深度的上限，但我看不出逐个等级的联合如何改善结构的整体性能。这怎么会比随机组合词根的联合更好呢？

提前感谢您的帮助。

推荐答案

UNION by RANK确保树的最大深度为LOG N，因此它为每个操作设置了O(LOG N)的最坏情况上限。

没有任何特殊并集的路径压缩规定了每个操作的摊销成本的上限为O(LogN)，但不限制最坏情况下的成本。(摊销成本甚至可能有更严格的界限，但我知道如何证明O(LogN))

将两者结合使用，可以得到和最坏情况下的O(LogN)极限，摊销界改进为O(𝛼(N))，这实际上是恒定的。在这种情况下，这两个优化是互补的。

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

这篇关于路径压缩和按等级合并如何相辅相成？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！