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