在不相交聯合中,假設我們必須合併兩個高度分別爲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
。
我上面的問題是
- 我們如何得到了 「可以得出:< = K/2和B < = K + 1」 的上述聲明。
謝謝!