AVL木とは
AVL木は、二分探索木（Binary Search Tree, BST）の一種であり、すべてのノードにおいて左右の部分木の高さの差（平衡度）が常に1以下に保たれるという制約を持つ、自己平衡型の探索木構造のことです。
AVL木の概要と平衡化の重要性
AVL木は、1962年にAdelson-VelskyとLandisによって考案され、自己平衡型の二分探索木として初めて提案されました。その名称は、考案者である彼らのイニシャルに由来しています。
標準的な二分探索木（BST）は、データの挿入順序によっては極端に偏った形（リスト状）になる可能性があり、その場合、探索にかかる時間は最悪で O(n) （nはノードの総数）にまで悪化します。
AVL木は、この性能劣化を防ぐために設計されました。ノードの追加や削除の操作の後、必ず木の平衡性（バランス）をチェックし、崩れていた場合は回転操作によって自動的に修正する機構を備えています。これにより、木の高さは常に log2n に近い状態に保たれることが保証され、探索、挿入、削除といった主要な操作の計算量が最悪の場合でも O(logn) の効率で実行できます。
主な目的は、二分探索木の持つ探索の効率性（O(logn)）を、データの挿入や削除の順序に依存することなく、常に維持することです。
AVL木の基本構造と平衡度の定義
AVL木は、すべてのノードについて以下の厳格な制約を満たさなければなりません。
1. ノードの平衡度（Balance Factor）
AVL木における平衡度は、各ノードの左右の部分木の高さの差として定義されます。
AVL木であるためには、すべてのノード v について、その平衡度 BF(v) が以下の条件を満たす必要があります。
−1≤BF(v)≤1
2. 操作の効率
n 個のノードを持つAVL木の高さ h は、以下の対数的な範囲内に収まることが証明されています。
log2(n+1)≤h<1.44log2(n+2)
この対数的な高さが、AVL木が高速な操作を保証する根拠となります。
平衡を維持する操作：回転（Rotation）
ノードの挿入や削除によって平衡度の制約が破られた場合（平衡度が −2 または 2 になった場合）、AVL木は回転（Rotation）と呼ばれる再構築操作を実行して、木の平衡性を回復します。回転操作は、ノード間のポインタを付け替えることで、木の構造を変えずに平衡度を修正します。
回転には、主に4つの基本的なケースが存在します。
1. 単回転（Single Rotation）
ノードが一直線上に偏って追加された場合に適用されます。
- LL回転（Left-Left Case）:
- 平衡度が 2 となったノードの、左の子の左の部分木にノードが追加された場合。右回転を実行します。
- RR回転（Right-Right Case）:
- 平衡度が −2 となったノードの、右の子の右の部分木にノードが追加された場合。左回転を実行します。
2. 二重回転（Double Rotation）
ノードがジグザグ（内側）に偏って追加された場合に適用されます。
- LR回転（Left-Right Case）:
- 平衡度が 2 となったノードの、左の子の右の部分木にノードが追加された場合。左回転の後に右回転を実行します。
- RL回転（Right-Left Case）:
- 平衡度が −2 となったノードの、右の子の左の部分木にノードが追加された場合。右回転の後に左回転を実行します。
これらの回転操作は、ノードの挿入・削除操作の後、根ノードに向かって再帰的に実行され、違反ノードごとに最大2回の回転操作（二重回転）で平衡性を回復することができます。このため、挿入・削除操作全体の計算量は O(logn) に維持されます。
AVL木の利用と他の平衡木との比較
AVL木は、常に厳密な平衡性を維持するため、探索性能の安定性において優れています。
- 利用分野:
- 頻繁に参照（探索）が行われるが、挿入や削除があまり発生しない、静的な辞書やインデックス構造に適しています。
- 赤黒木（Red-Black Tree）との比較:
- AVL木は赤黒木よりも厳密な平衡性を保ちます。このため、探索速度は一般にAVL木の方がわずかに高速です。
- しかし、AVL木は平衡性を厳密に保つために、挿入・削除の際により多くの回転操作が必要になる傾向があります。
- 一方、赤黒木はより緩やかな平衡条件を持つため、挿入・削除の際のオーバーヘッドが少なく、多くのシステム（例：Javaの
TreeMap、Linuxカーネル）では、挿入・削除と探索の頻度が同程度の場合に赤黒木が好んで使用されます。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
