我们是否需要在不相交的集合数据结构中同时进行路径压缩和按等级合并？
Do we need both path compression and union by rank together in disjoint set data structure?
我在研究不相交集数据结构。我研究了路径压缩和按等级联合。最初，所有元素在它们自己的集合中都是单一的，通过执行并集，我们可以组合不同的集合。现在，由于我们按等级执行并集，因此结果树的高度总是最小的。在这一点上，我认为我们可能根本不需要路径压缩。我对吗？如果我错了，请举例说明。
Now since we are performing union by rank the height of the resultant tree is always minimum
如果您按等级合并两棵高度为 h 的树，那么您将得到一棵高度为 h + 1 的树。所以你有两棵高度为 1 的树，你会得到高度为 2 的树。然后如果你得到另一棵高度为 2 的树，你最终可能会将它们组合成一棵高度为 3 的树，依此类推。这可以给你一棵非常高的树。
我读是很久以前的事了，我手边没有 CLRS，但我认为这两种启发式方法本身都不足以保证最佳的复杂性（Akerman 的东西）。我们都需要他们。但在实践中也许只使用一个就可以了。
我在研究不相交集数据结构。我研究了路径压缩和按等级联合。最初，所有元素在它们自己的集合中都是单一的，通过执行并集，我们可以组合不同的集合。现在，由于我们按等级执行并集，因此结果树的高度总是最小的。在这一点上，我认为我们可能根本不需要路径压缩。我对吗？如果我错了，请举例说明。
Now since we are performing union by rank the height of the resultant tree is always minimum
如果您按等级合并两棵高度为 h 的树，那么您将得到一棵高度为 h + 1 的树。所以你有两棵高度为 1 的树，你会得到高度为 2 的树。然后如果你得到另一棵高度为 2 的树，你最终可能会将它们组合成一棵高度为 3 的树，依此类推。这可以给你一棵非常高的树。
我读是很久以前的事了，我手边没有 CLRS，但我认为这两种启发式方法本身都不足以保证最佳的复杂性（Akerman 的东西）。我们都需要他们。但在实践中也许只使用一个就可以了。