次の2分探索木に12を追加したとき、追加された節12の位置を正しく表している図はどれか。
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
答え ウ
【解説】
節12を追加するので、まず根である節8と比較すると、節12のほうが大きいので右に行く。
次に節10と比較すると、節12のほうが大きいので右に行く。
次に節15と比較すると、節12のほうが小さいので左に行く。
次に節13と比較すると、節12のほうが小さいので左に行く。
節13に左の子はないので、節12を節13の左の子としておく。
これは、選択肢の“ウ”になる。
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「2分探索木」について調べてみよう。
戻る
一覧へ
次へ