data-structures - Bツリーの葉の数が最も少ない?

Question

kB ツリーの場合、少なくとも2(k + 1)^(h-1) の葉が必要であることを証明するよう求められています。

自分で簡単な 3-B ツリーをスケッチするだけで、ツリーが高さ 2 に達するには少なくとも 4 枚の葉が必要ですが、2(k + 1)^(h-1) の結果は 8 になります。葉。

私は何かを見落としていますか？

Answer 1

まず、典型的な B ツリーの問題*には、内部ノードと葉ノードの 2 種類のノードがあります。したがって、内部ノードの最大数 M とリーフ ノードの最大数 L の両方を指定するのが標準です。

しかし、M と L が同じ数 k であると仮定すると、高さ 2 の最小葉 3-B ツリーには実際には葉が 4 つしかありません (高さ h の標準定義を仮定)。

あなたの問題は式の定義にあると思います。2(k + 1)^(h-1) は、葉のデータ要素の最小数を示します。これは、各葉ノードが少なくとも半分満たされている必要があるため、8 である必要があります。したがって、この例では各リーフ ノードに 2 つの要素が必要であり、ツリーには合計 8 つのデータ要素があります。ただし、リーフ ノードは 4 つしかありません。

これは良い概要です：

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

*誰もが B+ ツリーを B ツリーと呼んでいますが、B ツリーは実際には使用されていないため、技術的には B+ ツリーとは何かを指していると思います。