树中内部节点数的证明

Question

我正在阅读有关压缩尝试的内容，并阅读了以下内容：

一个压缩的trie是一棵树，它有L个叶子，并且trie中的每个内部节点至少有2个子节点。

然后，作者写出了一个具有L个叶子的树，使得每个内部节点至少有2个子节点，至多有L-1个内部节点。我真的很困惑为什么这是真的。

有没有人能提供一个归纳的证据？

Answer 1

您应该尝试绘制一个包含L个内部节点的树，其中每个节点都有2个子节点，并且有L个叶子。如果你明白为什么这是不可能的，就不难弄清楚为什么它对L-1个内部节点有效。

Answer 2

好的，那我就开始吧。

为开始定义树：

T_0 = { Leaf }

T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 }

Trees = sum T_i

现在，你的断言的(草图)证据。

对于T_0

• For

• ，很容易检查它:如果是t \in T_i，那么它要么是在T_i-1中，要么是在新元素中。在前一种情况下，使用IH。在后一种情况下，检查断言(简单:如果ci有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).

• By归纳，如果断言对所有t in Trees.

的t in T_i都成立，那么它也对i成立