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

AVL木とは

AVL木とは、すべてのノードにおいて左部分木と右部分木の高さの差が1以下になるように構築された2分探索木です。
要素の追加や削除によって木のバランスが崩れ、部分木の高さの差が2以上になった場合は、ノードの回転を行って平衡を保ちます。

正解の根拠

1. 要素の追加
   • 2分探索木の性質上、親ノードより小さい値は左、大きい値は右に追加されます。
   • 既存の木に要素「1」を追加し、次に「0」を追加すると、値が連続して左側に連なるため、左側の部分木が深く偏ります。
2. バランスの崩れと回転操作
   • 要素「0」を追加した時点で、特定のノードにおいて左部分木と右部分木の高さの差が「2」以上となり、AVL木の条件を満たさなくなります（LL状態と呼ばれる左側の偏り）。
   • この偏りを解消するため、木を再構築する右回転（LL回転）を行います。
   • 中央の値を持つノードを新しい親として持ち上げ、それに伴ってポインタをつなぎ変えることで、すべてのノードで左右の高さの差が1以下に保たれた正解の木（ウ）が完成します。

各選択肢の解説

• ア：要素追加後に木の回転操作が行われておらず、左部分木と右部分木の高さの差が2以上になっている部分があるため、AVL木の条件を満たしていません。
• イ：ノードの回転操作や配置が誤っており、部分木の高さのバランスが取れていない、または無関係なノードの位置が移動してしまっています。
• ウ（正解）：要素「1」と「0」を追加後、適切に右回転が行われており、2分探索木の大小関係（左の子 ＜ 親 ＜ 右の子）を維持したまま、すべてのノードで左右の高さの差が1以下に保たれています。
• エ：値の大小関係が崩れており、2分探索木としての基本的な性質を満たしていないか、不適当な回転処理が行われています。