algorithm - bツリーの実行時間の上限

Question

Art of Computer Programmingの、485ページの下部にあります。

次数mのBツリーがあり、N個のキーがあるとすると、N+1の葉がレベルlに表示されます。

レベル1、2、3 ...のノード数は、少なくとも2,2 [m / 2]、2 [m / 2] ^2..です。

（ここで[]は上限を示します）

そしてKnuthは与える

N + 1> = 2 [m / 2] ^（l-1）

---

私の質問は：

これはN+1> = 2 + 2 [m / 2] +2 [m / 2] ^ 2 + ... + 2 [m / 2] ^（l-1）ではありませんか？

（l-1）レベルのノードのみを考慮に入れることのポイントは何ですか？

Answer 1

k個のキーを持つブランチノードには、 k +1個の子があります。したがって、レベルl -1には多くのノードがありますが、レベルlにはさらに多くのノードが必要です。

したがって、 N + 1（レベルlのノード数）はレベルl -1のノード数よりも大きくなります。明らかに、レベルl-1の実際のノード数は、レベルlの最小ノード数以上です。l -1.したがって、N +1≥2⌈<i>m/2⌉<sup> l -1。