LISTA DE FIGURAS 4
RESUMO 5
1 INTRODUÇÃO 6
2 ÁRVORES RUBRO-NEGRA 7
2.1 PROPRIEDADES 7
2.2 INSERÇÃO 8
2.2.1 Caso 1 8
2.2.2 Caso 2 8
2.2.3 Caso 3 9 2.2.3.1 Caso 1 9 2.2.3.2 Caso 2 10 2.2.3.3 Caso 3 10
2.2.4 Caso 4 10
2.3 REMOÇÃO 11
2.3.1 Remoção efetiva 11
2.3.2 Remoção preguiçosa 11
CONCLUSÃO 12
REFERÊNCIAS 13

LISTA DE FIGURAS
Figura 1 – “Exemplo de Árvore Rubro-Negra” 7
Figura 2 – “Inserção em árvore vazia” 8
Figura 3 – “Pai negro” 8
Figura 4 – “Pai rubro” 9
Figura 5 – “Ambos rubros” 9
Figura 6 – “Pai rubro, tio negro e filho esquerdo” 10
Figura 7 – “Pai rubro, tio negro e filho direito” 10
Figura 8 – “Raiz da árvore final” 11

RESUMO
A Árvore rubro-negra é um tipo especial de árvore de busca binária, que se mantém balanceadas no decorrer de suas operações, existindo algoritmos de inserção e remoção de complexidade logarítmica, relativo ao número de nós.
Esta estrutura de dados, utilizada em ciência da computação, que teve seu inicio em 1972, inventada por um professor emérito de informática, Rudolf Bayer, são muito utilizadas, por ter sua prática muito eficiente e também pelo diferencial de ter um bit extra, que armazena a cor de cada nodo presente na estrutura (vermelho ou preto, rubro ou negra). Além disso, cada nodo é composto ainda pelo seu valor (dados do nó), fe (filho esquerdo, outro nó), fd (filho direito, outro nó) e pai (outro nó).

Palavras-chave: Árvore rubro-negra; Estrutura de dados; Ciência da