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

解説

正解は3。まず普通の2分探索木として追加する。1は5→3→2と下りて2の左に入る。この時点ではどの節点も左右の高さの差は1以下。次に0は5→3→2→1と下りて1の左に入る。すると節点2は左の高さ2、右の高さ0で差が2になり、平衡が崩れる。崩れたのが左の子の左側なので、節点2で右回転（LL回転）を1回行い、1を親、0と2を子にする。ほかの部分はそのまま残るので、3の木になる。

• 1、2、4の木も同じ要素をもつ平衡した探索木だが、AVL木への追加は平衡が崩れた最も低い節点で回転するだけで、根や右の部分木まで組み替えることはない。
• 1は根を3に、2は根を4に変えている。
• 4は崩れていない右部分木の7と6の関係まで入れ替えている。

根拠：AVL木の挿入と回転（LL・RR・LR・RL）。