データ構造 (全29問中20問目)

No.20

すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子を持つ要素数nの完全2分木がある。どの部分木をとっても左の子孫は親よりも小さく,右の子孫は親よりも大きいという関係が保たれている。2分木で探索する場合,ある要素を探索するときの最大比較回数のオーダはどれか。

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

設問の記述にある「完全2分木」と「どの部分木をとっても左の子孫は親よりも小さく,右の子孫は親よりも大きいという関係が保たれている」から、この木は次のような構造を持つ完全2分探索木であるとわかります。
09.gif/image-size:418×240
2分探索木では節点の値と探索値を比較し、探索値が存在する範囲を1/2ずつに狭めながら要素の探索を行います。要素数が2倍になれば探索回数が1回、4倍では2回増え、要素数が半分になれば1回減ることになるので比較回数のオーダは「log2n」になります。

※log2nは、n=2pとなる指数pの値です。例.log28=3、log2256=16
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop