Arvore Rubro-Negra

Árvores Rubro-Negras

Uma árvore rubro-negra é uma árvore binária balanceada onde cada nó, além dos atributos normais dos nós de árvores binárias, tem um atributo de cor (vermelho ou preto) e um ponteiro para o nó pai.

Nas árvores rubro-negras os nós folha não são considerados importantes e por isso não contêm dados, sendo identificados apenas por um ponteiro para NULL. Em certas ocasiões todos os nós folha são representados por apenas um único nó sentinela, que é apontado por todas as referências dos nós internos a nós folhas, para economia de memória.

Árvores rubro-negras possuem as seguintes propriedades:

• Todo nó ou é vermelho ou é preto.

• A raiz é preta.

• Todas as folhas (nil) são pretas.

• Todos os filhos de nós vermelhos são pretos, não havendo dois nós vermelhos consecutivos.

• Todo caminho de um nó para alguma de suas folhas descendentes possui o mesmo número de nós pretos.

Essas regras asseguram o balanceamento da árvore tornando a altura dela a menor possível. Desta forma uma árvore rubro-negra, tendo a menor altura possível, possui um tempo de busca O(log n), onde n é o número total de nós da árvore.

Analogia com árvore B de ordem 4

Uma árvore rubro-negra tem estrutura similar a uma árvore B de ordem 4, onde cada nó pode conter de 1 até 3 valores e (consequentemente) entre 2 e 4 ponteiros para filhos. Nesta árvore B, cada nó contém apenas um valor associado ao valor de um nó negro da árvore rubro-negra, com um valor opcional antes e/ou depois dele no mesmo nó. Estes valores opcionais são equivalentes a um nós vermelhos na árvore rubro-negra. Entretanto, esta árvore B é mais geral que uma árvore rubro-negra, já que a árvore B pode ser convertida de mais de uma maneira em uma árvore rubro-negra. Se a lista de valores de um nó da árvore B contém somente 1 valor, então esse valor corresponde a um nó negro com dois filhos. Se a lista contém 3 valores, então o valor central corresponde a um nó negro e os outros dois valores correspondem a filhos vermelhos. Se a lista contém 2 valores, então podemos fazer qualquer um dos valores negro e o outro valor corresponde a seu filho vermelho.

Operações

As operações somente-leitura em uma árvore rubro-negra não necessitam nenhuma modificação daquelas usadas em uma árvore binária, porque toda árvore rubro-negra é um caso especial de uma árvore de busca binária simples. Contudo, o resultado imediato de uma inserção ou remoção pode violar as propriedades de uma árvore rubro-negra. Restaurar as propriedades rubro-negras requer um pequeno número (O(log n) ou O(1)) de modificações de cores (que na prática são muito rápidas) e não mais do que três rotações de árvore (duas para a inserção). Embora operações de inserção e remoção sejam complicadas, seus tempos permanecem O(log n).

Inserção

A cada vez que uma operação é realizada na árvore, testa-se este conjunto de propriedades e são efetuadas rotações e ajuste de cores até que a árvore satisfaça todas estas regras. Uma rotação é uma operação realizada na árvore para garantir seu balanceamento. Na rubro-negra pode ser feita a direita e a esquerda, onde são alterados os ponteiros dos nós rotacionados. Ao inserir-se um elemento em uma árvore rubro-negra, esta é comparada com os elementos e alocada em sua posição conforme a regra 2. Ao inserir-se um elemento ele é sempre da cor vermelha (exceto se for o nó raiz). A seguir a árvore analisa o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 4.

Uma inserção começa pela adição de um nó de forma semelhante a uma inserção em árvore binária, pintando-se o nó em vermelho. Diferentemente de uma árvore binária onde sempre adicionamos uma folha, na árvore rubro-negra, as folhas não contêm informação, então inserimos um nó vermelho na parte interna da árvore, com dois nós filhos pretos, no lugar de uma folha preta.

Casos de Inserção

Ocasiões que poderão ocorrer ao inserirmos um novo nó na árvore: Caso 1: O novo nó N está na raiz da árvore. Neste caso, este nó é repintado de preto para satisfazer a Propriedade 2. Como esta ação adiciona um nó preto em todos os caminhos da árvore de uma só vez, a Propriedade 5 não é violada Exemplo:

void

insercao_caso1(struct node *n){

if (n->pai == NULL)

n->cor = PRETA

}

Caso 2: O pai do novo nó P é preto. Neste caso a Propriedade 4 claramente não é invalidada. A Propriedade 5 tampouco é ameaçada pois o novo nó N tem como filhos dois nós - folha pretos, e sendo N vermelho, os caminhos passando por cada um dos seus filhos têm o mesmo número de nós pretos - da mesma forma que os caminhos que passavam pelo nó-folha preto que foi substituído por N. Por fim, neste caso, a árvore continua válida após a inserção, não sendo necessária mais alterações. Exemplo:

Void

insercao_caso2(struct

...