最下位のレベル以外の節点には必ず左右の子が存在する2分探索木から、あるデータを探索する。 節点の総数が15のとき、比較する節点の数は最大で幾つか。 ここで、探索するデータが存在するとは限らないものとする。
答え イ
【解説】 問題文の「最下位のレベル以外の節点には必ず左右の子が存在する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分探索木
戻る 一覧へ 次へ