不相交集，按大小和路径压缩并集;较高的树有可能成为较短树的子树

Question

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

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

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

从上述初始状态开始：

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

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

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

---

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

谢谢。

Answer 1

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

按

大小联合和按高度联合之间存在区别，主要是因为路径压缩。 具体来说，路径压缩可以导致非常高度的节点，因此树具有许多节点但高度非常短。 例如，您可以使用路径压缩的联合查找创建以下两个树：

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

如果下一个操作是这两个树的合并，则"按等级并集"和"按高度并集"算法将选择不同的父级。

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