平成20年 春期 基本情報技術者 午前 問12

最下位のレベル以外の節点には必ず左右の子が存在する2分探索木から、あるデータを探索する。
節点の総数が15のとき、比較する節点の数は最大で幾つか。
ここで、探索するデータが存在するとは限らないものとする。

　ア 　3
　イ 　4
　ウ 　7
　エ 　13

答え　イ

【解説】
問題文の「最下位のレベル以外の節点には必ず左右の子が存在する2分探索木」を満足する、2分探索木を書くと

になる。(この2分木は“完全2分木”です。)
この2分探索木で探索を行うことを考えると、
(1)1との比較
(2)2(または3)との比較
(3)4(または5、6、7)との比較
(4)8(または9、10、11、12、13、14、15)との比較
と最大で4回(イ)の比較を行うことになります。

ちなみに、2分探索の計算量(オーダ)はO(log2n )です。

【キーワード】
・2分探索木

【キーワードの解説】

戻る 一覧へ 次へ