Árvores rubro-negras

ÁRVORES RUBRO-NEGRAS
Uma árvore rubro-negra é uma árvore binária balanceada onde cada nó, além dos atributos normais dos nós de árvores binárias, tem um atributo de cor (vermelho ou preto) e um ponteiro para o nó pai.
Nas árvores rubro-negras os nós folha não são considerados importantes e por isso não contêm dados, sendo identificados apenas por um ponteiro para NULL. Em certas ocasiões todos os nós folha são representados por apenas um único nó sentinela, que é apontado por todas as referências dos nós internos a nós folhas, para economia de memória.
Árvores rubro-negras possuem as seguintes propriedades:
• Todo nó ou é vermelho ou é preto.
• A raiz é preta.
• Todas as folhas (nil) são pretas.
• Todos os filhos de nós vermelhos são pretos, não havendo dois nós vermelhos consecutvos.
• Todo caminho de um nó para alguma de suas folhas descendentes possui o mesmo número de nós pretos.

Essas regras asseguram o balanceamento da árvore tornando a altura dela a menor possível. O maior caminho da raiz a uma folha não é maior que duas vezes o menor caminho para outra folha da árvore. Isso ocorre porque todos os caminhos até as folhas possuem o mesmo número de nós pretos e o menor caminho possui todos os nós pretos e o maior possui nós vermelhos e pretos alternados, uma vez que não é possível haver dois nós vermelhos seguidos.
Desta forma uma árvore rubro-negra, tendo a menor altura possível, possui um tempo de busca O(log n), onde n é o número total de nós da árvore.

INSERÇÃO EM UMA ÁRVORE RUBRO-NEGRA
As operações de inserção ou remoção podem gerar resultados que violem as propriedades de uma árvore rubro-negra. Por isso, depois das operações é necessário que seja realizada uma restauração das propriedades das árvores como modificações de cores de nós e rotações de árvore.
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 ponteiros dos nós