図の木構造は2分探索木である。 a〜gの値の大小関係として、適切なものはどれか。 ここで、a〜gの値は重複しないものとする。
| ア | a<b<d<e<c<f<g | イ | d<b<e<a<f<c<g | |
| ウ | d<e<f<g<b<c<a | エ | g<f<c<e<d<b<a |
答え イ
【解説】
2分探索木は左の子は親より値が小さく、右の子は親より値が大きいので、値が一番小さいのはdで、次はdの親のb、その次dの右の子のはe、その次はbの親のa、その次はf、その次はd、その次はgとなるので、
d<b<e<a<f<c<g
(イ)である。
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「2分探索木」について調べてみよう。
戻る
一覧へ
次へ