Árvores rubro-negras

UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL

ALGORITMOS E ESTRUTURA DE DADOS II
Árvores Rubro-Negra

ERIC MACIEL CARDOSO

UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL

Árvore Rubro-Negra

Árvore Rubro-Negra
 A árvore rubro-negra tem esse nome devido a “coloração” de seus nós;

 Uma árvore rubro negra (ARN) é uma árvore binária de busca com um campo adicional que armazena se o nó é rubro ou negro;  O fato de um nó ser rubro ou negro é usado como fator de balanceamento da ARN

Árvore Rubro-Negra
 A todos os nós é associada uma cor que pode ser vermelha ou negra de tal forma que:

1. Nós externos (folhas ou nulos) são negros; 2. Todos os caminhos entre um nó e qualquer de seus nós externos descendentes percorre um número idêntico de nós negros; 3. Se um nó é vermelho (e não é a raiz), seu pai é negro; Observe que as propriedades acima asseguram que o maior caminho desde a raiz uma folha é no máximo duas vezes maior que o de o qualquer outro caminho até outra folha e portanto a árvore é aproximadamente balanceada

Árvore Rubro-Negra
 (Altura negra) A altura negra de uma árvore rubro-negra A, denotada an(A) é o número de nós negros que se encontram nos caminhos da raiz até uma folha.
18 10 3 1 5 13 22

20
16 19

27 21 24
40

12

14

17

Árvore Rubro-Negra
 Definição de um nó

Chave Ptr Esquerda

Cor(Rubro ou Negra)

Ptr Direita

Inserção em Árvores Rubro-Negra

Árvore Rubro-Negra
 Ao inserir um nó x numa posição vazia da árvore (isto é, no lugar de um nó nulo) este é pintado de vermelho.

 Isto garante a manutenção do critério (2), já que um nó vermelho não contribui para a altura negra.

p

1

p 1 x 1

Árvore Rubro-Negra
[Caso 0] Se x não tem pai ou se p, o pai de x, é negro, nada mais precisa ser feito já que o critério (3) também foi mantido; [Caso 1] Suponha agora que p é vermelho. Então, se p não tem pai, então p é a raiz da árvore e basta trocar a cor de p para negro p x p

x