树中内部节点数量的证明
我正在阅读有关压缩 trie 的内容，并阅读以下内容：
压缩 trie 是一棵具有 L 个叶子的树，并且 trie 中的每个内部节点至少有 2 个子节点。
然后作者写道，一棵有 L 个叶子的树，每个内部节点至少有 2 个子节点，最多有 L-1 个内部节点。我真的很困惑为什么这是真的。
有人可以为此提供归纳证明吗？
I was reading about compressed tries and read the following:
a compressed trie is a tree which has L leaves and every internal node in the trie has at least 2 children.
Then the author wrote that a tree with L leaves such that every internal node has alteast 2 children, has atmost L-1 internal nodes. I am really confused why this is true.
Can somebody offer a inductive proof for it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
归纳证明：
我们将通过对
L（树中叶子的数量）的归纳来证明这一点。基础：由一片叶子组成的树实际上是一棵只有根的树。它有 0 个内部节点，并且声明是正确的。
假设对于具有 L 个叶子的压缩树来说，该声明成立。
步骤：令 T 为一棵具有 L+1 个叶子的树。选择任意一片叶子，将其设为l，然后修剪它。
为了使树再次压缩 - 你需要使 l 的父亲成为一片叶子 [如果 l 的父亲有超过 2 个儿子，包括 l，则跳过此步骤]。我们通过赋予它与 l 的兄弟相同的值并修剪兄弟来实现此目的。
现在你有一棵树 T'，有 L 个叶子。
归纳起来：T'最多有L-1个内部节点。
所以，T 最多有 L-1+1 = L 个内部节点和 L+1 个叶子。
QED
替代证明：
具有 L 个叶子的二叉树有 L-1 个内部节点 (1 + 2 + 4 + ... + L/2 = L-1)
由于在“最坏情况”下你有一个二叉树[每个内部节点至少有 2 个儿子！]，那么你不能有超过 L-1 个内部节点！
Inductive proof:
we will prove it by induction on
L- the number of leaves in the tree.base: a tree made out of 1 leaf is actually a tree with only a root. It has 0 internal nodes, and the claim is true.
assume the claim is true for a compressed tree with L leaves.
Step: let T be a tree with L+1 leaves. choose an arbitrary leaf, let it be l, and trim it.
In order to make the tree compressed again - you need to make l's father a leaf [if l's father has more then 2 sons including l, skip this step]. We do it by giving it the same value as l's brother, and trimming the brother.
Now you have a tree T' with L leaves.
By induction: T' has at most L-1 internal nodes.
so, T had L-1+1 = L internal nodes, and L+1 leaves, at most.
Q.E.D.
alternative proof:
a binary tree with L leaves has L-1 internal nodes (1 + 2 + 4 + ... + L/2 = L-1)
Since at "worst case" you have a binary tree [every internal node has at least 2 sons!], then you cannot have more then L-1 internal nodes!
您应该尝试绘制一棵具有 L 个内部节点的树，其中每个节点有 2 个子节点，并且有 L 个叶子。如果您明白为什么这是不可能的，就不难理解为什么它对 L-1 内部节点有效。
You should try drawing a tree with L internal nodes, where every node has 2 children and there are L leaves. If you see why this is impossible, it won't be hard to figure out why it does work for L-1 internal nodes.
好的，那我就去尝试一下。
首先定义树：
现在，（草图）你的断言的证明。
很容易检查
T_0对于
T_i： ift \in T_i它位于T_i-1或新元素中。对于前一种情况，请使用 IH。在后一种情况下，检查断言（简单：如果cis有L_i叶子，t有L = L_1 + ... + L_n叶子。它也有不超过L_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1个内部节点（对于子节点，IH，对于自身，+1）因为我们假设每个内部节点至少有两个子节点（这是 trie 定义中的事实），它不超过L_1 + l_2 + ... + L_n - 2 + 1 = L - 1）。 p>通过归纳，如果断言对于所有
i都适用于 T_i 中的t，那么它也适用于 Trees 中的t。Ok, so I'll have a go.
Define trees for a start:
Now, the (sketch) proof of your assertion.
It is easy to check it for
T_0For
T_i: ift \in T_iit is either inT_i-1or in the new elements. In the former case, use IH. In the latter case check the assertion (simple: ifcis haveL_ileaves,thasL = L_1 + ... + L_nleaves. It also hase no more thanL_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1inner nodes (by IH for children, +1 for self). Because we assume each inner node has at least two children (that's the fact from the trie definition), it is no more thanL_1 + l_2 + ... + L_n - 2 + 1 = L - 1).By induction, if the assertion holds for
t in T_ifor alli, it holds fort in Trees.