技術士の過去問
令和元年度（2019年）
基礎科目「情報・論理に関するもの」 問8

二分探索木とは、各頂点に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の左部分木の頂点に登録する。以降同様に全てのキーを登録すると下図に示す二分探索木を得る。
キーの集合が同じであっても、登録するキーの順番によって二分探索木が変わることもある。下図と同じ二分探索木を与えるキーの順番として、最も適切なものはどれか。