基本情報技術者 PR

【基本情報】2分探索木を完全に理解する!

記事内に商品プロモーションを含む場合があります

データをどうやって探す?

突然ですが、下の問題をどうやって解きますか?

適当に開けていきますか?①から順番に開けていきますか?
実は効率良く探す方法があります。それが2分探索です。

2分探索とは

2分探索では、昇順に並んだ値からある値を探す時に、まず、中央の値と探したい値を比較し、探したい値が前半にあるか後半にあるかを明らかにします。そして検索範囲を絞り込んだら、再度、その範囲の中央の値と探したい値を比較し、探したい値がその範囲の前半にあるか後半にあるかを明らかにします。。。というのを繰り返しながら値を探します。

具体的に見てみましょう。まず中央の箱(⑤)を開けます。⑤には68が入っていたので、25は前半(①~④)にあることが分かります。

ということで次は①~④の中央の箱、③の箱を開けます(②でもOKです)。③には19が入っていたので、①~④の後半(④)にあることが分かります。

ということで④の箱を開けてみましょう。④には25が入っていました。

このように、

  1. 中央の値と探したい値を比較して、前半にあるか後半にあるかを明らかにする
  2. 絞った探索範囲の中央の値と探したい値を比較して、絞った探索範囲の中から更に前半にあるか後半にあるかを明らかにする
  3. 絞った探索範囲の中央の値と探したい値を比較して、絞った探索範囲の中から更に前半にあるか後半にあるかを明らかにする
  4. ・・・
  5. ・・・

というのを探したい値が見つかるまで繰り返すのが2分探索です。
2分探索では効率良く値を探せると言いました。どれくらい効率良いかと言うと、箱が10000個あったとしても平均13回で探せるくらいです。

2分探索では効率良く値を探せるので、最初から2分探索しやすいようにデータを格納したいですよね。では、どのようにデータを格納すれば2分探索しやすくなるのか?その答えが2分探索木になります。

2分探索木とは

2分探索木とは、2分探索しやすくなるようなデータの格納方法や2分探索ってどうやるの?という方法を分かりやすく図にしたものです

先程の箱を全て開けてみましょう。

これらの数字を2分探索木に表すと下図のようになります。〇の部分を節(ノード)と言い、節と節を繋いだ線を枝(ブランチ)を言います。

2分探索木には上の節より大きい数字は右側の節に、小さい数字は左側の節に格納するというルールがあります。

2分探索木を色々な視点で見てみる

節の値を一番下に降ろして見ると……

節の値を一番下に降ろしてみましょう。すると、一番左が小さく、右に行くにつれて大きくなっていることが分かります。2分探索は値が昇順になっていなければ出来ません。その特徴を表していることが分かりますね。

箱を開ける順番

2分探索木では2分探索で開ける箱がすぐに分かります
68は全ての値の中央にある値なので、1回目に開ける箱になります。
また、19と83はそれぞれ【3,11,19,25】の中央にある値、【69,80,83,92,98】の中央にある値なので、2回目に開ける箱になります。
このように、2分探索木で上にある節の箱から開けていけば2分探索になると分かります

基本情報技術者試験での出題例

サンプル問題問5

基本情報技術者
科目A サンプル問題問5

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

正解と解説

正解は”イ”

イは2分探索木の特徴を持っています。

平成31年度春期問5

基本情報技術者
午前試験 
平成31年度春期問5

2分探索木として適切なものはどれか。ここで,1~9の数字は,各ノード(節)の値を表す。

正解と解説

正解は”イ”

イは2分探索木の特徴を持っています。

平成29年度春期問7

基本情報技術者
午前試験 
平成29年度春期問7

顧客番号をキーとして顧客データを検索する場合,2分探索を使用するのが適しているものはどれか。

ア 顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造

イ 顧客番号に関係なく,ランダムに配置されているデータ構造

ウ 顧客番号の昇順に配置されているデータ構造

エ 顧客番号をセルに格納し,セルのアドレス順に配置されているデータ構造

正解と解説

正解は”ウ”

2分探索を使用するにはデータが昇順に並んでいる必要があります。よって答えはウです。