arvore rubro negra

Árvore Rubro-Negra
Oque é?
Á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.
Site: http://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/%C3%81rvores_Rubro-Negras

Propriedades
1 - Cada nó tem uma cor que é rubro ou negro. Por convenção, uma árvore não vazia (ou subárvore) tem a cor de sua raiz e uma árvore vazia é negra
2 - A raiz é negra
3 - Qualquer caminho da raiz até uma subárvore vazia tem um número igual de nós negros
4 - As subárvores de um nó rubro são sempre negras
-> Propriedade óbvia resultando da quarta condição é que num caminho da raiz até uma subárvore vazia não pode haver dois nós rubros consecutivos

Inserção
Todo nó a ser inserido por convenção é rubro (pois se fosse negro não seguiria a propriedade 3)
Se após a inserção for quebrada qualquer propriedade da ARN devem ser feitas rotações e/ou inversão de cores dos nós para que sejam satisfeitas todas as propriedades
As regras de inserção levam em consideração a cor do “tio” (o outro filho do pai do nó que recebeu o novo nó) do nó inserido

Exclusão
A remoção em árvores rubro-negras pode ser realizada também com um número logarítmico de operações
O procedimento de remoção é composto de uma etapa de remoção em árvore binária de busca seguido de uma etapa de balanceamento, caso as propriedades rubro-negras teriam sido destruídas durante a operação
Se o nó