une question de cas noir rouge

Question

J'essaie de comprendre comment les arbres noirs rouges fonctionnent, supposons la transition de la première à la seconde à l'image, je l'obtiens sans aucun problème, après cela selon les ressources pédagogiques, je dois faire une correction locale sur le nœud G rouge. Donc, en guise de solution à la 2ème étape, G colorie-t-il simplement en noir pour conserver les propriétés rouge-noir?

alt text http://img683.imageshack.us/img683/4929/rb1.jpg

grâce

Answer 1

La définition classique dit la racine doit être noir, il faudrait être peint en noir pour obtenir cette propriété. L'idée de base est que les nœuds rouges sont interdits à certains endroits (comme être un enfant d'un autre nœud rouge). Par conséquent, peindre un nœud en rouge crée une violation de contrainte potentielle qui doit être vérifiée.