为什么要按军衔合并，而不是数数？

Question

我想知道，为什么在联合查找算法中--根据树的高度合并两棵树--将较小的树附加到较高的树上(在没有路径压缩的简单变体中)。

如果您根据元素数合并它们--用较少的元素将树附加到具有更多元素的树上，这会是一个更糟糕的方法吗？

Answer 1

这是一个有趣的问题。在不进行深入分析的情况下，似乎最好将节点与其各自根的平均距离保持在最小，而不是最大距离。这意味着，将元素较少的树添加到元素较多的树是更好的方法。通过这样做，平均距离最多可以增加1/2，而在另一种情况下，平均距离最多可以增加1。