AVL木とは何ですか？

各ノードの左右部分木の高さの差が1以内に保たれる自己平衡二分探索木。最初に発明された平衡木。

AVL木のポイントは？

各ノードの左右部分木の高さ差（平衡係数）が-1、0、1のいずれか。挿入・削除・検索が最悪O(log n)。赤黒木より厳密にバランスされるため検索が高速。挿入・削除時の回転操作が赤黒木より多い

【えーぶいえるぎ】

💡 「左右の高さ差1以内」を厳密に守る平衡木

📌 このページのポイント

AVL木の回転による平衡化イメージ

ひよこ

赤黒木との使い分けは？

ペンギン先生

AVL木は木の高さが厳密に最小限だから検索が速い。赤黒木は挿入・削除時の回転が少ないから更新が速い。読み取り中心のデータ（辞書、ルックアップテーブル）ならAVL木、頻繁に更新されるデータ（メモリマップ、スケジューラ）なら赤黒木。実務ではライブラリが選択済みだから意識することは少ないよ

ひよこ

回転操作って何？

ペンギン先生

挿入や削除でバランスが崩れた時に木の構造を組み替える操作。左回転（右の子がルートに昇格）と右回転（左の子がルートに昇格）の2種類。AVL木では単回転（LL/RR）と二重回転（LR/RL）の4パターン。挿入時は最大2回、削除時は最大O(log n)回の回転が必要になるんだよ

ひよこ

平衡係数って何？

ペンギン先生

各ノードの「左部分木の高さ - 右部分木の高さ」が平衡係数（Balance Factor）。AVL木では全ノードの平衡係数が-1、0、1のいずれかでなければならない。2以上や-2以下になったら回転で修復する。各ノードに高さ情報を持たせておくと効率的に計算できるよ

ひよこ

実装する機会はある？

ペンギン先生

実務ではまずない。言語の標準ライブラリや既存実装を使う。ただしアルゴリズムの面接や大学の授業ではよく出る。実装することでバランス木の本質的な仕組みを理解できるから、一度は書いてみる価値がある。理解すると赤黒木やB木の仕組みもスムーズに理解できるようになるよ

まとめ：ざっくりこれだけ覚えればOK！

「AVL木」って出てきたら「左右の高さ差を厳密に保つ平衡二分探索木」と思えればだいたいOK！

📖 おまけ：英語の意味

「AVL Tree」＝ AVL木

💬 発明者のAdelson-Velsky（アデルソン-ベリスキー）とLandis（ランディス）の頭文字。1962年発表の最初の自己平衡二分探索木だよ