L'opération de suppression dans Red Black Tree

Question

Récemment, j'apprends l'arbre noir rouge gauche maigre. Et j'ai rouge this pour m'aider à apprendre. Cependant, je ne peux pas la signification des codes dans la supprimer opération, ils sont:

if (isRed(h.left))h = rotateRight(h); 

Je ne peux pas trouver un bon exemple pour me aider à obtenir l'utilisation de ce code.

Quelqu'un peut-il m'aider à me donner la raison pour laquelle le code devrait être là (avec un petit exemple, c'est beaucoup mieux)?

Answer 1

La page 7 du PDF contient la fonction complète. Fondamentalement ce qu'il fait, si la ligne est "rouge" (signifiant qu'il a été ajouté pour forcer l'arbre à être un LLRBT), alors faites pivoter le nœud enfant gauche à sa place.

A 
/\ 
    B C 

Si je supprime A, B je fais tourner à sa place:

B 
    \ 
     C