応用情報技術者試験 応用情報技術者試験 令和7年度春期 午前 問6: 図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として，適切なものはどれか。

正解

ウ. 図(選択肢ウ)

正答率 51.0%（1,100人中 561人が正解）

問題の解説

AVL 木は、どの節点でも左右の部分木の高さの差が 1 以下である 2 分探索木である。1 を追加すると 2 の左の子になるが、高さの差は 1 以下に収まる。次に 0 を追加すると 1 の左の子になり、節点 2 の左の高さが 2、右が 0 と差が 2 になるので、右回転して 1 を部分木の根にする。根 5 と右部分木（7 の左に 6）は動かない。

選択肢ごとの解説

• ア根が 3 に変わり、右部分木も 5 の下に 6、その右に 7 と組み替わっている。高さの条件は満たすが、1 と 0 の追加で必要な回転は左側の一か所だけなので、この形にはならない。
• イ根が 4 に変わり、全体が組み替わっている。AVL 木の条件は満たしていても、1 と 0 の追加では根まで動かす回転は生じないので、得られる形ではない。
• ウ正しい。1 の追加では釣り合いが保たれ、0 を追加した時点で節点 2 だけが崩れる。そこを右回転して 1 を根にすると、根 5 と右の 7-6 は元のままで、左は 3 の下に 1（0 と 2）と 4 が並ぶ。
• エ左部分木は正しいが、右部分木が「6 の右に 7」に変わっている。0 と 1 の追加は左側にしか影響しないので、元の「7 の左に 6」のまま残るはずである。