AVL木とは？

AVL木とは、すべての節点で、左右の部分木の高さの差が1以下になるよう維持される平衡2分探索木。挿入・削除で条件が崩れると回転（ローテーション）という操作で形を整え直す。これにより木の高さが常にlog nに抑えられ、探索の最悪計算量もO(log n)を保証できる。

えーぶいえるき

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）

AVL木の意味

すべての節点で、左右の部分木の高さの差が1以下になるよう維持される平衡2分探索木。挿入・削除で条件が崩れると回転（ローテーション）という操作で形を整え直す。これにより木の高さが常にlog nに抑えられ、探索の最悪計算量もO(log n)を保証できる。

10, 20, 30 をこの順に挿入すると通常の2分探索木では右へ一直線になるが、AVL木は20を新しい根とする左回転を行い、10と30が子になる高さ2の木へ整える。以後どんな順で入れても片寄らない。

平衡を保つ代償として、挿入・削除のたびに回転処理のコストがかかる。「常にAVL木が有利」ではなく、更新が多く探索が少ない用途では単純な構造が有利なこともある。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。