広告 基本情報技術者

【基本情報技術者試験】2分探索木

今回のテーマは基本情報技術者試験や応用情報技術者試験で出題される「2分探索木」です。
にぶんたんさくぎ?

問題

2分探索木になっている2分木はどれか。

ア:解答ア  イ:解答イ

ウ:解答ウ  エ:解答エ

基本情報技術者平成28年秋期 午前問6 ※図は過去問を参考に作成したものです。

基本情報技術者試験や応用情報技術者試験で出題される2分探索木の問題、聞きなれない言葉なので難しく感じます。ただし、2分探索木を理解していれば簡単に解くことができます。

本記事では、2分探索木について図解で分かりやすく解説していきます。

本記事で学べること

  • 木構造の構成要素を覚える
  • 2分木2分探索木を理解する
  • 基本情報技術者試験の過去問の解き方を学ぶ

木構造

木構造(きこうぞう)とは、データ構造(※配列のように複数のデータを格納できる入れ物)の1つで木のような階層構造でデータを管理するものです。

木構造は、ハードディスクのファイルシステム(フォルダの下にフォルダやファイルがぶら下がっている)やインターネットのドメイン名などの管理で使用されています。

スポンサーリンク

木構造の構成要素

木構造の要素部分を節(ノード)といい、親のない最上位のノードを根(ルート)、子のないノードを葉(リーフ)、そして ノードとノードを繋ぐ線のことを枝(ブランチ)といいます。

木構造

2分木

2分木(にぶんぎ)とは、どの親ノードも2つ以下の子ノードで構成されている木構造のことをいいます。

以下は2分木のイメージ例です。

2分木

親ノードにぶら下がっている子ノードが1つか2つで構成されているのが2分木です。

2分探索木

2分探索木(にぶんたんさくぎ)とは、2分木の各ノードにデータをもたせることで探索を行えるようにした木であり、木構造の左部分と右部分の関係が「左の子 < 親 < 右の子」になっているのが特徴です。

例えば、数値「1」~「6」を2分探索木にあてはめると次のように格納されます。

二分探索木

左から順に「1、2、3、4、5、6」と昇順に整列されています。

2分探索木の探索

2分探索木は「左の子 < 親 < 右の子」の順にデータが並んでいるので、探索を容易に行うことができます。

ルートから順に探索対象と比較していき、探索対象の方が小さければ左へ、探索対象の方が大きければ右へ移動し、目的のデータを探索していきます。

探索

基本情報技術者試験 過去問の解説

基本情報技術者平成28年秋期 午前問6

問題

2分探索木になっている2分木はどれか。

ア:解答ア  イ:解答イ

ウ:解答ウ  エ:解答エ

基本情報技術者平成28年秋期 午前問6

2分探索木とは、各ノードにデータをもたせることで探索を行えるようにした木であり、木構造の左部分と右部分の関係が「左の子 < 親 < 右の子」になっている2分木です。

解答のア~エが2分探索木の条件に一致しているか1つずつ確認していきます。

解答ア

解答ア

左から順に「10,15,14,16,19」となり、昇順に並んでいないので不正解です。

解答イ

解答イ

左から順に「10,14,16,17,18、19」となり、昇順に並んでいるので正解です。

解答ウ

解答ウ

左から順に「15,16,14,18,19,20」となり、昇順に並んでいないので不正解です。

解答エ

解答エ

左から順に「10,18,14,20,15,19,16」となり、昇順に並んでいないので不正解です。

helpful