4

我正在实施不相交集数据结构来进行联合查找。我在 Wikipedia 中看到了以下声明：

...每当相同等级 r 的两棵树联合起来时，结果的等级为 r+1。

当树的等级相同时，为什么连接树的等级只增加一？如果我简单地添加两个等级（即2*r）会发生什么？

4

5 回答 5

7

首先，什么是等级？它几乎与一棵树的高度相同。事实上，现在，假装它与高度相同。

我们希望保持树木矮小，因此跟踪每棵树的高度有助于我们做到这一点。当合并两棵不同高度的树时，我们将较短的树的根作为较高树的根的子节点。重要的是，这不会改变较高树的高度。也就是说，较高的树的等级不会改变。

但是，当合并两棵相同高度的树时，我们将一个根作为另一个根的子节点，这会将整个树的高度增加一，因此我们将该根的等级增加一。

现在，我说等级几乎与树的高度相同。为什么差不多？由于路径压缩，联合查找数据结构用于保持树短的第二种技术。路径压缩可以改变现有树，使其比其等级所指示的更短。原则上，根据实际身高做出决定可能比使用排名作为身高的代表更好，但在实践中，跟踪真实身高信息太难/太慢，而这很容易/快速跟踪排名。

您还问“如果我简单地将两个等级相加（即 2*r）会发生什么？” 这是个有趣的问题。答案可能是什么都没有，这意味着一切仍然可以正常工作，并具有与以前相同的效率。（好吧，假设您使用 1 作为起始排名而不是 0。）为什么？因为使用等级的方式，重要的是等级的相对顺序，而不是它们的绝对大小。如果您添加它们，那么您的排名将是 1,2,4,8 而不是 1,2,3,4（或更可能是 0,1,2,3），但它们仍然具有完全相同的相对顺序，所以一切都很好。您的排名只是 2^（旧排名）。最大的危险是在处理非常大的集合时，您冒着溢出用于表示排名的整数的更大风险（或者，换句话说，您将需要使用更多空间来存储您的排名）。

另一方面，请注意，通过添加两个等级，您是在近似树的大小而不是树的高度。通过始终添加两个等级，无论它们是否相等，您都可以准确地跟踪树的大小。同样，一切都很好，如果你的树非常大，同样需要注意整数溢出的可能性。

事实上，按规模联合被广泛认为是按等级联合的合法替代方案。对于某些应用程序，您实际上想知道集合的大小，对于这些应用程序，按大小联合实际上比按等级联合更可取。

于 2013-08-06T14:36:33.293 回答
6

因为在这种情况下——你添加的一棵树是另一棵树的“子树”——这使得原始子树增加了它的大小。

看看下面的例子：

1           3
|           |
2           4

在上面，每棵树的“等级”是 2。
现在，假设 1 将成为新的统一根，您将得到以下树：

    1
   / \
  /   \
 3     2
 |
 4

加入后，“1”的等级为3，rank_old(1) + 1- 正如预期的那样。1

至于你的第二个问题，因为它会为树木产生错误的高度。

如果我们以上面的例子为例，合并这些树以获得排名为 3 的树。如果我们想将它与这棵树2合并会发生什么：

         9
        / \
      10   11
            |
           13
            |
           14

我们会发现两个等级都是 4，并尝试以与之前相同的方式合并它们，而不支持“较短”的树——这将导致树的高度更高，并最终导致时间复杂度更差。

(1) 免责声明：此答案的第一部分取自我对类似问题的回答（尽管由于您的问题的最后一部分而有所不同）

(2) 请注意，上面的树是按语法制作的，它不能在优化的不相交森林算法中创建，但它仍然展示了答案所需的问题。

于 2013-08-06T13:39:27.267 回答
4

如果您更深入地阅读该段落，您会意识到这rank更像是深度，而不是大小：

由于影响运行时间的是树的深度，因此将深度较小的树添加到较深树的根下，只有在深度相等时才会增加深度。在该算法的上下文中，使用术语“等级”而不是“深度”......

并且相等深度树的合并只会将树的深度增加一，因为一棵树的根被添加到另一棵树的根上。

考虑：

  A                  D
 / \   merged with  / \
B   C              E   F

是：

  A
 /|\
B C D
   / \
  E   F

两者的深度都是 2，合并的深度是 3。

于 2013-08-06T13:36:52.973 回答
3

Rank 表示树的深度，而不是其中的节点数。当您将具有较小等级的树与具有较大等级的树连接时，整体等级保持不变。

考虑将 rank 4 的树添加到 rank 6 的树的根：因为我们在 depth-4 树的根之上添加了一个节点，所以该子树现在的 rank 为 5。我们添加了我们的子树然而，深度 4 树为 6，因此排名不会改变。

现在考虑将 rank 6 的树添加到 rank 6 的第二棵树的根：由于第一个 depth-6 树的根现在在其上方有一个额外的节点，该子树（以及整个树）的 rank 更改为7.

由于树的等级决定了处理速度，因此该算法试图通过始终将较短的树附加到较高的树来保持等级尽可能低，从而保持整体等级不变。仅当树具有相同的等级时，等级才会改变，在这种情况下，其中一棵树会连接到另一棵树的根部，从而将等级提升一级。

于 2013-08-06T13:45:05.773 回答
0

实际上，这里有两个重要的性质我们应该非常清楚......

1) 什么是排名？2）为什么使用排名？？？

等级不过是树的深度。U 可以说等级为树的深度（级别）。当我们创建联合节点时，这些（图节点）将形成为具有最终根节点的树。排名仅针对这些根节点表示。

A merged with D

最初 A 的 rank (level) 0 和 D 的 rank(level) 0 。所以你可以合并它们，使它们中的任何一个成为根。因为如果您将 A 作为根，则等级（级别）将为 1，如果您将 D 作为根，则等级也将为 1

A
 `D

当 root 为 A 时，此处的 rank (level) 为 1。

现在想想另一个，

A    merge   B     ----->   A 
 `D           `C           / \
                          D   B
                               \
                                C

所以级别将增加 1 ，确切地看到没有根（A），最多高度/深度/等级为 2 。排名 [1] -> {D,B} 和排名 [2] -> {C} ......

现在我们的主要目标是在合并时使树的等级（深度）尽可能小。

现在当两个不同等级的树合并时，那么

 A(rank 0) merge B(rank 1)---> B  Here merged tree rank is 1 same as high rank (1) 
                  `C          / \
                             A   C

当小品位低于高品位时。然后合并树的排名（高度/深度）将与更高排名的树相关联的排名相同。这意味着排名不会增加，合并后的树排名将与之前的更高排名相同......

但是如果我们做相反的工作意味着高等级树会超过低等级树，那么请看，

A ( rank 0 ) merge B  (rank 1 ) --> A   ( merged tree rank 2 greater than both )
                    `C               `B
                                       `C

因此，从以下观察中可以看出，如果我们尝试将合并树的等级（高度）保持在最低限度，那么我们必须选择第一个进程。我认为这部分很清楚！

现在你必须了解我们的目标是保持树的高度尽可能低......

当我们使用不相交集联合然后进行路径压缩（找到与节点连接的最终根）当我们从一个节点遍历到它的根节点时，如果它的高度（等级）很长，那么处理时间会很慢。这就是为什么当我们尝试合并两棵树然后我们尝试保持高度/深度/等级尽可能小

于 2019-08-07T09:26:36.377 回答