平成28年 秋期 基本情報技術者 午前 問6

2分探索木になっている2分木はどれか。

 ア    イ  
 ウ    エ  


答え イ


解説
この2分探索木の条件は、節の右の子はすべて節より大きいこと、左の子は節より小さいことなので、この条件を満たすのは、
 
(イ)になります。
アは15に右の子が14と小さいので間違い、ウは16の右の子が14と小さいので間違い、エは20の右の子が19と小さいので間違いです。


キーワード
・2分探索木

キーワードの解説
  • 2分探索木
    節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
    2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
    木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。

もっと、「2分探索」について調べてみよう。

戻る 一覧へ 次へ