応用情報技術者 試験情報＆徹底解説

AVL木は、2分探索木の特徴に加え、どの節（ノードともいう）についても「左部分木と右部分木の高さの差が1以下」という条件を満たす平衡な木構造です。木の高さを一定に保つ自己平衡性をもつため、木の偏りが生じる通常の2分探索木と比べて、探索回数を安定させることができます。

AVL木が満たすべき条件は以下のとおりです。

1. 各節から出る枝の数は最大で2
2. 各節が持つデータは、その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい
3. 各節の左部分木と右部分木の高さの差が1以下

まず要素1を追加します。要素1は上記②の性質により、要素2の左部分木として配置されます。この時点では、どの節においても左部分木と右部分木の高さの差は1以下に保たれています。次に要素0を追加します。要素0は上記②の性質により、要素1の左部分木として配置されます。0の追加により、要素2、3、5において左右の部分木の高さの差が2となり、AVL木の平衡条件に反する状態となります。0のように平衡条件を満たさないノードが存在する場合、AVL木では平衡状態を保つように回転操作が行われます。回転とは、バランスが崩れる原因となっている部分木の1つのノードを上にし、別のノードを下にすることで順序を維持したまま再構成する操作です。回転は葉に近い要素から順に行われるため、0-1-2の部分木がその対象となり、1を節点とし、0が左部分木、2が右部分木となるように再構成されます（右回転）。これにより、高さの差が1以下を満たします。したがって「ウ」が正解です。