data-structures - 赤黒木挿入で赤ノードの代わりに黒ノードを追加してみませんか？

Question

赤黒木の挿入では、ツリーの黒の高さを変更しないように、常に新しいノードを赤として追加することを選択します。ブラックノードを追加するよりも、これが望ましいのはなぜですか？

Answer 1

これは赤黒木のルールによるものだと思います...

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

ツリーの下部に挿入が追加され、リーフ（黒のnil）ノードが値と2つの黒のnilの子を持つノードに置き換えられます。ルール5は、ブラックノードの数がすべてのパスで同じでなければならないことを規定しています。ブラックノードを追加すると、このルールに違反することになります。説明しようと思います。

                       B(10)
             R(5)                    B(15) 
    B(1)              B(6)       B(NIL)   B(NIL)
B(NIL) B(NIL)    B(NIL) B(NIL)

すべてのパスに3つの黒いノードがあることに気付くでしょう。15歳未満の新しいノード16をブラックノードとして挿入しようとすると（追加するノードの下に2つのブラックnilノードを追加することに注意してください）、そのパスは長くなります（4）。これは次のように正しくありません。

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     B(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)

すべてのルールを満たしておくには、赤いノードを挿入する必要があります。そうすれば、すべてのパスの黒いノードの数は同じままになります。

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     R(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)