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

Question

我一直在研究并查集问题。两个主要的改进是路径压缩和按秩合并。据我所知，按秩合并用于确定如何组合不相交的树。如果我们有两棵不相交的树T1和T2，那么我们将较小秩的树的根节点连接到较大秩的树上。如果我们不使用路径压缩，则秩仅为树的深度。这是有道理的，因为我们不想增加树的深度，因为它直接影响查找和合并。

我的问题是当我们也使用路径压缩时。我一直在阅读两种优化互补的说法，但我没有看出来。由于路径压缩，秩不再是树的深度（它变成了深度的上界）。假设T1有2个分支（T1的秩为3），T2的深度为2，秩为2。现在假设我们对标记为“*”的T1叶子进行查找操作（使用路径压缩）。现在，如果我们联合T1和T2的根节点，则T2将附加到T1的根节点上（因为查找不会更新秩）。结果得到的树的深度为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

这里有什么我不明白的吗？路径压缩和按秩合并如何互补？我知道秩只是树深度的上界，但我不明白按秩并如何提高结构的整体性能。与随机组合根节点相比，这种方式更好在哪里？

先感谢您的帮助。

- Hermon

---

为什么你说“如果我们将T1附加到T2上，性能会更好”？如果联合操作后跟着对每个节点的查找，那么这将导致更多的工作量。 - Matt Timmermans

我对更好的性能的理解是，如果树更深，则查找和合并需要更多时间来定位它们的顶级代表（根）-由于路径压缩，后续的查找和合并操作将更快。但这只是路径压缩的作用。我只是不明白按秩合并如何提高性能，因为秩并不能准确地捕捉树的深度。我想我的问题可以更好地表达 - 如果我只使用路径压缩来实现这个算法，我会失去什么？ - Hermon

Answer 1

按秩合并确保树的最大深度为log N，因此它对每个操作都有一个O(log N)的最坏情况上界。

路径压缩没有任何特殊的合并规则，使每个操作的摊销成本有一个O(log N)的上界，但没有限制最坏情况的成本。(甚至可能有更紧密的成本上界，但我知道如何证明的是O(log N))

两者结合起来，可以得到最坏情况下的O(log N)限制，摊销上界提高到了O(N)，实际上相当于常数。这样两种优化方法是相辅相成的。

你说得对，有一些操作序列不是完全最优的，但是保证比没有它更好，这才是最重要的。我们通常不会花费精力优化最佳情况的性能，而是优化最坏或平均情况。

- Matt Timmermans

---

哦，那太有道理了。非常感谢你。 :) - Hermon

Answer 2

问题中的图T2，如果使用按秩合并/按权重合并，则无法首先形成。

您可以尝试使用3个节点自己尝试一下，看看是否能够得到图T2。这是不可能的。甚至图T1也无法首先形成。

您可以从N个节点的示例开始，如果您从一开始就使用按秩合并/按权重合并，您将实际上会发现它会给出最佳的合并结构（某些操作序列可能不会给出最佳合并，但大多数情况下它会给出最佳结果）。

换句话说，按秩合并/按权重合并有助于find方法（进而使用路径压缩进行进一步优化），使得find操作几乎成为常数时间操作。

- Swaroop As