空の2分探索木に、8、12、5、3、10、7、6の順にデータを与えたときにできる2分探索木はどれか。
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
答え エ
【解説】
8、12、5、3、10、7、6の順にデータを与えたときの2分探索木を作ると、
- 空の2分探索木に8を与える
- 12は8より大きいので、右の子になる
- 5は8より小さいので、左の子になる
- 3は8より小さく、5よりも小さいので、5の左の子になる
- 10は8より大きく、12より小さいので、12の左の子になる
- 7は8より小さく、5より大きいので、5の右の子になる
- 6は8より小さく、5より大きく、7より小さいので、7の左の子になる
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「二分探索木」について調べてみよう。
戻る
一覧へ
次へ