Red Black Treeの挿入：挿入するとノードが赤くなるのはなぜですか？

Question

Red Black Tree Propertiesには、ノードの色を挿入するためのルールは含まれていませんが、常に赤色のノードが挿入されます。

ブラックカラーノードを挿入すると、プロパティ（4つのルールのいずれか）に違反しますか？

Answer 1

あなたは、ツリー内の1つのノードがあるとします。

5 (black) 

今ツリーに新しい黒のノードを挿入します。今すぐ

5 (black) 
    \ 
     9 (black) 

ツリー内のすべてのルートヌルパスは同じ番号を持っていることを不変左のルートからのパスには黒ノードが1つあり、ルートの右からのパスにはそれぞれ2つのブラックノードが存在するため、ブラックノードの数は壊れています。

希望すると便利です。

Answer 2

は、次の2つの質問

1）なぜ）タイトルに（挿入されたノード赤を作るを求めているように見えますか？

2）黒色で挿入すると正当なものに違反しますか？

はまた、2はいの答えは））1の自動正当であるという誤った印象の下にあるように見えます。

そうではありません！赤色のノードを挿入すると、もRBツリーのプロパティの1つに違反する可能性があります。たとえば、赤いノードを別の赤いノードの子にすると、赤いノードには黒い子しか持たないというプロパティに違反したことになります。

これを赤にする理由は、パス長のプロパティを修正するのではなく、子ノードのプロパティを修正して（親ノードと祖父母を再描画することによって）、簡単に行うことができるからです。たぶんもう一つの理由は、それは著者が思いついたことです。

黒いノードを挿入して赤を塗り直すことでツリーを修正することもできます。おそらく誰もそれについてまだ考えていないでしょう。