図の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分探索木
戻る
一覧へ
次へ