Arvore rubro negra (redblack tree)

1. Introdução
As árvores rubro-negras (Red-Black Trees), foram inventadas em 1972, 10 anos depois das árvores AVL, por Bayer sob o nome “Árvores Binárias Simétricas”. Elas consistem em árvores binárias de busca, que se mantém balanceadas no decorrer de suas operações, possuindo algoritmos de inserção e remoção de complexidade logarítmica, relativo ao número de nós. Contudo, as árvores rubro-negras são geralmente mais utilizadas do que as árvores binárias, por terem implementações mais eficientes.
Assim como as árvores binárias tradicionais, as árvores rubro-negras possuem um conjunto básico de operações (inserção, remoção, pesquisa...). Nas árvores binárias, estas operações possuem um tempo de execução O(h) (h corresponde à altura da árvore), mas que garante um bom funcionamento apenas para árvores de pequena altura. Já as árvores rubro-negras, por estarem sempre balanceadas, conseguem garantir que o tempo de execução das mesmas operações seja O(log h) no pior caso, o que lhes garante um bom funcionamento para qualquer que seja a altura da árvore.
Outra diferença das árvores rubro-negras em relação às árvores binárias tradicionais é que estas apresentam um bit extra, que armazena a cor de cada nodo presente na árvore (vermelho ou preto). Além deste, cada nodo será composto ainda pelos seguintes campos: valor (os “dados” do nodo), fe (filho esquerdo, outro nodo), fd (filho direito, outro nodo) e pai (outro nodo).

2. Propriedades
O balanceamento das árvores rubro-negras é alcançado obedecendo-se a um conjunto de propriedades, as quais são:

1. cada nodo da árvore possui um valor;
2. o valor de um nodo é maior do que o valor de seu filho da esquerda, e menor do que o valor de seu filho da direita;
3. cada nodo possui cor vermelha ou preta;
4. nodos vermelhos que não sejam folhas possuem somente filhos pretos;
5. todos os caminhos a partir da raiz da árvore até uma de suas folhas passa obrigatoriamente pelo mesmo número de nodos pretos;
6. o nodo raiz