二分探索木とは、アルゴリズムの中では比較的簡単なものですので、理解しやすいでしょう。
基本情報技術者の問題も一緒に見ながら理解を深めましょう。
二分探索木とは
二分探索木とはこのような木の根のように下に広がっていく構造のことを指します。
それぞれの呼び名
まずは二分探索木を構成しているものの呼び方を覚えましょう。
一番上の真ん中の点を「根」と呼び、丸い数字が入ったものを「点」、
点と点を結ぶ線を「辺」と呼びます。
また、左側「12」の点に注目したとき、上にある「9」を「12」の親と呼び、
下にある「13」を「12」の子と呼びます。
探索木の見方
この構造の特徴は、ある点に注目した時に右側の子はある点の数値より大きく、左側の子は小さいものが入っています。
大きいか小さいかで二分することで探索する(木の内部にある数値を見つける)のが楽になります。
探索の仕方
例えば上の木で、「13」を探索する問題とします。
まず「根」を見ます。
「根」の数値は15なので、それより小さいので左側にあることがわかります。
次に「9」をみるとそれよりも大きいので、右側の子を見ます。
「12」なのでそれよりも大きいので、また右側の子を見ます。
目的の「13」が見つかったので探索が終わります。
このように、4回比較するだけで目的の数値を見つけることができました。
問題
基本情報技術者試験ではこのような問題が出されました。
「2分探索木になっている2分木はどれか？」
一つ目から一緒に見ていきましょう。
まず根から下の子を見ていきます。
根の子は左側が小さく、右側は大きいのでここまではあっています。
次に「15」に着目すると、右側が「15」よりも大きくないので間違っていることがわかります。
同じく根から見ます。
左側に小さい値、右側に大きい値が入っているのであっています。
また根の「子」の「子」も同じくあっていますので、
これが2分探索木だとわかりましたが、他の候補も見ておきましょう。
慣れてくるとパッと見ただけで違うとわかります。
左側の「16」の子が両方とも小さい値になっているので、2分探索木ではありません。
こちらも「根」の子が両方とも小さい値になっているので、二分探索木ではありません。
まとめ
今回は二分探索木について解説しました。
アルゴリズムの中では簡単な内容になっていますので、しっかりと理解しておきましょう。
