2分探索木とは？図解でわかる【基本情報技術者試験対策】

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

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

木構造

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

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

スポンサーリンク

木構造の構成要素

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

2分木

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

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

2分探索木

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

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

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」となり、昇順に並んでいないので不正解です。

基本情報技術者試験おすすめの参考書・問題集

いちばんやさしい 基本情報技術者	『基本情報技術者試験』試験に、短期間で一発合格するための試験対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。
かやのき先生の基本情報技術者教室	基本情報技術者をめざす方のためのやさしいオールインワンタイプの参考書＆問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。
基本情報技術者 パーフェクトラーニング過去問題集	科目A・Bともに万全の対策ができる、定番の過去問題集！科目A・科目Bの両方について万全の対策ができる。
キタミ式イラストIT塾 基本情報技術者	すべての解説をイラストベースで行っているため，とてもわかりやすい解説本。いちばん最初に読む基本情報技術者試験関連の書籍を探している人におすすめ！
出るとこだけ！基本情報技術者［科目B］	基本情報技術者【科目Ｂ】対策の定番書！前提知識＋解き方＋試験問題を掲載。効率よく学習できる。
基本情報技術者 合格教本	出題範囲を体系的にきちんと理解しながら学習したい人におすすめ！基本情報技術者試験の定番テキストの改訂版。
基本情報技術者 超効率の教科書＋よく出る問題集	動画でスムーズに学習スタート、テキストでしっかり理解度を深める！よく出る問題を反復学習することで、合格に直結するチカラが身に付く！