我正在观看 Robert Sedgewick 关于改进快速联合的视频。( https://youtu.be/sEo6LlPxpHE?t=267 )
在那里，他使用树的大小而不是高度。实际上问题是找到根节点。如果高度很高，则很难找到。所以我们应该找到一种方法来减轻高度的影响。只有当我们比较高度时，它才会按预期工作吗？将较短的树连接到较高的树不会解决问题，而是这样做：将具有较少节点的树连接到具有较多节点的树？
下面的情况呢？
根据视频中的逻辑：
一棵树的大小 = 4
B 树的大小 = 7
如果您将 A 连接到 B 。实际上，我们正在使生成的树更高（高度 4）。但是如果我们根据树的高度来完成它，我们可以通过将树 B 连接到 A 来解决它。因此生成的树的高度为 3。
我对吗 ？如果错了，我错在哪里？
请记住，不相交集森林的大多数实现都应用了路径压缩优化，其中在每次查找期间，您更改链中所有节点的父指针，以便它们都指向它们的代表。
事实证明，如果您使用路径压缩并在压缩之前跟踪所有节点的高度，那么按高度链接的渐近性能（通常称为union-by-rank，其中“rank”是先验高度到任何压缩）和重量链接是相同的。两者都给出了逆阿克曼时间复杂度。这个结果来自这篇论文，它技术性很强，但确实证明了这两个结果。
但是，即使您不这样做，还有另一种方法可以看到这两种方法（大致）彼此相等。请注意，如果您有一棵高度为 1 的树，则它必须至少有两个节点。为什么？好吧，制作高度为 1 的树的唯一方法是合并到高度为零的树，每个树都必须至少有一个节点。使用类似的逻辑，您可以看到，如果您有一棵高度为 2 的树，那么它必须至少有四个节点，因为要形成它，您必须将两棵高度为 1 的树合并在一起。更一般地，您可以证明一棵高度为 n 的树中必须至少有 2 n 个节点。因此，按高度合并与按重量合并基本相同，因为树木的高度和大小之间存在密切联系。
希望这可以帮助！
首先，正如其他人所提到的，尺寸和高度都具有相似的性能。
但是，为什么我们选择尺寸而不是高度？我认为这是因为在路径压缩期间高度会改变，而大小不会。
这是我自己的意见，因为我在任何地方都没有找到。希望是真的。
按大小或按高度加权的快速联合大致相同，它们具有相同的上限，正如 @templatetypedef 之前提到的。
让我再分享一些细节。
在按大小加权的策略中，让一棵树T只有一个节点x，其深度（或高度）为 1。只有在合并到另一棵大小等于或大于 的树时， hh 才会增加 1 。所以，TT
换句话说，h 的上限是 lgN + 1(· h <= (lgN + 1))。
如果 union-find 是按高度加权的呢？很明显，当 tree depthh = 2时，至少需要 2 个节点。当 时h = 3，最小节点数为 4（两棵深度为 2 的树都合并了最小节点数）。情况和上面一样，
对于按高度加权的联合查找，我们有结论：h <= (lgN + 1). 也就是说，无论是按高度还是按大小加权，它们的深度都具有相同的上限。
关于你提到的令人困惑的情况，这是由合并的随机性引起的，我们已经找出了深度的上限，假设它是5，但结果可能是4or 3，或者任何不超过5的数字，基于序列的合并。
还有一句话，教科书算法（第 4 版）在 1.5.14 的创意问题第 237 页确实提到了按高度加权的快速联合。