平成31年度 春期 午前 問5

✓ これが正解ウ空き領域の大きさをキーとする 2 分探索木

解説

大きさを鍵にした2分探索木なら、対数の時間で選べます。

最適適合は、要求量以上の空き領域のうち最小のものを選ぶ方式です。この選び方に合うデータ構造とは、空き領域を大きさの順に並べた形の中から、要求量以上で最も小さいものを素早く見つけられる仕組みです。空き領域の大きさをキーにした 2 分探索木では、要求以上の中で最小の値を、木を上から下へたどるだけで探せます。要素数を n とすれば、平均で対数のオーダで済みます。順序が保たれているので、割当てのたびに全体を見直す必要もありません。追加や削除の際も、木の再編は局所的に済み、割当て時間が長く伸びません。

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

• ア空き領域のアドレスをキーとする 2 分探…：アドレスをキーにした 2 分探索木は、番地の順で空き領域を並べる形です。要求量以上の中で最小のものを探すには結局全体を走査する必要があり、割当てのたびに時間が要素数に比例して伸びます。
• イ空き領域の大きさが小さい順の片方向連結リ…：大きさが小さい順の片方向連結リストは、先頭から順に見て要求量以上のものに当たるところまで進みます。走査そのものが要素数に比例して伸びるため、平均処理時間は対数のオーダに収まりません。
• エアドレスに対応したビットマップ：アドレスに対応したビットマップは、番地ごとに使用中かどうかだけを 1 ビットで持つ形です。連続した空きの塊を大きさ順で扱う機構がなく、要求量以上で最小のものを取り出すには結局走査が必要になります。