【基本情報】2分探索木を完全に理解する！｜絶対分かるちゃちゃちゃITブログ

この記事では2分探索木についてIT初心者にも分かりやすく解説します。

2分探索木

2分探索は以下の方法でデータを探す方法。
①データを昇順(小さいもの順)に並べる。
②真ん中にある数字を見る。
③②で見た数字と探したい数字を比較する。
④探したい数字の方が小さい場合は前半の数字で②と③を行い、大きい場合は後半の数字で②と③を行う。
⑤数字が見つかるまで②～④を繰り返す。
2分探索木は2分探索を図で表したもの。

基本情報では2分探索木に関する問題が出題されます。是非最後までご覧ください。

データをどうやって探す？
2分探索とは
2分探索木とは
- 2分探索木を色々な視点で見てみる
  - 節の値を一番下に降ろして見ると……
  - 箱を開ける順番
基本情報技術者試験での出題例
基本情報に関する他の記事

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

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

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

2分探索とは

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

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

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

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

このように、

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

というのを探したい値が見つかるまで繰り返すのが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分探索になると分かります。