Ciências da Computação

Estrutura de Dados I
Árvore rubro negra

Discentes: Bianca Lançoni de Oliveira Garcia

Gabriel Scarano de Oliveira
Júlia Rodrigues Marques do Nascimento
Lucas Furriel Rodrigues
Pedro Benedicto de Melo Cardana

Docente:: Prof. Wallace Correa de Oliveira Casaca

São José do Rio Preto-SP

Junho de 2023
 Sumário
1 Definição de Árvore Binária de Busca 2

2 Definição de Árvore Rubro Negra 2

2.1 Propriedades da árvore Rubro Negra: . . . . . . . . . . . . . . . . . . . . . 2
2.2 Breve histórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Operação de Busca na Árvore Rubro Negra 3

4 Operação de Inserção na Árvore Rubro Negra 3

5 Operação de Remoção na Árvore Rubro Negra 4

6 Complexidade das operações 5

7 Principais aplicações 5

8 Conclusão 5

9 Bibliografia do trabalho 6
1 Definição de Árvore Binária de Busca
Árvore é um Tipo Abstrato de Dados, ou seja, um algoritmo que possui caracte-
rísticas e operações específicas, definindo assim sua classificação. A Estrutura de Dados
denominada árvore consiste em um tipo de grafo específico em que há um único ancestral
comum a todos os nós, exceto ele mesmo. Esse nó especial é denominado raiz. Assim,
todos os outros nós descendem dele. Uma árvore é dita binária quando cada nó possui no
máximo dois filhos.
Esse tipo de ED é muito utilizada para organização de dados de forma hierárquica,
representando graus de parentesco entre eles.
Um tipo especial de árvore é a Árvore Binária de Busca (ABB), em que a relação
entre os elementos consiste no valor assumido por cada nó. Se um nó possui um valor
menor do que seu pai, ele é inserido à esquerda da árvore. Caso seu valor seja maior que o
do seu pai, ele é inserido à direita. Desse modo, é possível encontrar informações de forma
mais eficiente, já que pela análise de valores, o algoritmo segue para a região correta, ao
invés de percorrer a árvore toda.

2 Definição de Árvore Rubro Negra

É um tipo especial de ABB em que os nós possuem duas cores: vermelho ou preto.
Dessa maneira, existem regras de organização e balanceamento da árvore de acordo com a
coloração de cada nó, além das regras oriundas de uma ABB.

2.1 Propriedades da árvore Rubro Negra:

A primeira propriedade já foi supracitada e se refere à coloração dos seus nós, que
podem assumir apenas duas cores: vermelho ou preto.
As outras propriedades são citadas a seguir:

• 1) A raiz da árvore possui sempre coloração preta.

• 2) Todas as folhas nulas (NULL/NILL) são consideradas pretas.

• 3) Se um nó é vermelho, então seus filhos são pretos, ou seja, não pode ter dois nós
vermelhos seguidos.

• 4) Todos os caminhos da raiz a uma folha nula têm o mesmo número de nós pretos.
Essa propriedade garante que a altura negra (número de nós pretos em um caminho
da raiz a uma folha nula) seja balanceada em toda a árvore.

Desse modo, uma Árvore Rubro Negra precisa de checagem constante dos valores
dos seus nós e de suas colorações a cada operação de inserção e remoção para manter-se
balanceada.

2
2.2 Breve histórico
A criação da Árvore Rubro Negra está relacionada a uma época em que os pes-
quisadores da área da computação buscavam formas eficientes de se realizar operações,
explorando diferentes tipos de TAD. A primeira aparição desse tipo de ED foi em 1972, em
um artigo de Rudolf Bayer, professor de informática da Universidade Técnica de Munique,
sendo denominada, inicialmente, como "Árvore Binária B Simétrica".
Contudo, essa TAD difundiu-se e popularizou-se apenas a partir do ano seguinte,
em 1978, com um estudo publicado por Leonidas J. Guibas e Robert Sedgewik, que a
denominaram "Árvore Rubro Negra"por conta das cores assumidas pelos seus nós.
A notoriedade desse algoritmo na época foi por conta da sua solução de balan-
ceamento, que é particularmente útil em situações em que a eficiência na manipulação
de grandes conjuntos de dados é essencial. Além disso, inspirou muitos algoritmos de
organização de dados em grafos que surgiram posteriormente.

3 Operação de Busca na Árvore Rubro Negra

A operação de busca por um elemento em uma Árvore Rubro Negra é como a busca
em uma ABB comum. Primeiro, é verificado se o nó é igual ao nó raiz, caso seja, temos o
caso de menor complexidade e a operação é encerrada.
O segundo caso é aquele em que o nó possui um valor menor do que seu pai, sendo
direcionado para a esquerda até encontrar um local livre.
Por fim, se o nó tem valor maior que o do seu pai, ele é direcionado para direita da
árvore.

4 Operação de Inserção na Árvore Rubro Negra

Para a inserção, deve-se checar caso a caso e ir reorganizando os nós de acordo com
a coloração, sendo o balanceamento realizado ao longo do processo. Existem basicamente
quatro casos que devem ser analisados na inserção:

• Nó inserido é a raiz: colore de preto.

• O nó inserido (X) possui um tio vermelho (X tem um pai vermelho):

colore o avô de vermelho e o pai e tio de preto. Caso o avô for a raiz, ele é recolorido
de preto.

3
 • O nó inserido (X) é filho de um nó vermelho e seu tio é preto (caso do
triângulo): faz uma rotação simples direita com o novo nó inserido e depois um
tratamento posterior de cor é realizado (o que será feito no próximo caso).

• O nó inserido (X) é filho de um nó vermelho e seu tio é preto (caso da

linha): faz rotação simples direita e recolore, de modo que o pai do nó inserido seja
preto e seus filhos vermelhos.

Assim, a cada inserção de nó, os elementos anteriores são checados e recoloridos e

rotacionados sempre que necessário, a fim de manter o balanceamento.

5 Operação de Remoção na Árvore Rubro Negra

Na remoção, os elementos são rearranjados de acordo com as mudanças realizadas
na árvore. Primeiramente, os elementos podem ser transplantados (troca seu local na
árvore), o nó removido é desalocado e por fim, o nó é recolorido caso haja necessidade.
A verificação que é feita é se o nó removido tem ambos os filhos, apenas o filho
esquerdo ou apenas o direito, fazendo a movimentação na árvore de acordo com essa
análise. Se no fim, algumas de suas propriedades forem violadas, é realizada a coloração
para arrumar.

4
6 Complexidade das operações
A complexidade de uma ED, diz respeito ao espaço físico ocupado e/ou tempo
para realizar uma operação. Em geral, a análise das principais operações da Árvore Rubro
Negra são representadas a seguir, sendo que "n"é o número de nós da árvore:

Espaço Busca Inserção Remoção

Melhor caso O(n) O(log n) O(log n) O(log n)
Pior caso O(n) O(log n) O(log n) O(log n))

Fonte: produzido pelos autores.

7 Principais aplicações
Algumas das principais aplicações do algoritmo na área da computação são apre-
sentadas a seguir:

• Implementação de mapas e conjuntos: a árvore rubro-negra é frequentemente

utilizada como base para implementar mapas (estruturas de dados que associam
chaves a valores) e conjuntos (coleções de elementos distintos). Ela oferece operações
de modo eficiente e por isso é tão utilizada (fato relacionado à sua complexidade).
Um exemplo desse uso é no TreeSet, TAD usada em Java.

• Sistemas de banco de dados: a árvore rubro-negra pode ser usada para indexar
informações e agilizar a recuperação de dados. Ela garante um bom desempenho
mesmo com grandes volumes de dados, isso por conta de sua complexidade.

• Gerenciamento de memória: em sistemas operacionais e ambientes de programa-

ção, a árvore rubro-negra pode ser aplicada no gerenciamento de memória, sendo
usada para rastrear blocos de memória alocados e liberados, ajudando a otimizar o
uso dos recursos disponíveis.

• Sistemas de arquivos: a árvore rubro-negra também pode ser utilizada em sistemas

de arquivos para organizar e indexar informações, permitindo uma busca eficiente
de arquivos e diretórios.

• Jogos de computador: em jogos, a árvore rubro-negra pode ser empregada para

otimizar a busca em estruturas de dados, como árvores de decisão utilizadas em
inteligência artificial ou para a organização de dados relacionados a elementos do
jogo.

8 Conclusão
Mediante o supracitado, infere-se que a Árvore Rubro Negra é uma TAD eficaz para
organização de dados, sendo ainda muito utilizada atualmente para diversas aplicações na
área de ciência da computação. O conhecimento desse algoritmo é, portanto, essencial

5
para melhorar a qualidade e desempenho de códigos usados para fins de gerenciamento e
busca de elementos, por guardar as informações de um modo em que a procura é facilitada.

9 Bibliografia do trabalho
[1] T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.Introduction to Algorithms,
second edition, The MIT Press, 2005.
[2] The Algorithms. Red-Black Tree implementation in C.
Disponível em:
github.com/TheAlgorithms/C/blob/master/data_structures/binary_trees/red_black_tree.c
Acesso em: 15 jun. 2023.
[3] KAHRS, Stefan. Functional Pearls: Red-Black Trees with Types. In: Journal
of Functional Programming.
[4] CARVALHO, Marcos Amorim Rossi de. Árvores Binárias de Busca Balanceadas
Implementadas em um Ambiente Móvel. Rio de Janeiro: Universidade Federal do Rio de
Janeiro, Instituto de Matemática, 2020.