合併兩棵定向樹？

Question

由於樹高是計算效率的主要障礙，所以一個好的策略是將較短樹的根作爲較長樹的根。

這是不是真的雖然？我的意思是，如果你反過來（將較長的樹合併成較短的樹），那麼樹的高度只會增加1.因爲增加1並不會產生真正的變化（是嗎？），它真的很重要嗎？哪棵樹被合併到哪個？或者有更多的原因可以解釋爲什麼較短的樹合併成更長的樹？

注意我在談論不相交的集合。

Answer 1

不太清楚你正在談論的是哪種樹（二叉搜索樹，不相交集或任何n元樹）。 但無論如何，我認爲原因是儘管增加1並不重要，但如果你做n次合併，你最終會增加n。如果您有一個需要大量合併的數據結構（例如不相交集合），這可能很重要。

Answer 2

問題缺乏背景。例如，在某些樹結構中，單個elemenet可能必須逐個插入（例如，可能重新平衡樹 - 通常需要高度爲O（log n）的樹）;也許這意味着：然後更容易插入更少的元素到更大的樹。

顯然，如果1個事宜的高度增加當事人依賴於高度的頻率增加一個:-)

編輯：隨着disjoint sets，它是重要的是，小的（低）樹將被添加到更大。