AVL木
AVL木（えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree）とは、コンピュータプログラムにおいて、どのノードの左右部分木の高さの差も1以下という条件を満たす2分探索木のことで、平衡2分探索木の1つである。
1つのデータを挿入、削除する度にこの条件を満たしているかどうか調べ、満たしていない場合は回転と呼ばれる操作を行うことで木を再構成し、平衡を維持する。
AVLの名は、1962年に論文を発表したソ連の2人の数学者、テンプレート:仮リンクとテンプレート:仮リンクに由来する。
AVL木平衡条件
AVL木は、どのノードの左右部分木の高さの差も1以下という条件を満たす。この条件を満たすということは、木全体の高さが小さく均一な状態、すなわち木が平衡な状態であることを意味する。
単純な2分探索木は、入力されるデータの順番によって木の構成が変わるため、例えばソートされたデータが順に入力されるという最悪の場合を考えると、木は線形リストと等価な構造になってしまい、木の性能を活かせなくなる。これは木を平衡な状態に近づければ解決するので、木をAVL木に再構成することは木の性能を維持することになる。
なお、子がない場合は部分木の高さを0と考えるため、1つの子しか持たないノードについて、その子は葉となる。
実際に平衡条件を満たすか調べるには、手がかりとして各ノードに平衡係数を持たせておく。初期値を0とし、左部分木の方が高いほど+1、右部分木の方が高いほど-1する。平衡係数が2以上または-2以下のノードが存在する時、木の再構成が必要である。木の再構成後は、平衡係数の更新も行わなければならない。
操作
AVL木の基本操作は、単純な2分探索木に対して行うものと同じだが、木の平衡が崩れた時は、木を再構成するために回転と呼ばれる操作も行う。回転は、平衡係数が2以上または-2以下のノードのうち、最も根から遠いノード、すなわち最も葉に近いノードから行う。
回転操作の詳細は「木の回転」を参照のこと。
探索
木の中から目的の値を持つノード見つけ出すのが探索である。2分探索木と同様に「左の子の値 ≤ 親の値 ≤ 右の子の値」の条件を手がかりに探索を行う。
まずルートノードに着目し、着目しているノードの値と目的の値を比較する。等しければ探索終了であるが、もし「目的の値 < 着目しているノードの値」であれば左の子を、「着目しているノードの値 < 目的の値」であれば右の子を新たに着目するノードとして、目的の値と比較するところから繰り返す。もし次に着目すべき子ノードがなければ、木に目的の値を持つノードは存在しないので、探索失敗として処理を終了する。
AVL木の探索の計算量は常にO(log N)であり、これは2分探索木の最良の計算量である。
挿入
2分探索木における挿入は、木を探索し、条件「左の子の値 ≤ 親の値 ≤ 右の子の値」を満たす枝の末端に、新たに作成したノードを繋ぐだけであるが、AVL木ではさらに、平衡条件を満たしているか調べ、満たしていない場合は回転を行う。
まず、探索しながら探索してきた経路を記憶しておく。これはスタックや再帰呼出しを用いることで実現できる。この経路上を、挿入したノードの親ノードからルートノードに向かって順に調べていき、平衡条件を満たさないノードがあった場合、そのノードと高い方の部分木のルートノードに対して回転を行う。これを単回転と呼ぶ。
ただし、1度単回転するだけでは平衡条件が満たされない場合があることに注意しなければならない。
具体的には、平衡条件を満たさないノードをPとすると、
- Pの左部分木の方が高く、かつPの左の子ノードの右部分木の方が高い場合
- Pの右部分木の方が高く、かつPの右の子ノードの左部分木の方が高い場合
である。
この場合はそれぞれ以下のように2度単回転を行うことで解決できる。これを複回転と呼ぶ。
- 回転前のPの左の子ノードをL、Lの右の子ノードをLRとすると、まずLとLRで単回転し、次にPと新たにPの左の子ノードとなったLRで単回転する
- 回転前のPの右の子ノードをR、Rの左の子ノードをRLとすると、まずRとRLで単回転し、次にPと新たにPの右の子ノードとなったRLで単回転する
木を回転したら、平衡係数の更新も行う。
AVL木の挿入における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認する必要は必ずしもなく、探索してきた経路上のどこかのノードを回転するか、探索してきた経路上に平衡係数が0のノードを見つけた時点で処理を終了できる。
なぜなら、挿入は木の高さを1大きくする操作であるのに対して、回転は木の高さを1小さくする操作だからである。また、挿入により平衡係数が0になったノードがあるということは、挿入前に高さが1小さかった方の部分木に挿入したということであるから、そのノードを根とする部分木の高さは挿入前後で変わっていないので、全てのノードが平衡条件を満たしていることがわかる。
削除
AVL木の削除は、2分探索木と同様の削除操作を行ったあと、平衡条件を満たしているか調べ、満たしていない場合は回転を行う。
まず、挿入と同様に、探索してきた経路上を、削除したノードの親ノードからルートノードに向かって順に調べていき、平衡条件を満たさないノードがあった場合、そのノードと高い方の部分木のルートノードに対して単回転、または複回転を行う。
AVL木の削除における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認しなければならない。なぜなら、削除は木の高さを1小さくする操作であるのに対して、回転も木の高さを1小さくする操作だからである。これは挿入とは異なる点である。
木を回転する度に、平衡係数の更新も行う。
