Arvores Red- Black

UNIVERSIDADE DO OESTE DE SANTA CATARINA- CAMPUS DE VIDEIRA
CURSO: CIÊNCIA DA COMPUTAÇÃO -5º FASE
PROFESSOR: ANDREY KUHELKAMP
COMPONENTE CURRICULAR: ESTRUTURA DE DADOS 2

Árvores Red-Black
As Árvores red-black foram criadas Por Rudolf Bayer, em 1972 10 anos após a criação da AVL(Arvores Balanceadas), sob o nome de arvores binarias balanceadas simétricas, sendo que em 1978 Leo J. Guibas and Robert Sedgewick alterou seu nome para a nomenclatura atual as arvores Rubro-Negras (do Ingles Red-Black).
Ela é complexa, mas tem um bom pior-caso de tempo de execução para suas operações e é eficiente na prática: pode-se buscar, inserir, e remover em tempo O (log n), onde n é o número total de elementos da árvore. De maneira simplificada, uma árvore rubro-negra é uma árvore de busca binária que insere e remove de forma inteligente, para assegurar que a árvore permaneça aproximadamente balanceada.
Esse tipo de arvores possui este nome devido a coloração de seus nodos, sendo que as arvores rubro negras tem um campo a mais que as demais arvores, utilizado somente para armazenar a coloração do nodo. O fator de diferenciação da coloração de nodo, é fator fundamental na hora do balanceamento da arvore.
Propriedades
1- Cada nodo tem uma cor que é Rubro ou Negra, por convenção uma arvore não vazia ou subarvore tem a mesma cor de sua raiz, e uma vazia é uma arvore 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
Conceito
Altura negra)- A altura negra de uma árvore rubro-negra A, denotada an(A) é o número de nós negros que se encontram nos caminhos da raiz até uma folha.

Note que, pela terceira condição da definição de árvore rubro-negra, esse número é bem definido. No caso da árvore acima, a altura negra é 2. A altura de qualquer árvore rubro-negra é logarítmica no número de chaves armazenadas, A busca nas árvores rubro-negra tem complexidade