algorithm - 合并两个有向树？

Question

由于树高是计算效率的主要障碍，一个好的策略是让较短树的根指向较长树的根。

这真的重要吗？我的意思是，如果你反过来（将较长的树合并到较短的树），树的高度只会增加 1。因为增加 1 不会产生真正的区别（会吗？），真的很重要哪棵树合并到哪棵树中？或者是否有其他原因可以将较短的树合并到较长的树中？

注意我说的是不相交的集合。

Answer 1

目前还不清楚您在谈论哪种树（二叉搜索树、不相交集或任何 n 叉树）。但无论如何，我认为原因是尽管增加 1 并不重要，但如果你进行 n 次合并，最终会增加 n。如果您有一个需要大量合并的数据结构（例如不相交集），这可能很重要。

Answer 2

引用缺乏上下文。例如，在某些树结构中，可能必须一个一个地插入单个元素（例如，可能重新平衡树 - 通常您需要高度为 O(log n) 的树）；也许这意味着：然后将更少的元素插入到更大的树中会更容易。

显然，如果高度增加 1 很重要，则取决于高度增加 1 的频率:-)

编辑：对于不相交的集合，将较小（较低）的树添加到较大的树中很重要。