AVL木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
AVL木の例
AVL木の例

AVL木(えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree)とは、コンピュータプログラムにおいて、どのノードの左右部分木高さの差も1以下という条件を満たす2分探索木のことで、平衡2分探索木の1つである。

1つのデータを挿入、削除する度にこの条件を満たしているかどうか調べ、満たしていない場合は回転と呼ばれる操作を行うことで木をAVL木に再構成し、平衡を維持する。

AVLの名は、1962年に論文を発表したソ連の2人の数学者、ゲオルギー・アデルソン・ヴェルスキー英語版エフゲニー・ランディス英語版に由来する。

AVL木平衡条件[編集]

単純な2分探索木は、入力されるデータの順番によって木の構成が変わるため、例えばソートされたデータが順に入力されるという最悪の場合を考えると、木は線形リストと等価な構造になってしまい、木の性能を発揮できなくなる。これは木全体の高さをできるだけ小さく均等な状態、すなわち平衡な状態に近づけることで解決できるが、AVL木はどのノードの左右部分木の高さの差も1以下という条件を満たす木なので、木をAVL木に再構成することで木の性能は維持できる。

AVL木はあくまで各ノードの左右部分木の高さのバランスを保った木であり、各葉ノード深さが均等な木というわけではないので、木全体で見ると深さが最も大きい葉ノードと最も小さい葉ノードの深さの差が2以上になる場合もある。

なお、子ノードがない場合は部分木の高さを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小さくする操作だからである。これは挿入とは異なる点である。

木を回転する度に、平衡係数の更新も行う。

関連項目[編集]

外部リンク[編集]