data-structures - B树的叶子最少？

Question

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

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

我忽略了什么吗？

Answer 1

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

但是假设您的意思是 M 和 L 是相同的数字 k，那么您的最小叶 3-B 树的高度为 2 确实只有四片叶子（假设高度 h 的标准定义）。

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

这是一个很好的概述：

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

*我假设您指的是技术上的 B+ 树，因为 B 树在实践中并未使用，尽管每个人都称 B+ 树为 B 树。