技事録係

IT中心にエンジニアに必要な技術情報・最新動向・資格試験対策等を記録

基礎科目 令和元年度 Ⅰ-2-2

◀︎ 前へ次へ ▶︎️

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

f:id:trhnmr:20200509103009p:plain
図 二分探索木

① 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の位置が入れ替わるため一致しません。

参考情報

過去の出題

 なし

オンラインテキスト

(準備中)