AVL ツリーからのノードの削除は、二分探索ツリーの場合と似ています。削除により AVL ツリーのバランス係数が乱される可能性があるため、AVL 性を維持するにはツリーのバランスを再調整する必要があります。この目的のために、ローテーションを実行する必要があります。回転にはL回転とR回転の2種類があります。ここでは R 回転について説明します。 L 回転はそれらの鏡像です。

削除されるノードがクリティカル ノードの左側のサブツリーに存在する場合、L 回転を適用する必要があります。そうでない場合、削除されるノードがクリティカル ノードの右側のサブツリーに存在する場合は、L 回転を適用する必要があります。 、R 回転が適用されます。

A がクリティカル ノード、B がその左側のサブツリーのルート ノードであると考えてみましょう。 A の右側のサブツリーに存在するノード X を削除する場合、次の 3 つの異なる状況が考えられます。

R0 回転 (ノード B のバランス係数は 0 )

ノード B のバランス係数が 0 で、ノード X の削除によりノード A のバランス係数が乱れた場合、R0 回転を使用してツリーを回転することでツリーのバランスが再調整されます。

クリティカル ノード A はその右側に移動され、ノード B がツリーのルートになり、T1 がその左側のサブツリーになります。サブツリー T2 と T3 は、ノード A の左右のサブツリーになります。R0 回転に含まれるプロセスを次の図に示します。

例：

次の図に示す AVL ツリーからノード 30 を削除します。

解決

この場合、ノード B のバランス係数は 0 であるため、次の図に示すように、R0 回転を使用してツリーが回転されます。ノード B(10) がルートとなり、ノード A がその右に移動します。ノード B の右の子は、ノード A の左の子になります。

Pythonの継承プログラム

R1 回転 (ノード B のバランス係数 1)

R1 ローテーションは、ノード B のバランス係数が 1 の場合に実行されます。R1 ローテーションでは、クリティカル ノード A がその右に移動され、サブツリー T2 と T3 がそれぞれその左と右の子になります。 T1 はノード B の左側のサブツリーとして配置されます。

R1 回転に関連するプロセスを次の図に示します。

例

次の図に示す AVL ツリーからノード 55 を削除します。

解決 ：

AVL ツリーから 55 を削除すると、ノード 50、つまりクリティカル ノードとなるノード A のバランス ファクターが乱されます。これは R1 回転の条件であり、ノード A がその右側に移動します (下の図を参照)。 B の右側が A の左側になります (つまり 45)。

ソリューションに含まれるプロセスを次の図に示します。

jpa と休止状態の比較

R-1 回転 (ノード B のバランス係数は -1)

R-1 回転は、ノード B のバランス係数が -1 の場合に実行されます。この場合は、LR 回転と同じように扱われます。この場合、ノード B の右の子であるノード C が、B と A をそれぞれ左と右の子とするツリーのルート ノードになります。

サブツリー T1、T2 は B の左と右のサブツリーになり、T3、T4 は A の左と右のサブツリーになります。

R-1 回転に含まれるプロセスを次の図に示します。

例

次の図に示す AVL ツリーからノード 60 を削除します。

解決：

この場合、ノード B のバランス係数は -1 です。ノード 60 を削除すると、ノード 50 のバランス係数が乱されるため、R-1 回転する必要があります。ノード C、つまり 45 は、ノード B(40) と A(50) を左右の子とするツリーのルートになります。