AVL 木への要素の追加
出典: 令和7年度 春期 応用情報技術者試験 午前 問6 (IPA)
図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として，適切なものはどれか。
- ア
- イ
- ウ
- エ
正解と解説を見る
正解: ウ
- ア: 根が 3 になっています。要素を追加しても根は 5 のままで、左右の形も合いません。
- イ: 根が 4 になっています。追加と回転で根が変わることはありません。
- ウ: 3 の左に 1 (子は 0 と 2)、右に 4 が付き、7 の左に 6 がある木で、正しい形になっています。正しい答えです。
- エ: 6 が 5 の右に付いており、2 分探索木の大小関係が崩れています (7 の左に 6 があるべきです)。
ポイント
AVL 木は、どの節点でも左右の部分木の高さの差が 1 以下になるよう保つ 2 分探索木です。
- 1 を追加すると、2 の左の子になります。この時点では全節点で高さの差は 1 以下です。
- 0 を追加すると、1 の左の子になります。すると 2 の左は高さ 2、右は 0 になり、差が 2 になって崩れます。
- 2 を根とする部分に 右回転 を行い、1 を根に、0 と 2 をその子にします。
結果は、5 の左が 3 (子は 1 と 4、1 の子は 0 と 2)、右が 7 (左の子 6) の木です。