AVL ツリーは 1962 年に GM アデルソン - ヴェルスキーと EM ランディスによって発明されました。このツリーは、発明者に敬意を表して AVL と名付けられました。
AVL ツリーは、高さバランスのとれた二分探索ツリーとして定義できます。各ノードは、左サブツリーの高さから右サブツリーの高さを減算することによって計算されるバランス係数に関連付けられます。
各ノードのバランス係数が -1 から 1 の間にある場合、ツリーはバランスが取れていると言われます。そうでない場合、ツリーはアンバランスになるため、バランスをとる必要があります。
バランス係数 (k) = 高さ (左 (k)) - 高さ (右 (k))
いずれかのノードのバランス係数が 1 の場合、左側のサブツリーが右側のサブツリーより 1 レベル高いことを意味します。
いずれかのノードのバランス係数が 0 の場合、左側のサブツリーと右側のサブツリーの高さが等しいことを意味します。
いずれかのノードのバランス係数が -1 の場合、左側のサブツリーが右側のサブツリーより 1 レベル低いことを意味します。
AVL ツリーを次の図に示します。各ノードに関連付けられたバランス係数が -1 から +1 の間にあることがわかります。したがって、これは AVL ツリーの例です。
複雑
| アルゴリズム | 平均的なケース | 最悪の場合 |
|---|---|---|
| 空間 | の上） | の上） |
| 検索 | o(ログn) | o(ログn) |
| 入れる | o(ログn) | o(ログn) |
| 消去 | o(ログn) | o(ログn) |
AVLツリー上の操作
AVL ツリーは二分探索ツリーでもあるため、すべての操作は二分探索ツリーで実行されるのと同じ方法で実行されます。検索とトラバースは、AVL ツリーのプロパティの違反にはつながりません。ただし、挿入と削除はこの特性に違反する可能性がある操作であるため、再検討する必要があります。
| SN | 手術 | 説明 |
|---|---|---|
| 1 | 挿入 | AVL ツリーへの挿入は、二分探索ツリーで実行されるのと同じ方法で実行されます。ただし、AVL ツリー プロパティの違反につながる可能性があるため、ツリーのバランス調整が必要になる場合があります。回転を適用することでツリーのバランスを取ることができます。 |
| 2 | 削除 | 削除も二分探索木と同様に行えます。削除によってツリーのバランスが崩れる可能性もあるため、ツリーのバランスを再調整するためにさまざまな種類の回転が使用されます。 |
なぜ AVL ツリーなのか?
AVL ツリーは、二分探索ツリーが歪まないようにすることで、その高さを制御します。高さ h の二分探索木のすべての演算にかかる時間は次のとおりです。 おお） 。ただし、次のように拡張することができます の上） BST が歪んだ場合 (つまり、最悪の場合)。この高さを log n に制限することにより、AVL ツリーは各操作に上限を課します。 O(log n) ここで、n はノードの数です。
bash の if と else
AVL 回転
AVL ツリーでの回転は、Balance Factor が 以外の場合にのみ実行されます。 -1、0、1 。回転には基本的に次の 4 種類があります。
- L L 回転: 挿入されたノードは A の左サブツリーの左サブツリーにあります。
- R R 回転 : 挿入されたノードは A の右サブツリーの右サブツリーにあります
- L R 回転 : 挿入されたノードは A の左サブツリーの右サブツリーにあります
- R L 回転 : 挿入されたノードは A の右サブツリーの左サブツリーにあります
ここで、ノード A は、バランス係数が -1、0、1 以外のノードです。
最初の 2 つの回転 LL と RR は 1 回転で、次の 2 つの回転 LR と RL は 2 回転です。木のバランスが崩れるためには、最小の高さは少なくとも 2 でなければなりません。各回転を理解しましょう
1.RR回転
ノードが A の右サブツリーの右サブツリーに挿入されたため、BST のバランスが崩れた場合、RR 回転を実行します。RR 回転は反時計回りの回転で、バランス係数 -2 を持つノードの下のエッジに適用されます。
上記の例では、ノード C が A の右サブツリーの右サブツリーに挿入されているため、ノード A のバランス係数は -2 になります。 A の下のエッジで RR 回転を実行します。
2.LL回転
ノードが C の左サブツリーの左サブツリーに挿入されたために BST がアンバランスになった場合、LL 回転を実行します。LL 回転は時計回りの回転であり、バランス係数 2 を持つノードの下のエッジに適用されます。
上記の例では、ノード A が C の左サブツリーの左サブツリーに挿入されているため、ノード C のバランス係数は 2 になります。 A の下のエッジで LL 回転を実行します。
3.LR回転
ダブルローテーションは、上ですでに説明したシングルローテーションよりも少し難しいです。 LR 回転 = RR 回転 + LL 回転。つまり、最初の RR 回転がサブツリーで実行され、次に LL 回転が完全なツリーで実行されます。完全なツリーとは、バランス係数が -1 以外である、挿入されたノードのパスからの最初のノードを意味します。 、0、または 1。
それぞれのステップを明確に理解しましょう。
| 州 | アクション |
|---|---|
 | ノード B が A の右側のサブツリーと C の左側のサブツリーに挿入されました。そのため、C はバランス係数 2 を持つ不均衡なノードになりました。このケースは L R 回転です。ここで、挿入されたノードは、A の左側のサブツリーの右側のサブツリーにあります。 C |
 | LR 回転 = RR + LL 回転であるため、A をルートとするサブツリーの RR (反時計回り) が最初に実行されます。 RRローテーションを行うことで、ノード あ 、の左側のサブツリーになりました。 B 。 |
 | RR ローテーションを実行した後、挿入されたノード A がノードの左側または左側にあるため、ノード C は依然としてアンバランスです。つまり、バランス係数 2 を持ちます。 C |
 | 次に、完全なツリー、つまりノード C で LL 時計回りの回転を実行します。 C はノード B の右側のサブツリーになり、A は B の左側のサブツリーになります |
 | 各ノードのバランス係数は -1、0、または 1 のいずれかになります。つまり、BST はバランスが取れています。 |
4.RLローテーション
すでに説明したように、二重回転は上で説明した単一回転よりも少し難しいです。 R L 回転 = LL 回転 + RR 回転、つまり、最初の LL 回転がサブツリーで実行され、次に RR 回転が完全なツリーで実行されます。完全なツリーとは、バランス係数が -1 以外である、挿入されたノードのパスからの最初のノードを意味します。 、0、または 1。
| 州 | アクション |
|---|---|
 | ノード B の左側のサブツリーに挿入されました C の右のサブツリー あ そのため、A はバランス係数 - 2 を持つ不均衡ノードになっています。このケースは RL 回転であり、次の場合です: 挿入されたノードは A の右サブツリーの左サブツリーにあります。 |
 | RL 回転 = LL 回転 + RR 回転なので、ルートをルートとするサブツリーでは LL (時計回り) になります。 C が最初に実行されます。 RRローテーションを行うことで、ノード C の正しいサブツリーになりました B 。 |
 | LL回転を実行した後、ノード あ はまだバランスが取れていません。つまり、バランス係数が -2 です。これは、右サブツリー ノード A の右サブツリーが原因です。 |
 | ここで、完全なツリー、つまりノード A に対して RR 回転 (反時計回りの回転) を実行します。 C はノード B の右側のサブツリーになり、ノード A は B の左側のサブツリーになりました。 |
 | 各ノードのバランス係数は -1、0、または 1 のいずれかになります。つまり、BST はバランスが取れています。 |
Q: 次の要素を含む AVL ツリーを構築します。
H、I、J、B、A、E、C、F、D、G、K、L
1. H、I、J を挿入します。
上記の要素を挿入すると、特に H の場合、H のバランス係数が -2 であるため、BST のバランスが崩れます。 BST は右に歪んでいるため、ノード H で RR Rotation を実行します。
結果のバランスツリーは次のようになります。
2.B、Aを挿入します
上記の要素を挿入すると、特に A の場合、H と I のバランス係数が 2 であるため、BST はアンバランスになります。最後に挿入されたノード、つまり H から最初のノードを考慮します。H からの BST は左に歪んでいるため、ノード H で LL Rotation を実行します。
結果のバランスツリーは次のようになります。
3. Eを挿入します
E を挿入すると、I のバランス係数が 2 であるため、BST はアンバランスになります。E から I に移動すると、BST が I の右サブツリーの左サブツリーに挿入されていることがわかり、ノード I で LR 回転を実行します。 LR = RR + LL回転
3 a) まずノード B で RR ローテーションを実行します。
RR ローテーション後の結果のツリーは次のとおりです。
3b) まずノード I で LL 回転を実行します。
MVC Java
LL 回転後のバランスの取れたツリーは次のようになります。
4. C、F、Dを挿入します
C、F、D を挿入すると、B と H のバランス係数が -2 であるため、BST はアンバランスになります。D から B に移動すると、B の左サブツリーの右サブツリーに挿入されていることがわかるため、次の処理を実行します。 RL ノード I の回転。RL = LL + RR 回転。
4a) まずノード E で LL 回転を実行します。
LL 回転後の結果のツリーは次のようになります。
4b) 次に、ノード B で RR ローテーションを実行します。
RR ローテーション後のバランスのとれたツリーは次のようになります。
5.Gを挿入する
G を挿入すると、H のバランス係数が 2 であるため、BST はアンバランスになります。G から H に移動すると、H の右サブツリーの左サブツリーに挿入されていることがわかるため、ノード I で LR 回転を実行します。 LR = RR + LL 回転。
5 a) まずノード C で RR ローテーションを実行します。
RR ローテーション後の結果のツリーは次のとおりです。
5 b) 次に、ノード H で LL 回転を実行します。
LL 回転後のバランスの取れたツリーは次のようになります。
6. Kを挿入します
K を挿入すると、I のバランス係数が -2 であるため、BST はアンバランスになります。 BST は I から K に右に歪んでいるため、ノード I で RR ローテーションを実行します。
mysqlカウント
RR ローテーション後のバランスのとれたツリーは次のようになります。
7.Lを挿入します
挿入時に、各ノードのバランス係数が -1、0、+1 のいずれかになるため、L ツリーのバランスは保たれています。したがって、ツリーはバランス型 AVL ツリーです。
