基本情報技術者平成20年春期 午前問12

午前問12

最下位のレベル以外の節点には必ず左右に子が存在する2分探索木から,あるデータを探索する。節点の総数が15のとき,比較する節点の数は最大で幾つか。ここで,探索するデータが存在するとは限らないものとする。

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

ひとつの節から分岐する枝の数が2以下の木を2分木といい、2分木の節や葉にデータを持たせ要素の探索を効率化する目的で構成されたデータ構造を2分探索木といいます。
問題文にある「節点の総数が15で、最下位のレベル以外の節点には必ず左右に子が存在する2分探索木」は下図のような構造になります。
12.gif/image-size:418×240
目的のデータを探索するときには木構造の根から順にその節がもつデータと探索対象のデータを比較していき、探索対象のデータが存在する方向の枝をたどることを繰り返します。問題文の条件より「探索するデータが存在するとは限らない」ので、探索回数は根で1回、根より1階層下の節点で1回、根より2階層下の節点で1回、最下位レベルのレベルの節点で1回の計4回になります。
12a.gif/image-size:418×240
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop