二分探索木
この用語のポイント
枝分かれして広がっていく構造だよ
1つの親に対して最大2つの子を持つよ
すべての要素で値の大小関係が「左≦自分＜右（もしくは、左＜自分≦右）」になっているよ
簡単に書くよ
二分探索木（読：ニブンタンサクギ 英：binary search tree）とは
それぞれの要素の枝分かれが2つまでしかない枝分かれして広がっていく構造（二分木）になっていて、すべての要素で値の大小関係が「左≦自分＜右（もしくは、左＜自分≦右）」になっているやつのこと
です。
詳しく書くよ
順番に見ていきましょう。
まずは予備知識として
・親
・子
・ツリー構造（木構造）
・二分木
について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。
親は「関係性を図に書いたときに上にくる方」です。
子は「関係性を図に書いたときに下にくる方」です。
例えば、そうですね。
ここにピヨ太ママがいたとしましょう。
ピヨ太ママはピヨ太君を作りました。
ピヨ太ママとピヨ太君の関係性を図で表現する場合、一般的には上にピヨ太ママを書いて下にピヨ太君を描きます。
このときのピヨ太ママが「親」です。
ピヨ太君が「子」になります。
……と、もったいぶって書きましたが、イメージは人間の親子関係と同じです。
ツリー構造（木構造）は「1つの親に対して複数の子を持つ、枝分かれして広がっていく構造」です。
上から下に広がっていく形で図を書くと、木を上下逆さまに見たような形になります。
二分木は「ツリー構造のうち、枝分かれが最大2つのもの」です。
「最大二つに分かれる木構造」だから「二分木」なんでしょうかね。
二分木を構成する要素は
１．入ってくるのがなくて、出ていくのが2つ
２．入ってくるのが1つで、出ていくのが2つ
３．入ってくるのが1つで、出ていくのが1つ
４．入ってくるのが1つで、出ていくのがない
の4つです。
１が枝分かれのスタートです。
２と３が枝分かれの途中です。
４が枝分かれの最後になります。
以上を踏まえて
すべての要素で値の大小関係が「左≦自分＜右（もしくは、左＜自分≦右）」になっている二分木
が「二分探索木」です。
例えば、そうですね。
「1」から「9」までの9つの数字が あったとしましょう。
一番上の要素が「5」でした。
このとき、左に入る可能性があるのは「1」から「4」のどれかです。
左には「5」より小さいやつが入れます。
右に入る可能性があるのは「6」から「9」のどれかです。
右には「5」より大きいやつが入れます。
今回は左に「2」が入ったとしましょう。
右には「7」が入りました。
次は「2」に注目してください。
「2」の左に入る可能性があるのは「1」だけです。
左には「2」より小さいやつが入れます。
「2」の右に入る可能性があるのは「3」か「4」です。
右には「2」より大きいやつで、かつ「2」の親である「5」より小さいやつが入れます。
今回は左に「1」を、右に「3」を入れました。
次は「7」に注目してください。
「7」の左に入る可能性があるのは「6」だけです。
左には「7」より小さいやつで、かつ「7」の親である「5」より大きいやつが入れます。
「7」の右に入る可能性があるのは「8」か「9」です。
右には「7」より大きいやつが入れます。
このようなことを繰り返して作った……とは限りませんが
すべての要素で値の大小関係が「左≦自分＜右（もしくは、左＜自分≦右）」になっている二分木
が二分探索木です。
なお、今回は値の重複は考えませんでした。
もし値が重複した場合は「左にする（左≦自分＜右）」もしくは「右にする（左＜自分≦右）」を統一しておきます。
どちらにするかの決まりは（多分）ありません。
決めの問題です。
あと注意点として、二分探索木の説明において「左の子≦親＜右の子（もしくは、左の子＜親≦右の子）」と説明されていることがあります。
これは少し話を単純化して説明されています。
実際には「左の子と、その子孫≦親＜右の子と、その子孫（もしくは、左の子と、その子孫＜親≦右の子と、その子孫）」です。
そうなっていないと値を探すときに使えません。
例えば、そうですね。
以下の二分探索木が あったとしましょう。
この中から「6」を探すとします。
まずは一番の親である「5」に行きます。
「6」は「5」より大きいですよね。
右に行きます。
右に行ったら「7」に到着しました。
「6」は「7」より小さいですよね。
左に行きます。
左に行ったら「6」に到着しました。
無事に「6」が見つかりましたね。
それでは次に、以下の二分探索木もどきを見てください。
この二分探索木もどきも、すべての要素において「左の子＜親＜右の子」は満たしています。
この二分探索木もどきを使って先ほどと同じように「6」を探してみましょう。
まずは一番の親である「5」に行きます。
「6」は「5」より大きいですよね。
右に行きます。
はい、この時点で「6」には、たどり着けなくなりましたよね。
「6」は「5」より左にあります。
ということで「左の子≦親＜右の子」のような説明を見かけたら「左の子と、その子孫≦親＜右の子と、その子孫」と読み替えてあげてください。
枝分かれした左の先にあるのは全部小さい値、枝分かれした右の先にあるのは全部大きい値です。
一言でまとめるよ
まぁ「二分探索木」って単語が出てきたら「すべての要素で値の大小関係が「左≦自分＜右（もしくは、左＜自分≦右）」になっている二分木
（それぞれの要素の枝分かれが最大2つまでのツリー構造）なんだな～」と お考えください。
おまけ
■検索してみる？
