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