- Tipo de árvore balanceada.
- Operações básicas em O(log n) no pior caso, onde n = quantidade de nós.
- Inventadas por Bayer com nome de "Árvores Binárias Simétricas" em 1972, 10 anos depois da árvore AVL.
- Cada nó possui:
Uma cor, vermelho ou preto, ou é nó NIL (fictício/NULO ou sentinela).
Ponteiros para a subárvore esquerda e direita e para o nó que contém este nó.- Nenhum caminho da raiz até um dado nó será maior que duas vezes o comprimento de qualquer outro.
- Altura máxima de 2*log(n + 1), onde n = quantidade de nós.
- A raiz sempre preta.
- Toda folha (nó NIL) é considerada preta.
- Se um nó é vermelho seus nós à esquerda e à direita são pretos.
- Todos caminhos a partir da raiz até uma dada folha passam pelo mesmo número de nós pretos.
- Corolário: não pode existir dois nós vermelhos consecutivos.
- Inicialmente, ocorre a busca pela posição do novo nó, em seguida, procede-se o método de uma árvore binária qualquer.
- Após a inserção, as regras são testadas.
- Caso a árvore esteja desbalanceada, são realizadas rotações e/ou ajustes de cor para reestabelecer o balanceamento.
- O nó inserido sempre é vermelho.
- Corolário: caso a inserção seja feita numa árvore vazia, a única operação a ser realizada será a mudança de cor da raiz (de vermelho para preto).
- Inicialmente, ocorre a busca pelo nó a ser deletado, em seguida, procede-se o método de uma árvore binária qualquer.
- Caso a remoção efetivada seja em um nó vermelho, não é necessário o rebalanceamento.
- Caso contrário, significa que a quantidade de nós pretos num determinado caminho foi alterada, então é necessário testas as regras e realizar as devidas rotações e/ou ajustes de cor.