平成20年春期試験問題 午前問12

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
最下位のレベル以外の節点には必ず左右に子が存在する2分探索木から,あるデータを探索する。節点の総数が15のとき,比較する節点の数は最大で幾つか。ここで,探索するデータが存在するとは限らないものとする。

  • 3
  • 4
  • 7
  • 15
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
ひとつの節から分岐する枝の数が2以下の木を2分木といい、2分木の節や葉にデータを持たせ要素の探索を効率化する目的で構成されたデータ構造を2分探索木といいます。
問題文にある「節点の総数が15で、最下位のレベル以外の節点には必ず左右に子が存在する2分探索木」は下図のような構造になります。
12.gif
目的のデータを探索するときには木構造の根から順にその節がもつデータと探索対象のデータを比較していき、探索対象のデータが存在する方向の枝をたどることを繰り返します。問題文の条件より「探索するデータが存在するとは限らない」ので、探索回数は根で1回、根より1階層下の節点で1回、根より2階層下の節点で1回、最下位レベルのレベルの節点で1回の計4回になります。
12a.gif

Pagetop