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

【正解】ウ

二分探索木では、親より小さい値を左、大きい値を右に追加します。まず1は、5、3、2より小さいので2の左の子になります。この時点では、各節点の左右の部分木の高さの差は1以内です。次に0を追加すると、0は1よりも小さいので1の左の子になります。その結果、節点2では左側の高さが右側より2大きくなります。これは左の子の左側に追加されたLL型の不均衡なので、節点2を基準に右回転します。すると、この部分木は1を親、0を左の子、2を右の子とする形になります。ほかの部分は変化しないので、根が5、左部分木の根が3、その左が1、右が4となるウが正解です。

アの木は誤りです。根を3にするほどの回転は必要なく、最初に不均衡となった節点2での右回転だけで平衡が回復します。

イの木は誤りです。根が4になるような木全体の組替えは行われません。AVL木の挿入では、挿入経路上の不均衡な部分を局所的に回転します。

エの木は誤りです。右部分木の6と7の親子関係まで変更されていますが、0の挿入によって不均衡になるのは左部分木だけです。

【ポイント】 AVL木では、全ての節点について左右の部分木の高さの差を1以内に保ちます。 LL型は右回転、RR型は左回転で修正します。挿入値から根までの経路をたどり、最初に不均衡となる節点に注目します。