AVL木
AVL木の挿入における平衡条件の確認は、探索してきた経路上の全てのノードが平衡条件を満たしていることを確認する必要は必ずしもなく、探索してきた経路上のどこかのノードを回転するか、探索してきた経路上に平衡係数が0のノードを見つけた時点で処理を終了できる。
なぜなら、挿入は木の高さを1大きくする操作であるのに対して、回転は木の高さを1小さくする操作であるから、これらの操作によってその部分木の高さが挿入前と等しくなるためである。また、挿入により平衡係数が0になったノードがあるということは、挿入前に高さが1小さかった方の部分木に挿入したということであるから、そのノードを根とする部分木の高さは挿入前後で変わっていないので、全てのノードが平衡条件を満たしていることがわかる。
ただし、探索してきた経路上に平衡係数が1もしくは-1のノードを見つけても処理を終了できない。
なぜなら、挿入により平衡係数が1もしくは-1になったノードがあるということは、挿入前のそのノードの左右部分木の高さは等しかったが、挿入により一方の部分木の高さが1大きくなったということであり、そのノードを根とする部分木の高さは1大きくなっているので、全てのノードが平衡条件を満たしていることを保証できないからである。
AVL木(えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree)とは、コンピュータサイエンスにおいて、「どのノードの左右部分木の高さの差も1以下」という条件を満たす二分探索木のことである。
平衡二分探索木の1つで、木に対する操作によって条件を満たさないノードが発生しても、回転と呼ばれる操作を行うだけで木をAVL木に再構成でき、平衡を維持できる。
AVL木は最初に考案された平衡二分探索木であり、その名は1962年に論文を発表したソ連の2人の数学者、ゲオルギー・アデルソン・ヴェルスキー(英語版)とエフゲニー・ランディス(英語版)に由来する。
通常の二分探索木における挿入は、条件「左の子の値 ≤ 親の値 ≤ 右の子の値」を満たす枝の末端を探索し、そこに新たに作成したノードを繋ぐだけであるが、AVL木ではさらに平衡条件を満たしているか調べ、満たしていない場合は回転を行う。
まず、挿入すべき枝の末端を探索しながら、探索してきた経路を記憶しておく。これはスタックや再帰呼出しを用いることで実現できる。挿入後、この経路上を「挿入したノードの親ノード」から「根ノード」に向かって順に調べていく。
平衡条件を満たさないノード(Pとする)があった場合に回転を行うが、ほとんどの場合、「P」と「Pの高い方の部分木の根ノード」に着目して1度回転を行えば、これらのノードとその子孫ノードは平衡条件を満たした状態になる。この回転を単回転または1重回転などと呼ぶ。
ただし、単回転では平衡条件が満たされない場合があることに注意しなければならない。具体的には、
Pの左部分木の方が高く、かつPの左の子ノードの右部分木の方が高い場合(図のLeft Right Case)
Pの右部分木の方が高く、かつPの右の子ノードの左部分木の方が高い場合(図のRight Left Case)
の2通りである。
この場合はそれぞれ以下のように2度回転を行うことで解決できる。これを複回転または2重回転などと呼ぶ。
回転前のPの左の子ノードをL、Lの右の子ノードをLRとすると、まずLとLRで回転し、次にPと新たにPの左の子ノードとなったLRで回転する
回転前のPの右の子ノードをR、Rの左の子ノードをRLとすると、まずRとRLで回転し、次にPと新たにPの右の子ノードとなったRLで回転する
このように、AVL木では部分木の構造によって単回転と複回転を使い分ける必要がある。