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

解説

2分探索木への挿入では，1 は 5→3→2 とたどって節点 2 の左の子になり，この時点では平衡は崩れません。次に 0 は 5→3→2→1 とたどって節点 1 の左の子になりますが，このとき節点 2 の左部分木の高さが 2，右部分木が 0 となり平衡が崩れます（LL 型）。節点 2 を右回転して 1 を部分木の根とし，その左を 0，右を 2 とすると全ての節点で高さの差が 1 以下になります。結果は，根 5，左に 3（子は 1 と 4，1 の子は 0 と 2），右に 7（左の子 6）という木です。

選択肢ごとの解説

• ア誤り。根が 3 に変わっており，回転が節点 2 ではなく上位の節点で行われた形です。元の木では根 5 の平衡は崩れていないので，根が変わることはありません。
• イ誤り。根が 4 になり 7 が 6 の子になるなど木全体を組み直した形で，AVL 木の挿入で行う局所的な回転の結果ではありません。
• ウ正しい。節点 2 での右回転によって 1 が 0 と 2 を子にもつ形になり，全ての節点で左右の部分木の高さの差が 1 以下になっています。
• エ誤り。右部分木が 6 を根として 7 を子にしており，平衡が崩れていない右部分木まで回転させてしまった形です。