二分探索木とは，各頂点に1つのキーが置かれた二分木であり，任意の頂点vについて次の条件を満たす。
（1）vの左部分木の頂点に置かれた全てのキーが，vのキーより小さい。
（2）vの右部分木の頂点に置かれた全てのキーが，vのキーより大きい。
以下では空の二分探索木に，8，12，5，3，10，7，6の順に相異なるキーを登録する場合を考える。最初のキー8は二分探索木の根に登録する。次のキー12は根の8より大きいので右部分木の頂点に登録する。次のキー5は根の8より小さいので左部分木の頂点に登録する。続くキー3は根の8より小さいので左部分木の頂点5に分岐して大小を比較する。比較するとキー3は5よりも小さいので，頂点5の左部分木の頂点に登録する。 以降同様に全てのキーを登録すると下図に示す二分探索木を得る。
キーの集合が同じであっても，登録するキーの順番によって二分探索木が変わることもある。下図と同じ二分探索木を与えるキーの順番として，最も適切なものはどれか。
図 二分探索木
① 8，5，7，12，3，10，6
② 8，5，7，10，3，12，6
③ 8，5，6，12，3，10，7
④ 8，5，3，10，7，12，6
⑤ 8，5，3，12，6，10，7
解答・解説
解答
①
解説
① 8，5，7，12，3，10，6
適切です。
② 8，5，7，10，3，12，6
右部分木の頂点に10が登録されるため一致しません。
③ 8，5，6，12，3，10，7
6と7の位置が入れ替わるため一致しません。
④ 8，5，3，10，7，12，6
右部分木の頂点に10が登録されるため一致しません。
⑤ 8，5，3，12，6，10，7
6と7の位置が入れ替わるため一致しません。
参考情報
過去の出題
なし
オンラインテキスト
（準備中）
