AVL木｜科目A-1（応用情報技術者） 令和7年 春期午前試験 問6
出典：令和7年春期 午前 問6
分野：アルゴリズムとプログラミング ／ データ構造
図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。
- ア：
- イ：
- ウ：
- エ：
TSUNAGARU-ADVICE
まず押さえたいこと
AVL木は、各ノードについて左部分木と右部分木の高さの差を1以内に保つ2分探索木です。要素を追加した後にバランスが崩れた場合は、回転操作によって高さを調整します。
迷ったときの判断軸
要素を追加するときは、まず通常の2分探索木と同じ規則で挿入位置を決め、その後で根方向へ戻りながら高さの差を確認します。左に偏り過ぎたのか、右に偏り過ぎたのか、さらに追加位置が外側か内側かによって、単回転か二重回転かを判断します。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、AVL木を探索性能を保つために自動で平衡化する2分探索木として理解しましょう。挿入や削除後の回転処理を追えるようになると、データ構造や探索アルゴリズムの問題にも対応しやすくなります。
2分探索木では、追加する値が現在の節の値より小さければ左側、大きければ右側へたどります。
まず1を追加します。1は5、3、2より小さいため、2の左の子として追加されます。この時点では、各節の左右の部分木の高さの差は1以下なので、回転は不要です。
次に0を追加します。0は5、3、2、1より小さいため、1の左の子として追加されます。
この結果、節2では左側に1、さらにその左側に0が連なり、左右の部分木の高さの差が2になります。AVL木の条件を満たさないため、節2を基準に右回転を行います。
右回転後は、1が部分木の根となり、0が1の左の子、2が1の右の子になります。
全体は、根が5、左部分木の根が3、その左の子が1、1の左右の子が0と2、3の右の子が4となります。右部分木は、7の左の子が6のままです。
したがって、ウが適切です。