不相交聯合發現分析

Question

在不相交聯合中，假設我們必須合併兩個高度分別爲h1和h2的樹。使用此技術，如果h1不等於h2，則生成的合併樹的高度將爲max（h1，h2），如果h1 == h2，則h1 + 1的高度爲h1 + 1。在從初始情況開始的任意合併操作序列之後使用該技術，包含'k'個節點的樹最多具有高度 （層的底部）。這通過歸納證明如下。

鹼：當k = 1米的高度爲0。0 < =（地板（日誌1））

感應步驟：考慮k >1和由假設therorm爲所有的m，使得1<=m<k真。通過合併兩個較小的子樹可以獲得包含k節點的樹。假設這兩棵較小的樹分別包含'a'和'b'節點，我們可以假設不失一般性a<=b。現在a>=1，因此沒有辦法從初始情況開始獲得一棵具有 零節點的樹，並且k = a + b。 由此得出a<=k/2和b<=k+1,自k>1，k/2 < k和(k-1) < k，因此a<k和b<k。

我上面的問題是

1. 我們如何得到了 「可以得出：< = K/2和B < = K + 1」 的上述聲明。

謝謝！

Answer 1

我們假設a > k/2，然後b > k/2，因爲b>=a。然後a + b > k/2 + k/2。因此，a + b > k。但我們有k = a + b！所以假設a > k/2導致矛盾，因此是錯誤的。這'證明'a <= k/2。

英文：如果我們兩個部分a和b，其中b較大一半，比a分裂k必須小於的k一半。