嗨，这是我第一次在这里发帖，
我一直在想一个学习的问题，但一直想不通：
我们考虑了不相交集抽象数据类型的林实现，它具有按大小加权并和路径压缩。最初，每个元素都在一个节点树中。
从上述初始状态开始：
给出一个（短的）并集和查找操作序列，其中最后一个操作是并集，使较高的树a成为较短树b的子树（即a的高度严格大于b的高度）。
显示最后一个并集合并的两棵树a和b
提示：您可以从n=9个元素开始，每个元素都在一个节点树中。
我不知道这是怎么回事，因为较小的树总是因为按大小合并而与较大的树合并？
谢谢。
最佳答案
我不想回答你的家庭作业，但这个问题已经很老了，你的学期可能已经结束了，无论如何，一个提示应该足够有用了。
按大小合并和按高度合并是有区别的，主要是因为路径压缩。具体地说，路径压缩可以产生非常高的节点，因此树的节点很多，但是高度很短。例如，可以使用union find with path compression创建两棵树：
|T1: o (n=5, h=2)
| /| |\
| o o o o
|
|T2: o (n=4, h=3)
| /|
| o o
| |
| o
如果下一个操作是这两棵树的合并，则“按列合并”和“按高度合并”算法将选择不同的父级。
在实践中，通常使用“等级联合”。秩是高度的一个上界，它可以在恒定时间内更新，并产生最佳的渐近运行时间。一个网络搜索会对这个算法产生很多好的解释。