AVL木とは、「どのノードにおいても左右の部分木の高さの差が1以下」という条件を満たす、バランスの取れた自己平衡二分探索木です。この平衡性を保つことで、データの検索、挿入、削除といった操作が最悪の場合でも𝑂(log𝑛)という効率的な時間計算量を保証します。
AVL木の主な特徴
- 平衡性: どのノードの左右の部分木の高さの差が±1を超えないように常に保たれています。
- 自己平衡: データが追加・削除された際に、木のバランスが崩れた場合（高さの差が2以上になった場合）、回転と呼ばれる操作で木を再構成し、平衡状態を回復させます。
- 効率性: この平衡性のおかげで、データの挿入や削除、検索といった基本的な操作が最悪のケースでも
𝑂(log𝑛)で実行できることが保証されています。
- 名称の由来: 1962年にこの手法を考案した2人の数学者、ゲオルギー・アデルソン・ヴェルスキー（Georgii Adelson-Velsky）とエフゲニー・ランディス（Evgenii Landis）にちなんで名付けられました。
なぜ平衡が重要なのか
通常の二分探索木は、データの挿入順序によっては木が極端に偏り、一本道のようになり、最悪の場合、検索効率が線形リストと同等の
𝑂(𝑛)になってしまうことがあります。AVL木は、この偏りを防ぎ、常に木の高さを低く保つことで、常に高い検索パフォーマンスを維持します。
コメント