fitness

2.3 Inserção
As operações Inserir e Remover são mais complicadas nas Árvores Rubro-Negras porque elas podem ferir alguma propriedade deste tipo de árvore.

• Como veremos, essas operações podem ser implementadas de forma bastante parecida com as respectivas operações nas Árvores Binárias de Busca, bastando apenas modificar as cores dos nós para que as propriedades de Árvores Rubro-
Negras sejam satisfeitas.

• Como a inserção e a remoção propriamente ditas já foram vistas para Árvores Binárias de Busca, veremos apenas o que é necessário para acertar as cores da árvore. Um nó é inserido sempre na cor vermelha, assim, não altera a altura negra da árvore

• Se o nodo fosse inserido na cor preta, invalidaria a propriedade 5, pois haveria um nodo preto a mais em um dos caminhos. • A operação de inserção em uma árvore Rubro-Negra começa por uma busca da posição onde o novo nodo deve ser inserido, partindo-se da raiz em direção aos nodos que possuam o valor mais próximo do qual vai ser inserido.
• Caso 1: Caso esta inserção seja feita em uma árvore vazia, basta alterar a cor do nodo para preto, satisfazendo assim a propriedade 2 • Caso 2: Ao inserir x, se o tio de x é vermelho, é necessário fazer a recoloração de a, t e p Obs1: Se o pai de a é vermelho, o rebalanceamento tem que ser feito
Novamente.

Obs2: Se a é raiz, então ele deve ser preto

• Caso 3: Suponha que o tio do elemento inserido é preto. Neste caso, para manter o critério (4) é preciso fazer rotações envolvendo a, t, p e x.
– Há 4 subcasos que correspondem às 4 rotaçõespossíveis:

• Caso 3a: Rotação à Direita

• Caso 3b: Rotação à Esquerda

• Caso 3c: Rotação Dupla Esquerda

• Pode ser visto como um caso 3a seguido do caso 3b

Caso 3d: Rotação dupla Direita

• Pode ser vistocomo um caso 3b seguido do caso 3ª

• Estado inicial da árvore