次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。
| ア | 9 | イ | 10 | ウ | 13 | エ | 14 |
答え ウ
【解説】
この2分探索木は、左の子が親よりも小さく、右の子が親よりも大きいので、削除した“12”のところには、左の子の“10”よりも大きく、右の子の“14”よりも小さい要素を入れればよいので、これを満足する要素としては“11”か“13”(ウ)である。
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「2分探索木」について調べてみよう。
戻る
一覧へ
次へ