0

在不相交的联合中，假设我们必须合并两棵高度分别为 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。k可以通过合并两个较小的子树来获得包含节点的树。假设这两个较小的树分别包含“a”和“b”节点，我们可以在不失一般性的情况下假设a<=b。现在a>=1，因此没有办法从初始情况开始获得具有零节点的树，并且 k=a+b。它遵循a<=k/2and b<=k+1, since k>1, bothk/2 < k和(k-1) < kand 因此a<k, and b<k。

我上面的问题是

  1. 我们如何得到上面的“它遵循 a<=k/2 和 b<=k+1”语句。

谢谢！

4

1 回答 1

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较大的一半，比a必须小于 的一半k。

于 2011-10-03T11:45:10.127 回答