Bツリーのリーフの数は？

Question

私はk-Bツリーの場合、少なくとも2（k + 1）^（h-1）の葉が存在していることを証明するように求められています。

私はちょうど3-Bツリーを素早くスケッチしていますが、樹木が高さ2に達するには少なくとも最低4枚の葉が残っていなければなりませんが、2（k + 1）^（h- ）は8葉になる。

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

Answer 1

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

しかし、MとLが同じ数kであると仮定すると、高さ2の-Bツリーは、実際には4つの葉しか持たない（高さhの標準的な定義を仮定して）。

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

これは良い概要です：

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

*誰もがB +木Bを呼び出してもBツリーは、実際に使用されていないとして、私は、あなたが技術的にB +ツリーです何を指していると仮定しています木。