最下位のレベル以外の節点には必ず左右の子が存在する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分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「二分探索木」について調べてみよう。
戻る
一覧へ
次へ