レッドブラックツリーで回転後に色を変えるときに従うべきルール

Question

私はRBツリーの初心者です。私はちょうど回転の後に木の色を変えることに吊るされた。

以下の場合を検討します： - ：色の競合がために、31の挿入を生じる上記の場合34,32,56,30,31

  34 (B) 

     32 (B)  56 (B) 

    30 (R) 

     31 (R) 

挿入

指図30の親と高さの不安定性も生じる。

したがって、ツリー32,30,31では、AVLツリーで行うのと同じように、左右回転を行います。

この回転までは、私にとってはうまくいくようです。

しかし、回転した後、木のようななり

は、だからここ

  34 (B) 

     31 (R)  56 (B) 

    30 (R)  32 (B) 

、赤、赤の競合が31と30で発生し、また、左側のサブツリーの黒さが影響を受けてしまいました。

この色付けと黒さの問題を解決するためには、式/条件のステップは何ですか？

ありがとうございます。 RED BLACKツリーにキーを挿入しながら

Answer 1

不変量を念頭に置くべきである：

【選択ルートは常に黒です。

。2つの赤いノードは連続することはできません。

。すべてのルートからヌルパスにアクセスするブラックノードの数は同じでなければなりません。 （

のインサート（34）

34(B) 

のインサート（32）

34(B) 
/
    32(R) 

挿入：

心の中で上記の点を維持、私たちは挿入をやらせます56）

34(B) 
/ \ 
    32(R) 56(R) 

インサート（30）

34(B) 
/ \ 
32(R) 56(R) 
/
30(R) 

不変2の違反。

これを処理するには、ノード32とノード56を黒色に再塗り替えて親を赤色にします。

親を赤色にすることによって不変の違反1が発生するので、親を黒色にして、次のツリーを持っています。

34(B) 
/ \ 
32(B) 56(B) 
/
30(R) 

上記のツリーはすべての不変量を満たし、挿入を続けます。

インサート（31）

 34(B) 
    / \ 
    32(B) 56(B) 
    /
    30(R) 
     \ 
     31(R) 

不変2の違反。

この違反を処理するには、の左回転をnode 32 and node 31（これらの2つのノードに影響を与える）で実行します。

 34(B) 
    / \ 
    32(B) 56(B) 
    /
    31(R) 
    /
    30(R) 

今、私たちは今、我々がすべきnode 31とnode 30をrecolour今、私たちはnode 31 and node 34

 31(R) 
    / \ 
    30(R) 34(B) 
      / \ 
      32(B) 56(B) 

に右回転を行うnode 31 and node 32

 34(B) 
    / \ 
    31(R) 56(B) 
    /\ 
    30(R) 32(B) 

に右回転を行います白痴kとnode 32とnode 56は赤色になります。我々は、次のツリーを取得：RED BLACKツリーの

 31(B) 
    / \ 
    30(B) 34(B) 
      / \ 
      32(R) 56(R) 

私たちの最後の木を満たすすべてのプロパティをしてバランスもあります。

Answer 2

私は今、数年のカップルのためのアルゴリズムとデータ構造を教えてきたし、黒/赤の木についての私の正直なアドバイスは以下の通りです：

ローテーションルールとカラーフリップはどこから来た知っているが、それらを覚えてはいけません。

実際に赤/黒のツリーの回転を手でトレースしたり、コードをコーディングしたりする必要はほとんどありません。そのような場合は、ほとんどの人が行うことをお勧めします。これは、CLRSのコピーを開き、それらに含まれている擬似コードをコピーすることです。

私の意見では、これらのルールが最初のどこから来て、どのようにそれらを派生させたのかを理解することが重要です。これはしばしば教えられることではありませんが、赤/黒のツリーの元のルールは、赤/黒のツリーと関連するデータ構造2-3-4 treeとの間の接続を使用して導出されました。 2-3-4ツリーは赤/黒の木よりもはるかに理解しやすく、それらの間の接続が見えると、赤/黒のツリーを修正するために必要なすべての回転と色のフリップを実際に再現することができます - と - 飛ぶとあまりにも困難なしに。私はa set of lecture slides outlining the connection between these data structures and how to use itをまとめました。興味があれば、これは赤/黒の木の仕組みを理解するのに最適な方法かもしれません。