平成20年 春期 基本情報技術者 午前 問12
最下位のレベル以外の節点には必ず左右の子が存在する２分探索木から、あるデータを探索する。
節点の総数が１５のとき、比較する節点の数は最大で幾つか。
ここで、探索するデータが存在するとは限らないものとする。
ア ３ イ ４ ウ ７ エ １３
【キーワード】
・２分探索木
【キーワードの解説】
- ２分探索木（二分探索木）
コンピュータが扱うデータ構造の一つで、データが左と右の２つの子データを持つように並べた（整列した）ものである。
（２分探索木の例）
左の子のデータは親よりも大きい（小さい）データ、右の子のデータは親よりも小さい（大きい）データとすることで、データの探索を簡単に行えるようになる。
スポンサードリンク
２分探索木についての問題です。
『木構造』のデータについての問題は出題頻度が高いので、木構造についてはしっかりと学習しておきましょう。
出題されるのは２分木構造の探索とソート（ヒープソート）で、２分木構造のデータに新しい要素を加えたときや、データを取り出したときの木の再構築もよく出題されます。
また、ソートのときの計算量（オーダー）についても覚えておいたほうがいいです。（ちなみに、ヒープソートの計算量はＯ（ｎ ｌｏｇｎ です。））
