基本情報技術者試験 ap-2025r07h-a 午前 問6: 図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として，適切なものはどれか。

問題本文

図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として，適切なものはどれか。

選択肢

• ア.ア
• イ.イ
• ウ.ウ
• エ.エ

正解

ウ. ウ

解説

AVL 木は 2 分探索木の一種で、すべての節点で左右の部分木の高さの差が 1 以下になるよう、挿入のたびに必要に応じて回転で再平衡する木です。元の木（根 5、左 3 の子が 2 と 4、右 7 の子が 6）に 2 分探索木の規則どおり 1 を追加すると 2 の左の子になり、続いて 0 を追加すると 1 の左の子になります。この時点で節点 2 は左部分木の高さ 2・右部分木の高さ 0 と差が 2 になり不均衡なので、2・1・0 の並びに対し右回転を行うと、1 が親となり子が 0 と 2 になります。結果として根 5、その左に 3、3 の左に 1（子が 0 と 2）、3 の右に 4、5 の右に 7（左の子が 6）という形になります。これが選択肢ウで、左右の高さ差がどの節点でも 1 以下に保たれているため正解です。

選択肢ごとの解説

• ア.根が 3 になっていますが、要素 1 と 0 を追加しただけで根が 5 から 3 へ変わるような大規模な再構成は AVL の局所的な回転では起こりません。元の平衡を崩していない右部分木まで作り替えており誤りです。
• イ.根が 4 に変わっており、これも追加された不均衡（節点 2 周辺）の局所回転だけでは生じない構成です。元の木の正しい平衡部分を不要に変更しているため誤りです。
• ウ.節点 2 で生じた不均衡を 1 を中心とした右回転で解消し、1 の子が 0 と 2、その親が 3 となる正しい AVL 木です。右部分木（7 とその左の子 6）は元のまま平衡を保っており、これが正解です。
• エ.左部分木はウと同じく正しく平衡化されていますが、右部分木が 6 を根として 7 をその右の子にしており、元の木（7 の左に 6）の構成と異なります。右側は追加要素の影響を受けず変化しないはずなので誤りです。