# Algoritmos e Estruturas de Dados/Árvores Rubro-Negras

Árvore rubro-negra (Red-Black tree) é uma estrutura de dados de programação criada em 1972 com o nome de árvores binárias simétricas. Como as árvores binárias comuns às rubro-negras possuem um conjunto de operações (inserção, remoção, busca), porém são geralmente mais eficientes devido ao fato da rubro-negra estar sempre balanceada. Este balanceamento se dá justamente pela característica que dá nome a árvore, que vem de um bit extra em cada nodo que determina se esta é "vermelha" ou "preta" dentro do conjunto de regras que rege a árvore. Além desde bit, cada nodo também conta com os campos dados do nodo, filho esquerdo do nodo, filho direito do nodo e pai do nodo.

## Regras da rubro-negra

Uma árvore rubro-negra estará sempre balanceada pois segue o seguinte conjunto de regras:
* cada nodo da árvore possui um valor
* a cada novo nodo inserido na árvore obedecerá o esquema de menor para o lado esquerdo e maior para o lado direito.
* a cada nodo é associado uma cor: vermelha ou preta.
* o nodo raiz é sempre preto.
* nodos vermelhos que não sejam folhas possuem apenas filhos pretos.
* todos os caminhos a partir da raiz até qualquer folha passa pelo mesmo número de nodos pretos.
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.

## Rotações

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 nodos rotacionados.

## Inserções

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 um elemento ele é sempre da cor vermelha (exceto se for o nodo raiz). A seguir a árvore analisa se o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 6.

## Remoções

Existem dois tipos de remoção em uma árvore:

### Remoção efetiva

Com as operações de rotação e alteração de cor, remove-se o nodo e estabelece-se as propriedades da árvore.

### Remoção preguiçosa

Esta remoção marca um nó como removido, mas efetivamente não o retira. Sendo desta maneira nenhuma alteração é efetuada na árvore, porém são necessários novos mecanismos de busca e inserção para que reconheçam o nó como "ausente".

## Bibliografia

* Mathworld: Red-Black Tree
* San Diego State University: CS 660: Red-Black tree notes, por Roger Whitney
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp. 273–301.

## Ligações externas
### Demos

* Red/Black Tree Demonstration, um demo interativo em Java
* Red-Black Tree Animation
* aiSee: Visualization of a Sorting Algorithm, uma animação em gif (200 Kb)
* Red-Black Tree Demonstration,um demo em Java criado por David M. Howard
* AVL Tree Applet

### Implementações

* Efficient implementation of Red-Black Trees
* RBT: A SmallEiffel Red-Black Tree Library
* libredblack: A C Red-Black Tree Library
* Red-Black Tree C Code
* Red-Black Tree Java implementation in java.util.TreeMap
* DragonFlyBSD VM subsystems utilize Red-Black trees