技術士第一次試験 基礎科目 R01

二分探索木とは、各頂点に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の左部分木の頂点に登録する。

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