AVL木

AVL木とは

AVL木（AVL tree）は、コンピュータサイエンスにおけるデータ構造の一つで、二分探索木をベースにした平衡二分探索木です。AVL木は、どのノードにおいても、左右の部分木の高さの差が常に1以下になるように維持されるという特徴を持ちます。この平衡状態を保つことで、データの検索、挿入、削除などの操作を効率的に行うことができます。

AVL木の歴史

AVL木は、1962年にソ連の数学者であるゲオルギー・アデルソン＝ヴェルスキーとエフゲニー・ランディスによって発表されました。彼らの名前の頭文字を取ってAVL木と名付けられました。これは、最初に考案された平衡二分探索木の一つです。

平衡条件と計算量

通常の二分探索木は、データの挿入順序によって木の形状が大きく変化します。最悪の場合、木が線形リストのようになり、探索の計算量がO(n)になってしまうことがあります。一方、木が完全にバランスが取れた状態（完全二分木）であれば、探索の計算量はO(log n)になります。AVL木は、常に「どのノードの左右部分木の高さの差も1以下」という平衡条件を満たすように調整されるため、探索の計算量は常にO(log n)程度に保たれます。

平衡係数

AVL木では、ノードごとに平衡係数という値が保持されます。平衡係数は、各ノードの左右部分木の高さの差を示す値です。


(平衡係数) = (左部分木の高さ) - (右部分木の高さ)


ノードの平衡係数が2以上または-2以下になった場合、木のバランスが崩れていると判断し、木の再構成（回転）を行います。平衡係数は、挿入や削除などの操作ごとに再計算されます。

AVL木の操作

AVL木は、通常の二分探索木と同じ基本的な操作（探索、挿入、削除）を行うことができますが、平衡を保つために、必要に応じて回転という操作を行います。

探索

AVL木での探索は、通常の二分探索木と同様に行われます。目的の値を持つノードを、以下の手順で探索します。

1. 根ノードに着目する。
2. 着目しているノードが存在しなければ、木に目的の値を持つノードはないので処理を終了。
3. 「着目しているノードの値」と「目的の値」を比較する。
4. 値が等しければ探索終了。
5. 「目的の値 < 着目しているノードの値」であれば、左の子ノードを新たに着目するノードとして手順2から繰り返す。
6. 「着目しているノードの値 < 目的の値」であれば、右の子ノードを新たに着目するノードとして手順2から繰り返す。

挿入

AVL木に新しいノードを挿入する手順は以下の通りです。

1. 通常の二分探索木と同様に、挿入すべき場所を探し、新しいノードを挿入します。
2. 挿入したノードの親ノードから根ノードに向かって、平衡条件を満たしているか確認します。
3. 平衡条件を満たしていないノードが見つかった場合、そのノードを基準に回転を行います。

回転には、以下の2種類があります。

単回転（1重回転）: ノードとその子ノードの間の1回の回転で平衡を回復させる操作です。
複回転（2重回転）: 単回転では平衡が回復しない場合に、2回の回転を行う操作です。具体的には、ノードとその孫ノードの間で回転を行います。


挿入後の平衡確認は、以下の条件で終了できます。
探索経路上のノードを回転した場合
探索経路上のノードの平衡係数が0になった場合

削除

AVL木からノードを削除する手順は以下の通りです。

1. 通常の二分探索木と同様に、削除するノードを探し、削除します。削除するノードが子ノードを2つ持つ場合は、そのノードの左部分木のうち最大値を持つノード、または右部分木のうち最小値を持つノードと置き換えてから削除します。
2. 削除したノードの親ノードから根ノードに向かって、平衡条件を満たしているか確認します。
3. 平衡条件を満たしていないノードが見つかった場合、そのノードを基準に回転を行います。

削除後の平衡確認は、以下の条件で終了できます。
探索経路上のノードの平衡係数が1もしくは-1になった場合

AVL木の特徴

バランス: AVL木は、常に木のバランスを保つため、探索などの操作を効率的に行うことができます。
部分木: AVL木の部分木もまた、AVL木です。
葉ノード: 子ノードを一つしか持たないノードは必ず葉ノードになります。
深さ: AVL木は各葉ノードの深さが均等とは限らず、深さの差が2以上になることもあります。
挿入・削除のコスト: 平衡を維持するための回転操作が伴うため、挿入や削除のコストは比較的高くなります。
性能: AVL木は、同じく平衡二分探索木である赤黒木に比べて、探索性能は良いですが、挿入や削除の性能は赤黒木の方が良いです。

関連項目

木構造
二分探索木
平衡二分探索木
木の回転
赤黒木
スプレー木
B木

もう一度検索