令和7年度春期 応用情報技術者試験 午前 問6

正解：ウ

AI解説

AVL木は、各ノードの左右部分木の高さの差(平衡係数)が常に1以内になるよう保つ二分探索木である。要素を追加して平衡が崩れた場合は、単一回転(LL・RR)や二重回転(LR・RL)によって二分探索木の順序性を保ったまま木を再構成し、平衡を回復させる。設問の図に1と0を順に追加した結果、適切な回転処理を経て得られる木の形が選択肢ウである。 ア: 平衡条件を満たしていない、あるいは必要な回転が行われていない木の形であり、AVL木の性質を満たさないため不適切である。 イ: 回転の種類(LL/RR/LR/RL)を誤って適用した結果生じる、平衡条件または探索順序のいずれかが崩れた木の形であり不適切である。 ウ: 正しい。1と0を追加した後、適切な回転処理によって平衡が保たれた形がこの選択肢である。 エ: 回転処理が不足しているか過剰に行われており、二分探索木としての順序性またはAVL木としての平衡条件を満たさない形であり不適切である。 💡 AVL木では挿入のたびに祖先ノードの平衡係数を確認し、崩れていればLL・RR・LR・RL型のいずれかの回転で修正するという手順を押さえておく。