Inserção na Árvore Rubro-negra

Em uma árvore AVL, usamos a rotação como uma ferramenta para fazer o balanceamento após a inserção que causou desequilíbrio. Na árvore Rubro negra, alem o do balanceamento, usa a mudança de cor. Tenta-se mudar as cores em primeiro lugar, caso não funcione, segue para a rotação.

Seja k o nó recém-inserido.

• Como no caso de um BST primeiro procurar por k; Isso nos dá o lugar onde temos de inserir k.
• Criamos um novo nó com chave k e inseri-lo neste local.
• O novo nó está colorido em vermelho.
• Como o nó inserido é colorido em vermelho, a altura preta da árvore permanece inalterada.
• No entanto, se o pai do nó inserido também é vermelho, então temos um problema de vermelho duplo.

Caso 1

• O pai do nó inserido (a) é vermelho.
• Pai de (a) deve ser preto (b)
• A outra criança de (b) é preta (c).

Caso 2

• O pai do nó inserido (a) é vermelho.
• Pai de (a) deve ser preto (b)
• A outra criança de (b) também é vermelha (c).

• O pai de b também poderia ser vermelho. Nesse caso, o problema de vermelho duplo ascende um nível.
• Repetimos esse processo no próximo nível.
• Eventualmente, poderemos colorir a raiz vermelha.
• Nesse caso, recolorimos a raiz negra. Isso aumenta a profundidade preta de cada nó externo em 1.
• Na árvore-B (2-4) isso equivale em dividir o nó raiz.

Precisamos fazer no máximo uma rotação, movendo-se para cima da árvore, mas apenas mudando a cor dos nós.