在不相交联合中，假设我们必须合并高度分别为 h1 和 h2 的两棵树。使用这种技术，如果 h1 不等于 h2，则生成的合并树的高度将为 max(h1, h2)，如果 h1 == h2，则生成的合并树的高度将为 h1+1。在从初始情况开始的任意序列的合并操作之后使用此技术，包含“k”个节点的树具有高度
至多（logk 的下限）。这通过归纳法证明如下。
底数：当 k=1 时，高度为 0。0<= (floor(log 1))
归纳步骤：考虑 k >1 并假设定理对于所有 m 都成立，使得 1< ;=m。通过合并两个较小的子树可以获得包含 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 和 b。
我对上面的问题是
- 我们如何得到上面的“它遵循 a<=k/2 和 b<=k+1”语句。
谢谢！
In disjoint union suppose we have to merge two trees whose heights are respectively h1 and h2. Using this technique, the height of the resulted merged tree will be max(h1, h2) if h1 not equal to h2, or h1+1 if h1 == h2. Using this technique after an arbitrary sequence of merge operations starting from initial situation, a tree containing 'k' nodes has a height
at most (floor of logk). This is proved by induction as follows.
Base: when k=1 height is 0. 0<= (floor(log 1))
Induction step: consider k >1 and by hypothesis therorm is true for all m such that 1<=m<k. A tree containing k nodes can be obtained by merging two smaller subtrees. suppose these two smaller trees contain respectively 'a' and 'b' nodes where we may assume with out loss of generality a<=b. Now a>=1, therefore there is no way of obtaining a tree with
zero nodes starting from the initial situation, and k=a+b. It follows that a<=k/2 and b<=k+1, since k>1, both k/2 < k, and (k-1) < k and hence a<k, and b<k.
My question on above is
- How we got "It follows that a<=k/2 and b<=k+1" statement above.
Thanks!
发布评论
评论（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。用英语来说：如果我们将
k分成两部分a和b，其中b比b大一半， code>a 必须小于k的一半。Let's assume
a > k/2, thenb > k/2, becauseb>=a. Thena + b > k/2 + k/2. Thus,a + b > k. But we havek = a + b! So the assumption thata > k/2is leads to a contradiction, and is thus false. This 'proves' thata <= k/2.In english: if we split
kin two partsaandb, wherebis bigger half, thanamust be less than half ofk.