Estruturas de Dados

Árvore de Busca Binária Balanceada: Rubro Negra

Glasielly Demori Proença

Outubro de 2020

Glasielly Demori Proença Estruturas de Dados

Rubro Negra

É uma Árvore de Busca Binária (ABB) com os atributos COR e PAI.

Seu nome é devido a coloração dos seus nós; Rubro ou Negro.
A coloração é utilizada para fazer o balanceamento da árvore.

Glasielly Demori Proença Estruturas de Dados

Propriedades da Rubro-Negra (RN)

Todo nó é rubro ou negro;

A raı́z da árvore é sempre negra;
Todo nó nulo tem cor negra;
O pai de um nó rubro é sempre negro; e
Qualquer caminho de um nó até um nó nulo
tem sempre o mesmo número de nós negros.

Glasielly Demori Proença Estruturas de Dados

Rubro-Negra X AVL

Ambas apresentam complexidade logarı́tmica;

Na AVL a altura de duas subárvores irmãs diferem
no máximo em 1;
Na Rubro-Negra a altura de uma subárvore pode
ser até o dobro da altura da sua irmã.
Na AVL a diferença das alturas das subárvores
irmãs é o fator de balanceamento dos nós.
Na Rubro-Negra o fator de balanceamento é
definido pelas cores dos nós.

Glasielly Demori Proença Estruturas de Dados

Inserção na árvore Rubro-Negra

Cada novo nó inserido, por definição possui cor Rubro;

Faça uma inserção exatamente igual em uma ABB;
Após a inserção, verifique se as propriedades da Rubro-Negra ainda
se mantêm.
Lembre-se:
A raiz da árvore é sempre Negra;
Se o pai do novo nó inserido for NEGRO, todas as propriedades se
mantêm; e
Se o pai do novo nó inserido for RUBRO, rotações ou alterações de
cor precisam ser feitas.

Glasielly Demori Proença Estruturas de Dados

Caso 1: O pai e o tio do novo nó são RUBROS

Observe a inserção do número 61.

Pai e tio ficam NEGROS; e

Avô fica RUBRO.

Glasielly Demori Proença Estruturas de Dados

Caso 1: O pai e o tio do novo nó são RUBROS

Atenção!
Se o pai do avô for RUBRO, inicia novamente o processo de
verificação dos casos.
Sugestão: No caso 1, atualize seu novo nó para o avô.

Caso 1
Pai e tio ficam NEGROS;
Avô fica RUBRO; e
novo no = Avô.

Glasielly Demori Proença Estruturas de Dados

Caso 1: O pai e o tio do novo nó são RUBROS
Observe a inserção do número 97.

Glasielly Demori Proença Estruturas de Dados

Caso 2: O pai é rubro e o tio é NEGRO

Vamos analisar o caso em que o pai do novo nó é filho esquerdo. O caso
em que ele é filho direito é análogo.

Glasielly Demori Proença Estruturas de Dados

Caso 2: O pai é rubro e o tio é NEGRO

Pai do novo nó é filho esquerdo e novo nó é filho esquerdo

Pai fica NEGRO;
Avô fica RUBRO; e
Rotaciona o avô para a direita.

Observe a inserção do número 24.

Glasielly Demori Proença Estruturas de Dados

Caso 2: O pai é rubro e o tio é NEGRO

Pai do novo nó é filho esquerdo e novo nó é filho direito

Rotaciona o pai para a esquerda.
novo no = filho esquerdo do novo no;
Pai fica NEGRO;
Avô fica RUBRO; e
Rotaciona o avô para a direita.

Observe a inserção do número 40.

Glasielly Demori Proença Estruturas de Dados

Definições do Node e da AVL

Node<T>{
T info;
Node<T> esq, dir, pai;
Cor cor;

AVL<T>{
Node<T> raiz;

public boleano insere (T valor);

public Node<T> remove (T valor);
public Node<T> busca (T valor);
}

Glasielly Demori Proença Estruturas de Dados

Dicas para o algoritmo de rotações

Agora podemos acessar o pai de todos os nós, portanto não precisa

utilizar troca de valores entre o nó desbalanceado e seu filho, como
fizemos na rotação da AVL.
Não há necessidade de trocar cores durante a rotação. Isso será feito
no algoritmo de inserção.
Fique atento quando rotacionar um nó, ele pode ser raı́z da árvore
ou não.

Glasielly Demori Proença Estruturas de Dados

Balanceamento após a Inserção
void verificaBalanceamento(Node<T> novoNo){
enquanto ([Link] == RUBRO && [Link] != null && [Link] == RUBRO){
se ([Link] é filho esquerdo) {
tio é o filho direito
se ([Link] == RUBRO) {
[Link] = [Link] = NEGRO
[Link] = RUBRO
novoNo = avo
}
senao {
se (novoNo é filho direito){
rotacionaEsquerda([Link])
novoNo = [Link]
}
rotacionaDireita(avo)
[Link] = RUBRO
[Link] = NEGRO
novoNo = [Link]
}
}
senao {

//aqui voc^
e deve implementar o caso em
//que o pai do novoNo é fiho direito

}
}
[Link] = NEGRO
}
Glasielly Demori Proença Estruturas de Dados
Remoção da árvore Rubro-Negra

O procedimento para remover um nó é o mesmo utilizado na árvore

ABB;
Após a remoção, verifique se as propriedades da Rubro-Negra ainda
se mantêm.

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó RUBRO

A remoção dos nós 28, 73 ou 90 não violam as propriedades da

Rubro-Negra

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó RUBRO

A remoção de um nó com dois filhos na verdade é apenas um

substituição.
O maior da esquerda (antecessor) ou o menor da direita (sucessor) é
quem será removido de fato.

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó RUBRO

Para remover o nó 57, seu valor será substituı́do por 45, porém a cor
permanece (no caso é NEGRA).

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó NEGRO

A remoção de um nó NEGRO reduz o número de nós NEGROS em

qualquer caminho que continha o nó que foi removido.
Seja X o no NEGRO que foi removido
Seja no o nó que ocupou o lugar de X . E nesse caso no pode ser
uma folha nula (nó fantasma).
Se no for RUBRO, basta trocar sua cor para NEGRA.

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó NEGRO

Ao remover o nó 24, este será substituı́do pelo 28 que é RUBRO. Basta
trocar a cor do 28 para NEGRA. Mas e se o substituto for NEGRO?

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó NEGRO

Se o substituto for NEGRO, ele se torna um nó DUPLO NEGRO.

X Substituto Resultado
NEGRO NEGRO DUPLO NEGRO
NEGRO NULO NEGRO NULO DUPLO NEGRO
NEGRO RUBRO NEGRO
RUBRO RUBRO RUBRO
RUBRO NULO NEGRO NULO NEGRO

Glasielly Demori Proença Estruturas de Dados

Remoção de um nó NEGRO

Ao remover o nó 61, este será substituı́do por um nó NULO NEGRO
resultando em um nó NULO DUPLO NEGRO à esquerda do 70.

Glasielly Demori Proença Estruturas de Dados

Balanceamento do nó DUPLO NEGRO
Seja no DUPLAMENTE NEGRO:
Se no é raiz, troque a cor para NEGRA.
Senão, vamos olhar para o irmao e para o pai de no

Vamos analisar o caso em que no é filho esquerdo de seu pai. O caso em

que é filho direito é análogo (apenas troque esquerda por direita e
vice-versa).

Glasielly Demori Proença Estruturas de Dados

Balanceamento do nó DUPLO NEGRO

Observe o exemplo, se fôssemos remover o 61.

Glasielly Demori Proença Estruturas de Dados

irmao é RUBRO

Caso 1: irmao é RUBRO

pai fica RUBRO
irmao fica NEGRO
rotacione o pai à esquerda
Atualize o irmao
Após rotação: o no ainda é DUPLO NEGRO e novo irmao é
NEGRO ocasionando um Caso 2, Caso 3 ou Caso 4

Glasielly Demori Proença Estruturas de Dados

irmao é NEGRO

Caso 2: irmao é NEGRO e filhos do irmao são NEGROS

irmao fica RUBRO
no passa a apontar para o pai
Se o no for RUBRO, basta trocar para NEGRO
Senão, o novo no é DUPLO NEGRO e inicia uma nova verificação.

Glasielly Demori Proença Estruturas de Dados

irmao é NEGRO

Caso 3: irmao é NEGRO e filho direito dir do irmao é NEGRO

Filho esquerdo do irmao fica NEGRO
irmao fica RUBRO
rotacione o irmao à direita
Atualize o irmao
Após rotação: o no ainda é DUPLO NEGRO e novo irmao é
NEGRO ocasionando o Caso 4

Glasielly Demori Proença Estruturas de Dados

irmao é NEGRO

Caso 4: irmao é NEGRO e filho direito dir do irmao é RUBRO

irmao copia a cor do pai
pai e dir ficam NEGROS
rotacione o pai à esquerda
se a raiz for RUBRO troque para NEGRO

Glasielly Demori Proença Estruturas de Dados

Possibilidades dos CASOS
CASO 1:
Sempre ocasiona o CASO 2 ou CASO 3 ou CASO 4.
1-2, 1-3-4, 1-4.
CASO 2:
Pode ocorrer sozinho, porém as verificações propagam para o
ancestral.
CASO 3:
Sempre ocasiona o CASO 4.
3-4.
CASO 4:
Pode ocorrer sozinho; e
Após sua execução o balanceamento
está concluı́do.

Glasielly Demori Proença Estruturas de Dados

Exemplo 1: Removendo o nó 04

Glasielly Demori Proença Estruturas de Dados

Exemplo 1: Removendo o nó 04

Glasielly Demori Proença Estruturas de Dados

Exemplo 2: Removendo o nó 11

Glasielly Demori Proença Estruturas de Dados

Exemplo 2: Removendo o nó 11

Glasielly Demori Proença Estruturas de Dados

Balanceamento após Remoção
void verificaBalanceamento(No<T> no) {
enquanto (no != raiz && no é NEGRO) {
se (no é filho esquerdo) {
irmao é o filho direito
se (irmao é RUBRO) {
irmao fica NEGRO;
pai fica RUBRO;
rotacionaEsquerda(pai);
atualiza irmao
}
se (os dois filhos do irmao s~ao NEGROS) {
irmao fica RUBRO;
atualize o no para o pai;
} senao {
se (filho direito do irmao é NEGRO) {
filho esquerdo do irmao fica NEGRO
irmao fica RUBRO
rotacionaDireita(irmao);
atualiza o irmao
}
irmao fica com a mesma cor do pai
pai fica NEGRO
filho direito do irmao fica NEGRO
rotacionaEsquerda(pai);
no aponta para a raiz
}
}
senao {

//aqui voc^
e deve implementar o caso em
//que o no é fiho direito

}
}
no fica NEGRO
}

Glasielly Demori Proença Estruturas de Dados

Referências Bibliográficas

CORMEN, Thomas H. et al. Algoritmos: teoria e prática. Rio de

Janeiro, RJ: Elsevier, 2012. 926 p. ISBN 9788535236996
SZWARCFITER, Jayme Luiz. Estruturas de dados e seus algoritmos.
3. Rio de Janeiro LTC 2010 1 recurso online ISBN
978-85-216-2995-5

Glasielly Demori Proença Estruturas de Dados