CLRS 18-2.4キー{1,2、...、n}を最低次数2の空のBツリーに挿入すると仮定します。最後のBツリーにはいくつのノードがありますか？

Question

鍵{1,2、...、n}を最低次数2の空のBツリーに挿入すると仮定します。最後のBツリーにはいくつのノードがありますか？

Answer 1

ルート以外のすべてのノードには、少なくともt-1 = 1個の鍵と、多くても2t-1 = 3個の鍵が必要です。最終的なツリーは、n≧2のとき、最大でn-1個のノードを有することができる。 n = 1にしなければ、空ではないノードにキーを挿入するだけなので、n個のノードが存在することはありません。したがって、常に2つのキーを持つノードが少なくとも1つあります。次に、Bツリーの右背骨ではないノードに複数のキーが存在することはないことに注意してください。これは、挿入するすべてのキーがツリーに格納されているすべてのキーよりも大きいため、ツリーの右端に挿入されるためです。右端の最も深いノードを除くすべてのノードが2つのキーを持ち、右のスプラインの最も深いノードが3つのキーを持つ場合、ノードの数はできる限り少なくなります。したがって、高さ1、1のノード、高さ2,3のノード、...、レベルh、2^h-1のノード。ここで、hはBツリーの高さであり、Bツリーのノード数は#nodes = 2 ^（h + 1）-2-hである。ここで、n = 2 ^（h + = n-lg（n + 1）である。したがって、任意のnに対して、最後のB-Treeはn-⌊lg（n + 1）⌋≦＃nodes≦n-1（n≧2の場合）でなければなりません。