3

嗨，这是我第一次在这里发帖，

我一直在尝试解决一个学习问题，但无法弄清楚：

我们考虑不相交集抽象数据类型的森林实现，按大小加权联合和路径压缩。最初，每个元素都位于单节点树中。

从上述初始状态开始：

  1. 给出一个（短）UNION 和 FIND 操作序列，其中最后一个操作是一个 UNION，它导致较高的树 A 成为较短树 B 的子树（即 A 的高度严格大于 B 的高度） .

  2. 显示最后一个 UNION 合并的两棵树 A 和 B

提示：您可以从 n = 9 个元素开始，每个元素都位于单节点树中。

我不确定这将如何工作，因为较小的树总是与较大的树合并，因为按大小联合？

谢谢。

4

1 回答 1

2

我不想回答你的作业，但是这个问题已经足够老了，你的学期可能已经结束了，无论如何，一个提示应该会有所帮助。

union by size和 union by height之间存在区别，主要是因为路径压缩。具体来说，路径压缩会导致节点的度数非常高，因此树的节点很多但高度非常短。例如，您可以使用带有路径压缩的 union find 创建两棵树：

|T1:   o    (n=5, h=2)
|    /| |\ 
|   o o o o
|    
|T2:   o    (n=4, h=3)
|     /|
|    o o
|      |
|      o

如果下一个操作是这两个树的合并，“排序联合”和“高度联合”算法将选择不同的父级。

在实践中，通常使用“按等级联合”。秩是高度的上限，可以在恒定时间内更新，并产生最佳的渐近运行时间。网络搜索将对该算法产生许多很好的解释。

于 2013-01-19T01:55:38.540 回答