基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

ひとつの節から分岐する枝の数が2以下の木を2分木といい、2分木の節や葉にデータを持たせ要素の探索を効率化する目的で構成されたデータ構造を2分探索木といいます。
問題文にある「節点の総数が15で、最下位のレベル以外の節点には必ず左右に子が存在する2分探索木」は下図のような構造になります。目的のデータを探索するときには木構造の根から順にその節がもつデータと探索対象のデータを比較していき、探索対象のデータが存在する方向の枝をたどることを繰り返します。問題文の条件より「探索するデータが存在するとは限らない」ので、探索回数は根で1回、根より1階層下の節点で1回、根より2階層下の節点で1回、最下位レベルのレベルの節点で1回の計4回になります。