证明内部节点的数量在树上

问题描述：

我读到关于压缩尝试和阅读以下内容：证明内部节点的数量在树上

后缀树是有L个叶子和特里树的每个内部节点至少有2名儿童一棵树。

然后作者写道，带有L的树离开，使得每个内部节点具有替代2个孩子，具有最内部L-1个内部节点。我真的很困惑，为什么这是真的。

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

这真的很容易...你有没有尝试过自己？ – jpalecek 2012-01-16 12:49:57

另外，你的意思是“trie”还是“树”？他们是不同的数据结构。 – Marcin 2012-01-16 12:55:57

@Marcin - 树是一种特殊的树，对于这个问题，差异并不重要。 – Ishtar 2012-01-16 12:58:37

答

归纳证明：
我们将通过归纳证明它L - 叶子在树的数量。
基数： 1叶制成的树实际上是一棵只有根的树。它有0个内部节点，并且声明是正确的。
假定对于具有L个叶子的压缩树，该声明是正确的。
步骤：让T是一棵有L + 1叶的树。选择一个任意的叶子，让它为l，并修剪它。
为了再次压缩树 - 你需要让我的父亲成为一片叶子[如果我的父亲有两个以上的儿子，包括l，跳过这一步]。我们通过给予它与兄弟的价值相同的价值，并修整这位兄弟。
现在你有一棵树'T'与L叶。
归纳法：T'最多有L-1个内部节点。
所以，T最多有L-1 + 1 = L个内部节点，并且L + 1离开。 012.M.

另一个证明：
与L-树叶的二进制树具有L-1内部节点（1 + 2 + 4 + ... + L/2 = L-1）
由于在 “最坏情况”你有一棵二叉树[每个内部节点至少有两个儿子！]，那么你不能有更多的L-1内部节点！

@Nemo：如果父亲有两个以上的儿子，包括l，那么通过修剪l，并且什么都不做，新树中有L个叶子[让它成为T']，并且通过归纳假设，在T'中没有更多的L-1内节点。我们没有修剪任何内部节点，所以在T中没有更多的L-1内部节点。这个案子很琐碎而且没有趣味，所以我跳过了它。关于替代证明：这是一个证明的指导原则。证明二进制情况是最糟糕的情况并不困难。 – amit 2012-01-16 16:43:02

是的，我的错误。在评论之前需要醒来。 – Nemo 2012-01-16 16:59:09

你能解释一下：具有L叶的二叉树有L-1个内节点（1 + 2 + 4 + ... + L/2 = L-1）吗？ – crisron 2016-10-17 02:27:06

答

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

答

好的，我会去的。

定义树的一个开始：现在

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
对于T_i：如果t \in T_i它无论是在T_i-1或在新的元素。在前一种情况下，使用IH。在后一种情况下检查断言（如果ci s有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）。
通过归纳法，如果所有i的主张均为t in T_i，则它适用于t in Trees。

不要喂帮助吸血鬼！ – Marcin 2012-01-16 13:41:21

证明内部节点的数量在树上

相关推荐