応用情報技術者試験 令和7年春 午前問6 解説付き過去問

この問題は、二分探索木に2つの要素「1」と「0」を順に挿入し、挿入後の構造がAVL木（自己平衡二分探索木）の条件を満たすかを判断する問題です。

1. 二分探索木への要素の追加
   初期状態では、図にあるように「2」を根、「3」を右子とする二分探索木が存在しています。
   ここに1を追加すると、1は2より小さいため、2の左子になります。さらに0を追加すると、0は2より小さく、1よりも小さいため、1の左子として配置されます。
   この結果、左側部分木が「2→1→0」という直線構造になります。
   
   
2. AVL木の平衡条件の確認と回転操作
   この状態では、ノード2において左部分木の高さは2、右部分木の高さは1であり、高さの差は1なのでAVL木の条件（差が1以内）を満たしているようにも見えます。
   しかし、0の追加によって、部分木のバランスが崩れており、AVL木ではこのような「左・左」構造が発生した場合には右回転が必要になります。
   具体的には、ノード2を中心とした右回転を行うことで、ノード1が根となり、0がその左子、2が右子となる構造に変化します。ノード3は引き続きノード2の右子となります。
   
   
3. 正しいAVL木の構造
   このようにして回転後のAVL木は、ノード1を根に持ち、左に0、右に2、そのさらに右に3を持つバランスのとれた構造となります。すべてのノードにおいて左右部分木の高さ差は1以内となり、AVL木の条件を満たします。
   
   

したがって、1と0を追加した後に適切な回転処理が行われたAVL木は、ノード1が根となる構造を示す選択肢です。