本やインターネットには AVL ローテーションの例がたくさんありますが、私が見つけたものは恣意的で、挿入と削除の 4 つのケースすべての簡単な例が含まれている場所はありませんでした。
これらは、4 種類のローテーションについて思いついた最も単純なテスト ケースです。説明を簡単にするために、ASCII 文字をキーとして使用し、テスト ケースを文字列として表現できるようにしました。たとえば、文字列「abc」は「a」を挿入し、「b」を挿入してから「c」を挿入します。
完全なテスト ケースではかなり複雑なツリーが作成されるため、2 つのテスト スイートを作成しました。1 つ目はローテーションを引き起こしますが、ローテーションされるノードのサブツリーが空のため、実際に何が起こったのかを簡単に確認できます。2 番目のスイートには、ローテーション コードを完全にテストするための空でないサブツリーがあります。
回転には 2 つの異なる命名法があるようです - 私が 2L 回転として学んだことは、一部の本では rl 回転と呼ばれ、2R 回転は lr 回転と呼ばれています。以下のテキストは 2R/2L を使用しています。
これらは、挿入の簡単なテスト ケースです。
「abc」、「c」の挿入で 1L 回転が必要になります
a b
\ / \
b == 1L ==> a c
\
c
「cba」、「a」の挿入で 1R 回転が必要になります
c b
/ / \
b == 1R ==> a c
/
a
「b」のインサートの「acb」は 2L ローテーションが必要です
a b
\ / \
c == 2L ==> a c
/
b
「b」のインサートの「cab」は 2R 回転が必要です
c b
/ / \
a == 2R ==> a c
\
b
削除用
「bcad」、「a」を削除すると、1L ローテーションが必要になります
b c
x \ / \
a c == 1L ==> b d
\
d
「cbda」、「d」を削除すると、1R ローテーションが必要になります
c b
/ x / \
b d == 1R ==> a c
/
a
「a」の削除に関する「bdac」には 2L ローテーションが必要です
b c
x \ / \
a d == 2L ==> b d
/
c
「d」の削除に関する「cadb」には 2R ローテーションが必要です
c b
/ x / \
a d == 2R ==> a c
\
b
より複雑なテスト ケースにはサブツリーがあり、ほとんどが 1 つのノードです。この記事を短くするために、挿入と削除のテスト ケースを組み合わせます。削除例は、削除文字の挿入をスキップして挿入例になります。たとえば、「cadb」の 2R 単純な削除ケースを使用すると、「d」の挿入をスキップして挿入ケース「cab」になります。この結果の 1 つは、以下の二重ローテーションのケースでは、削除するノードを挿入した後、ツリーのバランスを維持するために余分なノードを挿入する必要があることです。これにより、挿入ケースが最小ではなくなります。
「a」の削除時の「cbedfag」または「a」のスキップと「g」の挿入には、c で 1L ローテーションが必要です。
c e
/ \ / \
b e == 1R ==> c f
x / \ / \ \
a d f b d g
\
g
「g」の削除または「g」のスキップと「a」の挿入の「ecfbdga」は、e で 1R ローテーションを必要とします。
- e - c
/ \ / \
c f == 1R ==> b e
/ \ x / / \
b d g a d f
/
a
「b」の削除または「b」のスキップと「f」の挿入の「ecjadhkgilbf」では、j で 2L ローテーションが必要になり、次に e が必要になります。挿入ケースは、必要に応じて「d」の挿入をスキップできます。
- e - —- h —-
/ \ / \
c j - e- j
/ \ / \ == 2L ==> / \ / \
a d h k c g i k
x / \ \ / \ / \
b g i l a d f l
/
f
「j」の削除または「j」のスキップと「g」の挿入の「hckbeiladfjg」には、c で 2R 回転が必要であり、次に b. 挿入ケースは、オプションで「l」の挿入をスキップできます</p>
- h - - e -
/ \ / \
c k c - h -
/ \ / \ == 2R ==> / \ / \
b e i l b d f k
/ / \ x / \ / \
a d f j a g i l
\
g
質問の方法 1 と 2 を使用して、ツリーが必要に応じて再調整されていることを確認します (つまり、ツリーがまだ整然としてバランスが取れていることを確認します)。本当に確実にしたい場合は、視覚的なテスト ケースを変換して、最終的なツリーの深さとバランスの値のリストを含め、順不同のトラバーサル中に検証します。