平成28年度 春期 午前Ⅱ 問2

✓ これが正解イ(2k＋1)^n−1

解説

各ノードに2k個、子は2k＋1個なので、合計は(2k＋1)^n−1です。

格納数が最大になるのは、すべてのノードが上限の2k個のレコードをもつときです。2k個のレコードをもつノードは、レコードの間と両端に合わせて2k＋1個の子をもてます。したがって1段目は1ノード、2段目は2k＋1ノード、m段目は(2k＋1)^(m−1)ノードになります。1段目からn段目までのレコード数の合計は、2k×{1＋(2k＋1)＋…＋(2k＋1)^(n−1)}で、等比数列の和の式を使うと2k×{(2k＋1)^n−1}÷2kとなり、(2k＋1)^n−1に整理できます。n＝2で確かめると、2k＋(2k＋1)×2k＝4k^2＋4kで、(2k＋1)^2−1と一致します。ノードの数を段ごとに数え、最後に等比数列の和でまとめる、という手順で解く問いです。

ほかの選択肢はなぜ違うのか

• ア(2k＋1)^(n−1)−1：(2k＋1)^(n−1)−1は、同じ考え方でn−1段目までの合計を求めた値です。n段目のノードがもつレコードを数えていないので、1段目からn段目までの最大値としては少なすぎます。
• ウ2(k＋1)^(n−1)−1：2(k＋1)^(n−1)−1は、ルートが1個、ほかのノードが下限のk個のレコードをもつ場合の合計で、n段の最小の格納数にあたります。最大を求める問いなのに、最も少ない場合を数えています。
• エ2(k＋1)^n−1：2(k＋1)^n−1は、ルートが1個、ほかのノードがk個のレコードをもつ最小の場合を、n＋1段目まで数えた値です。最大の場合を求める式ではなく、段の数も一つずれています。