Arvore Binaria

1 Resumo

Árvore rubro-negra é uma árvore binária de busca, com determinadas

propriedades adicionais e um bit extra por nó. Tal bit extra registra sua

cor: VERMELHO ou PRETO, RUBRO ou NEGRA.

A restrição na coloração de cada nó é importante, pois é desta forma que é assegurado na árvore rubro-negra que nenhum caminho, seja ele dum nó qualquer ou da raiz, até uma folha, que haja um comprimento maior que duas vezes qualquer outro caminho. O que torna esta árvore aproximadamente balanceada.

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