algorithm - 赤黒の場合の質問

Question

赤黒の木がどのように機能するかを理解しようとしています。写真で最初から2番目への移行を想定しています。これは問題なく取得できます。その後、教育リソースに従って、赤のGノードでローカル修正を行う必要があります. では、2 番目のステップの修正として、赤黒の特性を維持するために G を単に黒に着色するだけですか?

代替テキスト http://img683.imageshack.us/img683/4929/rb1.jpg

ありがとう

Answer 1

古典的な定義では、ルートは黒くなければならないため、そのプロパティを取得するには黒くペイントする必要があります。基本的な考え方は、赤いノードは特定の場所 (別の赤いノードの子であるなど) では禁止されているため、ノードを赤くペイントすると、チェックする必要がある潜在的な制約違反が発生するというものです。