図の2分探索木に1と0の二つの要素を順に追加したAVL木として、適切なものはどれか。
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
答え ウ
【解説】
AVL木(Adelson-Velskii and Landis' tree)は、各ノードについて、左右の部分木の高さの差が1以下になるように維持された2分探索木です。
問題の2分探索木に1の要素を追加すると、1は2分探索木の中で最小の要素の2よりも小さいので、2の左の子になる。
さらの、0の要素を追加すると、0はは2分探索木の中で最小の要素の1よりも小さいので、1の左の子になるが、これだと2の親の3から見て左右の部分木の高さの差が2になってしまうので、
要素3の左の部分木について並び替えを行い
(ウ)になる。
また、これはAVL木としても条件を満たしている。
【キーワード】
・2分探索木
- 2分探索木
節の子の数が2以下になるように構成された2分木の一種で、節の左の子は節のよりも小さな節になっていて、右の子は節よりも大きな節になる。
2分探索木は節の追加のときに木の再構築を行う必要がないため、節(要素)の追加が容易であることが特徴である。また、節を削除するときも木の再構築は一部分で行える。
木の中で一番右の節が木の中の最大値で、一番左の節が最小値になる。
もっと、「2分探索木」について調べてみよう。
戻る
一覧へ
次へ