证明具有n个叶子的二叉树的高度至少为log n [英] Proof that a binary tree with n leaves has a height of at least log n

问题描述

我已经能够创建证明，显示一棵树中的最大节点总数等于n = 2 ^(h + 1)-1，从逻辑上我知道二叉树的高度为log n(可以抽出来看看)，但是我在构造正式的证明以显示具有n个叶子的树具有至少" log n时遇到麻烦.我遇到或能够组合在一起的每一个证明总是可以处理完美的二叉树，但是在任何情况下我都需要一些东西.有什么提示可以指引我正确的方向吗?

I've been able to create a proof that shows the maximum total nodes in a tree is equal to n = 2^(h+1) - 1 and logically I know that the height of a binary tree is log n (can draw it out to see) but I'm having trouble constructing a formal proof to show that a tree with n leaves has "at least" log n. Every proof I've come across or been able to put together always deals with perfect binary trees, but I need something for any situation. Any tips to lead me in the right direction?

推荐答案

引理:高度为h的树中的叶子数不超过2^h.

Lemma: the number of leaves in a tree of height h is no more than 2^h.

证明:通过在h上进行归纳来证明.

Proof: the proof is by induction on h.

基本情况:对于h = 0，树仅包含一个根节点，该根节点也是一个叶；根据需要，此处为n = 1 = 2^0 = 2^h.

Base Case: for h = 0, the tree consists of only a single root node which is also a leaf; here, n = 1 = 2^0 = 2^h, as required.

归纳假设:假设所有高度为k或更少的树木的叶子少于2^k.

Induction Hypothesis: assume that all trees of height k or less have fewer than 2^k leaves.

归纳步骤:我们必须证明高度为k+1的树上的叶子不超过2^(k+1).考虑根的左和右子树.这些树的高度不超过k，比整棵树的高度少一.因此，根据归纳假设，每个叶子最多只有2^k个叶子.由于叶子的总数只是根的子树的叶子数的总和，因此根据需要我们有n = 2^k + 2^k = 2^(k+1).这证明了索赔.

Induction Step: we must show that trees of height k+1 have no more than 2^(k+1) leaves. Consider the left and right subtrees of the root. These are trees of height no more than k, one less than the height of the whole tree. Therefore, each has at most 2^k leaves, by the induction hypothesis. Since the total number of leaves is just the sum of the numbers of leaves of the subtrees of the root, we have n = 2^k + 2^k = 2^(k+1), as required. This proves the claim.

定理:具有n个叶子的二叉树的高度至少为log(n).

Theorem: a binary tree with n leaves has height at least log(n).

我们已经在引理中指出，仅由根节点组成的树具有一个叶子，高度为零，因此在这种情况下该主张是正确的.对于具有更多节点的树，证明是矛盾的.

We have already noted in the lemma that the tree consisting of just the root node has one leaf and height zero, so the claim is true in that case. For trees with more nodes, the proof is by contradiction.

让n = 2^a + b其中0 < b <= 2^a.现在，假设树的高度小于a + 1，这与我们打算证明的定理相反.然后高度最大为a.通过引理，高度为a的树的最大叶子数为2^a.但是我们的树有n = 2^a + b > 2^a的叶子，因为0 < b;矛盾.因此，高度小于a+1的假设必须不正确.这证明了索赔.

Let n = 2^a + b where 0 < b <= 2^a. Now, assume the height of the tree is less than a + 1, contrary to the theorem we intend to prove. Then the height is at most a. By the lemma, the maximum number of leaves in a tree of height a is 2^a. But our tree has n = 2^a + b > 2^a leaves, since 0 < b; a contradiction. Therefore, the assumption that the height was less than a+1 must have been incorrect. This proves the claim.

这篇关于证明具有n个叶子的二叉树的高度至少为log n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！