Discussão:Árvore rubro-negra
O artigo não aborda todos os casos de inserção, nos casos não triviais, onde o nó inserido não é raiz ou seu pai não é preto, leva-se em consideração que o nó tem um nó tio, o que nem sempre é verdade.
Supondo que um nó seja inserido e seja o filho de um nó que ainda não possui filhos, depois outro nó é inserido, e é colocado como filho desse último nó inserido, nessa situação a árvore esta desbalanceada e o novo nó não possui um tio. casos:
O nó possui avô e não possui tio: Nestes casos o pai do nó inserido será sempre vermelho e seu avô sempre será preto.
Caso o novo nó seja inserido como filho à esquerda e seu pai seja um filho à direita:
1: Rotação para a direita no pai do nó inserido (essa etapa é o que diferencia este caso do caso porvir); 2: O filho do nó inserido (seu pai antes da rotação) é pintado de preto; 3: Rotação para esquerda no pai do novo nó (seu avô antes da rotação).
Caso o novo nó seja filho a direita, assim como seu pai:
1: O novo nó é pintado de preto; 2: Rotação para a esquerda no avô do novo nó.
(Analogamente para os casos simétricos, apenas invertendo os lados).
COGR