AVL木とは？
AVL木とは、すべての節点で、左右の部分木の高さの差が1以下になるよう維持される平衡2分探索木。挿入・削除で条件が崩れると回転（ローテーション）という操作で形を整え直す。これにより木の高さが常にlog nに抑えられ、探索の最悪計算量もO(log n)を保証できる。
えーぶいえるき
AVL木の意味
すべての節点で、左右の部分木の高さの差が1以下になるよう維持される平衡2分探索木。挿入・削除で条件が崩れると回転（ローテーション）という操作で形を整え直す。これにより木の高さが常にlog nに抑えられ、探索の最悪計算量もO(log n)を保証できる。
AVL木の具体例
10, 20, 30 をこの順に挿入すると通常の2分探索木では右へ一直線になるが、AVL木は20を新しい根とする左回転を行い、10と30が子になる高さ2の木へ整える。以後どんな順で入れても片寄らない。
AVL木は試験でどう引っ掛けられる？
平衡を保つ代償として、挿入・削除のたびに回転処理のコストがかかる。「常にAVL木が有利」ではなく、更新が多く探索が少ない用途では単純な構造が有利なこともある。
AVL木と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。