赤と黒のツリーのプロパティには、ノードの色を挿入するためのルールが含まれていませんが、常に赤い色のノードを挿入しています。
黒色のノードを挿入すると、プロパティに違反しますか (4 つのうちのいずれかのルール)?
3273 次
2 に答える
10
うん！ツリーに単一のノードがあるとします。
5 (black)
次に、新しい黒いノードをツリーに挿入します。
5 (black)
\
9 (black)
これで、ツリー内のすべてのルートヌルパスに同じ数のブラックノードがあるという不変条件が破られます。これは、ルート左からのパスに1つのブラックノードがあり、ルート右からのパスにそれぞれ2つあるためです。
お役に立てれば！
于 2013-03-16T16:19:26.417 に答える
4
あなたは2つの質問をしているようです
1) (タイトルに) 挿入時にノードを赤くするのはなぜですか?
2) 黒として挿入すると、プロパティに違反しますか?
また、2) に対する「はい」の回答は 1) に対する自動的な正当化であるという誤った印象を受けているようです。
それはそんなに！ノードを赤として挿入すると、RB ツリー プロパティの 1 つに違反する可能性もあります。たとえば、赤のノードを別の赤のノードの子にすると、赤のノードは黒の子のみを持つことができるというプロパティに違反したことになります。
赤くする理由は、パスの長さのプロパティを修正しようとするよりも、(回転と親/祖父母の再描画によって) 子ノードのプロパティを修正する方が「簡単」だからです。おそらく別の理由は、それが著者が思いついたものだということです。
黒のノードを挿入し、赤を再描画しないことで、ツリーを修正することも可能です。おそらく、まだ誰も考えていないのでしょう。
于 2013-03-16T17:41:19.737 に答える