赤い黒い木にノードを挿入するときに、おじさんが黒で親が黒であればどうでしょうか？

Question

私は叔父が黒い2つのケースがあることを知っています。しかし、すべてのケースで親は赤です。親が黒であれば違反はありません。赤い黒の木の中でこのような状況で何をしなければならないでしょうか？

Answer 1

ノードを赤色/黒色のツリーに追加すると、その親が黒色になる場合は、ノードを赤くして1日と呼びます。フィックスアップは必要ありません。赤/黒のツリーのルールを見ると、root-nullパスがすべて同じ数の黒ノードを通過するため、新しい違反は発生しません。

異なる考え方：赤/黒の木をアイソメトリまたは2-3-4ツリーと考える場合、このルールは、その中に1つのキーを持つリーフを取り、別のキーを追加することに対応します。それ以上の修正手順が必要です。