Data-structures-algorithms-avl-tree-algorithm

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

バイナリ検索ツリーへの入力が並べ替えられた（昇順または降順）場合はどうなりますか？ それはこのようになります-

アンバランスBST

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

発明者 Adelson 、 Velski ＆ Landis 、* AVLツリー*は、高さのバランスをとるバイナリ検索ツリーにちなんで命名されました。 AVLツリーは、左右のサブツリーの高さをチェックし、差が1以下であることを確認します。 この違いは「バランス係数」と呼ばれます。

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

不平衡AVLツリー

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

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

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

AVLローテーション

それ自体のバランスをとるために、AVLツリーは次の4種類の回転を実行することがあります-

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

最初の2つの回転はシングル回転で、次の2つの回転はダブル回転です。 不均衡なツリーを作成するには、少なくとも高さ2のツリーが必要です。 この単純なツリーを使用して、それらを1つずつ理解しましょう。

左回転

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

左回転

この例では、ノードのAの右サブツリーの右サブツリーにノードが挿入されるため、ノード A は不均衡になりました。 A をBの左サブツリーにして左回転を実行します。

右回転

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

右回転

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

左右回転

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

State	Action
Right Rotation	A node has been inserted into the right subtree of the left subtree. This makes *C *an unbalanced node. These scenarios cause AVL tree to perform left-right rotation.
Left Rotation	We first perform the left rotation on the left subtree of* C*. This makes A, the left subtree of B.
Left Rotation	Node *C *is still unbalanced, however now, it is because of the left-subtree of the left-subtree.
Right Rotation	We shall now right-rotate the tree, making* B the new root node of this subtree. C *now becomes the right subtree of its own left subtree.
Balanced Avl Tree	The tree is now balanced.

右回転

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

State	Action
Left Subtree of Right Subtree	A node has been inserted into the left subtree of the right subtree. This makes* A*, an unbalanced node with balance factor 2.
Subtree Right Rotation	First, we perform the right rotation along C *node, making C the right subtree of its own left subtree B*. Now, B *becomes the right subtree of A*.
Right Unbalanced Tree	Node *A *is still unbalanced because of the right subtree of its right subtree and requires a left rotation.
Left Rotation	A left rotation is performed by making* B the new root node of the subtree. A becomes the left subtree of its right subtree B*.
Balanced AVL Tree	The tree is now balanced.