data-structures - B树中叶数最少？

Question

我被要求证明对于k-B树，至少必须有 2(k + 1)^(h-1)叶子。

从我自己自己画出一棵快速的3-B树开始，我一直想到至少要有4片叶子才能使树达到2的高度，但是2(k + 1)^(h-1)导致8树叶。

我在俯视什么吗？

Answer 1

首先，对于典型的B树问题*，有两种类型的节点，即内部节点和叶节点。因此，标准是同时指定内部节点的最大数量M和叶节点的最大数量L。

但是，假设您的意思是M和L为相同的数字k，则高度为2的最小叶子3-B树实际上将只有四片叶子(假设高度为h的标准定义)。

我认为您的问题在于公式的定义。 2(k +1)^(h-1)将为您提供叶子中数据元素的最小数量，该数量必须为8，因为每个叶子节点必须至少充满一半。因此，在此示例中，每个叶节点必须具有2个元素，因此树中总共有8个数据元素。但是，您将只有4个叶节点。

这是一个很好的概述:

http://en.wikipedia.org/wiki/B%2B_tree

*我假设您实际上是指B +树，因为实际上没有使用B树，尽管每个人都称B +树为B树。