データ構造についての質問です。

質問

データ構造についての質問です。

１．平均16個の子に持つようなB木があり、その深さが３である場合，記録されている
　　データの個数はどのくらいになるか計算しなさい。

２．B 木に利用するm 分木について，m の値を大きくすればするほど探索効率は良くなる。
　　正しいか，正しくないか？正しくない場合はその理由を答えなさい。

という2つの問題があります。1番は記録されているデータの個数の計算方法がわかりません。2番はmを大きくすると深さが浅くなるので効率は良くなると思うのですが合っているかわかりません。
どなたかご指導よろしくお願いします。

回答No.2

kmee · ベストアンサー

1)
深さ1の場合: 平均16個
深さ2の場合: 深さ1の各子が平均16個ずつ子を持つから 16x16
深さ3の場合: 深さ2の各子が平均16個ずつ子を持つから....

2)
データ数nとすると、 m≧nで、深さ1のn分木になります。
深さ1のn分木は、n要素のリストと同じです。
B木の目的を考えれば、リスト構造と木構造のどちらが探索効率がよいか、わかるのでは無いでしょうか。

B木の平均探索回数は
(各深さでの平均探索回数) * (深さ)
です。
各深さの探索は、そのノードに注目すれば、要素mのリストでの探索と同じです。
深さはmを底とする対数 log_m(n) となります。

これで、式を作って、 mがk倍されたら計算量が何倍になるか、計算してみてはどうでしょうか。

回答No.3

Tacosan

2 についてだけど, 「探索効率」が何を意味するのか分かりません. いくつか想定できるんだけど, そのうちのどれなのか (あるいはいずれでもないのか) が判断できない.

回答No.1

noname#115788

１の問題

データの個数は決まっていないので最低値を計算して、その最低値以上であると回答すればよい。
深さ３のＢ木の接点の最低数は根（ルート）含めて３個です。根の分岐が１、その接点の分岐が１、それで平均１６個のなるためには・・・

２の問題

Ｂ木は良くハードディスクに使用されていますね。それで考えるとＢ木の探索はヘッドのシーク回数が少ない方が有利ということになります。ｍを大きくすれば木の高さは小さくなりますから、シークの回数は？