データ構造とアルゴリズム-AVLツリー

二分探索木への入力がソートされた（昇順または降順）方法で来る場合はどうなりますか？このようになります-

BSTの最悪の場合のパフォーマンスは、線形探索アルゴリズム、つまりΟ（n）に最も近いことが観察されています。リアルタイムデータでは、データパターンとその頻度を予測することはできません。そのため、既存のBSTのバランスを取る必要が生じます。

彼らの発明者にちなんで名付けられました Adelson、 Velski ＆ Landis、 AVL trees高さバランス二分探索木です。AVLツリーは、左右のサブツリーの高さをチェックし、差が1以下であることを確認します。この差は、Balance Factor。

ここでは、最初のツリーのバランスが取れていて、次の2つのツリーのバランスが取れていないことがわかります。

2番目のツリーでは、の左側のサブツリー C の高さは2で、右側のサブツリーの高さは0なので、差は2です。3番目のツリーでは、の右側のサブツリーは A高さが2で、左が欠落しているため、0であり、差は再び2です。AVLツリーでは、差（バランス係数）を1のみにすることができます。

BalanceFactor = height(left-sutree) − height(right-sutree)

左右のサブツリーの高さの差が1より大きい場合、ツリーはいくつかの回転手法を使用してバランスが取られます。

AVLローテーション

バランスを取るために、AVLツリーは次の4種類のローテーションを実行できます-

• 左回転
• 右回転
• 左右回転
• 左右回転

最初の2回転は1回転で、次の2回転は2回転です。不均衡な木を作るには、少なくとも高さ2の木が必要です。この単純な木で、それらを1つずつ理解しましょう。

左回転

ツリーが不均衡になった場合、ノードが右側のサブツリーの右側のサブツリーに挿入されると、1回の左回転を実行します-

この例では、ノード AAの右側のサブツリーの右側のサブツリーにノードが挿入されると、バランスが崩れます。左回転を行うA Bの左側のサブツリー。

右回転

左側のサブツリーの左側のサブツリーにノードが挿入されると、AVLツリーが不均衡になる可能性があります。次に、ツリーを右に回転させる必要があります。

示されているように、不均衡なノードは、右回転を実行することにより、左の子の右の子になります。

左右回転

二重回転は、すでに説明したバージョンの回転の少し複雑なバージョンです。それらをよりよく理解するために、ローテーション中に実行される各アクションに注意する必要があります。まず、左右回転の実行方法を確認しましょう。左右回転は、左回転とそれに続く右回転の組み合わせです。

状態	アクション
	左側のサブツリーの右側のサブツリーにノードが挿入されました。これはC不均衡なノード。これらのシナリオにより、AVLツリーは左右に回転します。
	まず、の左サブツリーで左回転を実行します C。これはA、の左側のサブツリー B。
	ノード C はまだ不均衡ですが、現在は、左サブツリーの左サブツリーが原因です。
	木を右回転させて、 B このサブツリーの新しいルートノード。 C これで、独自の左側のサブツリーの右側のサブツリーになります。
	これで、ツリーのバランスが取れました。

左右回転

二重回転の2番目のタイプは、右左回転です。これは、右回転とそれに続く左回転の組み合わせです。

状態	アクション
	右側のサブツリーの左側のサブツリーにノードが挿入されました。これはA、バランス係数2の不平衡ノード。
	まず、右回転を行います C ノード、作成 C 独自の左側のサブツリーの右側のサブツリー B。さて、B の正しいサブツリーになります A。
	ノード A 右サブツリーの右サブツリーのためにまだ不均衡であり、左回転が必要です。
	左回転は B サブツリーの新しいルートノード。 A 右側のサブツリーの左側のサブツリーになります B。
	これで、ツリーのバランスが取れました。