algorithm - 树中内部节点数的证明

Question

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

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

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

有人可以提供一个归纳证明吗？

Answer 1

归纳证明：
我们将通过对L- 树中叶子的数量进行归纳来证明它。
base：一棵由一片叶子组成的树实际上是一棵只有根的树。它有 0 个内部节点，并且声明是正确的。
假设该声明对于具有 L 个叶子的压缩树是正确的。
步骤：令 T 为一棵有 L+1 片叶子的树。选择任意一片叶子，让它为 l，然后修剪它。
为了使树再次压缩 - 你需要让 l 的父亲成为一片叶子 [如果 l 的父亲有超过 2 个儿子，包括 l，请跳过这一步]。我们通过赋予它与 l 的兄弟相同的值并修剪兄弟来做到这一点。
现在你有一棵树 T' 有 L 个叶子。
通过归纳：T' 最多有 L-1 个内部节点。
所以，T 有 L-1+1 = L 个内部节点，最多有 L+1 个叶子。
量子点

替代证明：
具有 L 个叶子的二叉树有 L-1 个内部节点 (1 + 2 + 4 + ... + L/2 = L-1)
因为在“最坏情况”你有一个二叉树 [每个内部节点都有至少有 2 个儿子！]，那么你不能有超过 L-1 个内部节点！

Answer 2

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

Answer 3

好的，那我去试试。

首先定义树：

T_0 = { Leaf }

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

Trees = sum T_i

现在，您的断言的（草图）证明。

1. 很容易检查它T_0

2. For T_i: 如果t \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）。

3. 通过归纳，如果断言适用t in T_i于所有i，它适用于t in Trees。