この記事では2分探索木についてIT初心者にも分かりやすく解説します。
2分探索木
- 2分探索は以下の方法でデータを探す方法。
①データを昇順(小さいもの順)に並べる。
②真ん中にある数字を見る。
③②で見た数字と探したい数字を比較する。
④探したい数字の方が小さい場合は前半の数字で②と③を行い、大きい場合は後半の数字で②と③を行う。
⑤数字が見つかるまで②~④を繰り返す。 - 2分探索木は2分探索を図で表したもの。
基本情報では2分探索木に関する問題が出題されます。是非最後までご覧ください。
データをどうやって探す?
突然ですが、下の問題をどうやって解きますか?
![](https://shikaku-dou.com/wp-content/uploads/2024/01/085ac2ffdd73a5d3516088817aa09400-e1705799648475-1024x414.jpg)
適当に開けていきますか?①から順番に開けていきますか?
実は効率良く探す方法があります。それが2分探索です。
2分探索とは
2分探索では、昇順に並んだ値からある値を探す時に、まず、中央の値と探したい値を比較し、探したい値が前半にあるか後半にあるかを明らかにする。そして検索範囲を絞り込んだら、再度、その範囲の中央の値と探したい値を比較し、探したい値がその範囲の前半にあるか後半にあるかを明らかにする。。。というのを繰り返しながら値を探します。
具体的に見てみましょう。まず中央の箱(⑤)を開けます。⑤には68が入っていたので、25は前半(①~④)にあることが分かります。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/5a13576ea1938910ad8f96f0046b3cd1-e1705800281483-1024x167.jpg)
ということで次は①~④の中央の箱、③の箱を開けます(②でもOKです)。③には19が入っていたので、①~④の後半(④)にあることが分かります。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/b39e3574324c56835acdf0039dbc6ffb-e1705800696934-1024x163.jpg)
ということで④の箱を開けてみましょう。④には25が入っていました。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/46ab0af66bc215c613e05dbdcbb53609-e1705801546988-1024x166.jpg)
このように、
- 中央の値と探したい値を比較して、前半にあるか後半にあるかを明らかにする
- 絞った探索範囲の中央の値と探したい値を比較して、絞った探索範囲の中から更に前半にあるか後半にあるかを明らかにする
- 絞った探索範囲の中央の値と探したい値を比較して、絞った探索範囲の中から更に前半にあるか後半にあるかを明らかにする
- ・・・
- ・・・
というのを探したい値が見つかるまで繰り返すのが2分探索です。
2分探索では効率良く値を探せると言いました。どれくらい効率良いかと言うと、箱が10000個あったとしても平均13回で探せるくらいです。
2分探索では効率良く値を探せるので、最初から2分探索しやすいようにデータを格納したいですよね。では、どのようにデータを格納すれば2分探索しやすくなるのか?その答えが2分探索木になります。
2分探索木とは
2分探索木とは、2分探索しやすくなるようなデータの格納方法や2分探索ってどうやるの?という方法を分かりやすく図にしたものです。
先程の箱を全て開けてみましょう。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/ff23a0f0edb64deaafe16be108684e65-e1705803016112-1024x160.jpg)
これらの数字を2分探索木に表すと下図のようになります。〇の部分を節(ノード)と言い、節と節を繋いだ線を枝(ブランチ)を言います。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/89d2684f0682a12c4a7e193cce3bf5ac-e1705806257381-1024x537.jpg)
2分探索木には上の節より大きい数字は右側の節に、小さい数字は左側の節に格納するというルールがあります。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/cadce3992232d05448a4dc461e1f4670-e1705806537796-1024x539.jpg)
2分探索木を色々な視点で見てみる
節の値を一番下に降ろして見ると……
節の値を一番下に降ろしてみましょう。すると、一番左が小さく、右に行くにつれて大きくなっていることが分かります。2分探索は値が昇順になっていなければ出来ません。その特徴を表していることが分かりますね。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/7717f646ffabe8109af59116f9b6f00c-1024x621.jpg)
箱を開ける順番
2分探索木では2分探索で開ける箱がすぐに分かります。
68は全ての値の中央にある値なので、1回目に開ける箱になります。
また、19と83はそれぞれ【3,11,19,25】の中央にある値、【69,80,83,92,98】の中央にある値なので、2回目に開ける箱になります。
このように、2分探索木で上にある節の箱から開けていけば2分探索になると分かります。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/1777eac855383e8c362baec5ed35ed3a-e1705808670701-1024x543.jpg)
基本情報技術者試験での出題例
サンプル問題問5
基本情報技術者
科目A サンプル問題問5
2分探索木になっている2分木はどれか。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/6e684c8b572fe9d5831f13cf698387c0-e1705709490808-1024x577.jpg)
正解は”イ”
イは2分探索木の特徴を持っています。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/efc9a4b1ced786fd342221d88c620ed3-e1705808997353-1024x389.jpg)
平成31年度春期問5
基本情報技術者
午前試験 平成31年度春期問5
2分探索木として適切なものはどれか。ここで,1~9の数字は,各ノード(節)の値を表す。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/382b6380d7d067697c280f32339e76c2-e1705710323827-1024x656.jpg)
正解は”イ”
イは2分探索木の特徴を持っています。
![](https://shikaku-dou.com/wp-content/uploads/2024/01/1071c24e9de128462fcac6f87c8b877b-e1705809373608-1024x536.jpg)
平成29年度春期問7
基本情報技術者
午前試験 平成29年度春期問7
顧客番号をキーとして顧客データを検索する場合,2分探索を使用するのが適しているものはどれか。
ア 顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造
イ 顧客番号に関係なく,ランダムに配置されているデータ構造
ウ 顧客番号の昇順に配置されているデータ構造
エ 顧客番号をセルに格納し,セルのアドレス順に配置されているデータ構造
正解は”ウ”
2分探索を使用するにはデータが昇順に並んでいる必要があります。よって答えはウです。
基本情報に関する他の記事
ハードウェア | ソフトウェア | システム構成 |
ネットワーク | データベース | 開発手法 | 情報セキュリティ |
開発手法に関する記事
プログラムについての記事
【基本情報】午前試験のアルゴリズムの苦手意識を克服する!
【基本情報】関数?手続?再帰的?プログラムの性質を解説!
データ構造についての記事
【基本情報】スタックとキューってなに?どこで使われている?
【基本情報】2分探索木を完全に理解する!
【基本情報】ハッシュ法を完全に理解する!過去問と一緒に解説!
開発の流れについての記事
【基本情報】アジャイルを完全に理解する!過去問と一緒に解説!
【基本情報】UMLやDFDの全てをまとめて解説!
【基本情報】モジュール結合度について分かりやすく解説!
【基本情報】オブジェクト指向で出題されることをまとめた!
【基本情報】基本情報で出題されるテスト手法の全てを解説