Árvores Rubro Negras - Trabalho Final

Prévia do material em texto

Árvores Rubro Negras
Árvore Rubri Negras
21214780 – Gabriel Martini Guilam (gabrielguilam@gmail.com)
20961011 – Pedro Chagas Pestana (pedro.c.pestana@gmail.com)
21457512 – Murillo Stoppa Muller Fernandes (mmullerdesigner@gmial.com)
21215040 – Vitor Bretas Prata (vitorbretasprata@gmail.com)
Estrutura de Dados – Fernando Chagas
Resumo
O Modelo de implementação de balanceamento de árvores binárias, Árvores Rubro-Negras, criada por Guibas e Sedgewick, em 1972, basea-se no uso da recursividade para gerar as conexões internas dos nós e permite a rotação da árvore para atingir a sua raiz. (Sedgewick, 2014)
Todos os códigos elaborados como árvore rubro-negra possuem, por proposta, a característica de pior cenário sendo um pequeno múltiplo constante de log(n), em uma árvore de N nós. Porém, em uma árvore balanceada, pode-se atingir a melhoria de pior cenário em log(n).
O comportamento dinâmico desse método de busca permite a experimentação em prol da eficiência do algoritmo. A usabilidade da árvore rubro-negra se dá pela vastidão de aplicações de tabelas-símbolo e a criação de novas bibliotecas de software no futuro. (Sedgewick, 2014)
Palavras-chave: Árvores, implementação, árvores rubro-negras, recursividade, rotação, raiz, comportamento, eficiência, algoritmo, bibliotecas.
Introdução
A Árvore Rubro-Negra (ARB) é um algoritmo baseado na melhoria do retorno de uma busca em conjunto rico de operações, dados dinâmicos com garantia de desempenho. Atualmente, dá-se enorme importância ao tempo, logo, quanto mais veloz o algoritmo, melhor.
Nesse trabalho será explicitado o funcionamento do método de busca cujo objetivo limita-se a reduzir o tempo daquele. O algoritmo trabalha com garantia das operações básicas demorem O(log n), no pior caso, por possuir um bit extra para simplificar o retorno requerido, conhecida como Árvore Rubro-Negra.
Esse artigo apresenta códigos, tabelas e imagens para explanar o algortimo em questão. Inicia-se com um breve histórico da criação da Árvore rubro-negra, seguido de explicações, exemplificações em código e análise de complexidade do mesmo.
Desenvolvimento
Essa seção exemplifica o funcionamento da Árvore Rubro-Negra desde a sua projeção até as regras que devem ser seguidas para sua correta implementação. Contém também descritivos sobre inserção, balanceamento e remoção de nós ou folhas da árvore, bem como a análise de complexidade do algoritmo.
Histórico
Projetada em 1972, pelo professor emérito na Universidade Técnica de Munique, a Árvore rubro negra, ou Árvores B Binária Simétrica (auto-balanceada), popularizou-se nos meados de 1978 por Leonidas J. Guibas e Robert Sedgewik.
A árvore rubro-negra consiste em um tipo especial de árvore binária balanceada, para organizar dados que possam ser comparáveis. Nessas comparações, os nós folhas são irrelevantes e não contém dados, porém, necessita-se manter um ponteiro não-nulo para identificá-las. Denomina-se um nó como Nó Sentinela, a fim de economizar memória, que interpretará o papel de todos os nós folha; ou seja, todas as referências dos nós internos para os nós folha apontam para o nó sentinela. Algumas operações em árvores rubro-negras são simplificadas se os nós folha forem explicitados. Árvores rubro-negras, como todas as árvores de busca binárias, permitem travessia ordenada de elementos de maneira eficiente, ao acessar o pai de qualquer nó. O tempo de busca resulta da travessia da raiz a folha, desta forma uma árvore balanceada, tendo a menor altura possível, resulta em tempo de busca O(log n). (David Déharbe, 2015)
Figura 1 – Explificação da Árvore Rubro-Negra
	
Implementação
Define-se Árvore rubro-negra a árvore binária de busca orientada à folha. A nularidade dos nós – sem filhos – são denominados Folhas, e os outros nós são denominados Nós Internos. De acordo com a quantidade de chaves (n) presentes na árvore, pode-se definir a altura da mesma como O(log n), tornando a árvore binária balanceada. Suprindo esses requisitos, pode-se intitular a árvore de Rubro-negra. A raiz dessa é negra.
Além desses quesitos, a implementação da ARN segue quatro regras básicas:
Todo o nó é vermelho (rubro) ou preto (negro)
Toda folha é preta;
Se um nó é vermelho, os seus dois filhos serão, necessariamente, pretos
Todo caminho, mesmo simples, de um nó à sua folha descendente, contém o mesmo número de nós pretos. 
Para realizar a busca de um elemento na ARN, precisa-se criar a árvore com as regras da função Inserção e, para alterar a árvore, usa-se a função Remoção, na qual, necessariamente, haverá rotação da árvore para balanceá-la.
O crescimento da árvore é aleatório abaixo da parte organizada, para manter a eficiência dos requisitos de rebalanceamento estilo top-down, pois existem muitas classes a serem analisadas. Assim, mantêm-se o algoritmo vinculado ao custo constante, desacoplando a estrutura inicial das novas atualizações, com atrasos e intervalos arbitrários. Para ser eficaz, a remoção de um nó somente ocorre após balancear a árvore.
A árvore é implementada com a utilização de ponteiros – alocação dinâmica da memória –, apontando os endereços de memória para os respectivos raiz, pais e filhos. Para a criação e remoção de chaves (nós) dela, utiliza-se o conceito de recursividade, no qual chama-se a mesma função para ser executada repetidas vezes até o parâmetro indicado.�
	#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct noh{
 int numero_arvore;
 char cor;
 struct noh *pai;
 struct noh *esquerda;
 struct noh *direita;};
typedef struct noh nohVP;
// Prototipo das funcoes
nohVP* criaNovoNoh();
void rotacaoEsquerda(nohVP **Arvore_PV, nohVP *noh);
void rotacaoDireita(nohVP **Arvore_PV, nohVP *noh);
nohVP* inserir_Novo_Noh_PV(nohVP **Arvore_PV, nohVP *noh);
void inserirCorVP(nohVP **Arvore_PV, nohVP *noh);
void removerCorVP(nohVP **Arvore_PV, nohVP *noh);
nohVP* sucessorVP(nohVP *noh);
nohVP* maximoVP(nohVP *noh);
nohVP* minimoVP(nohVP *noh);
void visitarEmOrdem(nohVP* Arvore_PV);
void mostraDadosNoh(nohVP* noh);
int menu();
int calcularAlturaPreta(nohVP *noh);
nohVP* localizar_Noh_Arvore(nohVP* noh, int numero_arvore);
nohVP* rotacaoDireitaEsquerda(nohVP* arvore);
nohVP* rotacaoEsquerdaDireita(nohVP*arvore);
nohVP *removerVP(nohVP **Arvore_PV, nohVP *noh);
nohVP *vazio = NULL;
int main(){
 nohVP *Arvore_PV = NULL;
 nohVP *aux;
 int valor, altura, opc;
 vazio = (nohVP*)malloc(sizeof(nohVP));
 vazio->pai = Arvore_PV;
 vazio->direita = vazio->esquerda = vazio;
 do{
 opc = menu();
 switch (opc){
 case 1:
 inserir_Novo_Noh_PV(&Arvore_PV, criaNovoNoh());
 break;
 case 2:
 printf("Listagem dos nohs da Arvore \n\n");
 if(Arvore_PV != NULL){
 visitarEmOrdem(Arvore_PV); 
			}else{
 printf("Sem Elementos na Arvore \n");}
 break;
 case 3:
 if(Arvore_PV != NULL){
 altura = calcularAlturaPreta(Arvore_PV);
 printf("Altura preta da arvore: %d\n", altura);
			}else{
 printf("Sem Elementos na Arvore \n");}
 break;
 case 4:
 if(Arvore_PV != NULL){
 printf("Digite o numero da Arvore para Remoção ? \n");
 scanf("%d", &valor);
 aux = localizar_Noh_Arvore(Arvore_PV, valor);
 if (aux->numero_arvore == valor){
 mostraDadosNoh(aux);
 removerVP(&Arvore_PV, aux);
 }else{
 printf("\nO numero %d nao encontrada!\n\n", valor);}
 if(Arvore_PV == vazio){
 vazio = (nohVP*)malloc(sizeof(nohVP));
 vazio->pai = Arvore_PV = NULL;vazio->direita = vazio->esquerda = vazio;}
 }else{
 printf("Sem Elementos na Arvore \n");}
 break;
 case 5:
 if(Arvore_PV != NULL){
 printf("Qual noh deseja alterar\n ");
 scanf("%d", &valor);
 aux = localizar_Noh_Arvore(Arvore_PV, valor);
 if (aux->numero_arvore == valor){
 mostraDadosNoh(aux);
 inserir_Novo_Noh_PV(&(Arvore_PV),criaNovoNoh());
 removerVP(&Arvore_PV, aux);
				}else{
 printf("O numero %d nao encontrada!\n\n", valor);}
 }else{
 printf("Sem Elementos na Arvore \n");}
 break;
 }
 }
 while (opc != 0);
 return 0;
}
// Rotação a Esquerda do Noh
void rotacaoEsquerda(nohVP **Arvore_PV, nohVP *noh){
 nohVP *y;
 if(((*Arvore_PV)->pai == vazio) && (noh->direita != vazio)){
 y = noh->direita;
 noh->direita = y->esquerda;
 y->esquerda->pai = noh;
 y->pai = noh->pai;
 if(noh->pai == vazio){
 *Arvore_PV = y;
 }else if(noh == noh->pai->esquerda){
 noh->pai->esquerda = y;
 }else{
 noh->pai->direita = y;}
 }
 y->esquerda = noh;
 noh->pai = y;
 (*Arvore_PV)->pai = vazio;}
//Rotação a Direita do no
void rotacaoDireita(nohVP **Arvore_PV, nohVP *noh){
 nohVP *y;
 if(((*Arvore_PV)->pai == vazio) && (noh->esquerda != vazio)){
 y = noh->esquerda;
 noh->esquerda = y->direita;
 y->direita->pai = noh;
 y->pai = noh->pai;
 if(noh->pai == vazio){
 *Arvore_PV = y;
 }else if(noh == noh->pai->direita){
 noh->pai->direita = y;
		}else{
 noh->pai->esquerda = y;}
 }
 y->direita = noh;
 noh->pai = y;
 (*Arvore_PV)->pai = vazio;
}
// Insere na arvore
nohVP* inserir_Novo_Noh_PV(nohVP **Arvore_PV, nohVP *noh){
 nohVP *y = vazio;
 nohVP *x = *Arvore_PV;
 if((*Arvore_PV)== NULL){// Verifica se a arvore é NULL
 *Arvore_PV = noh;
 (*Arvore_PV)->pai = vazio;
 vazio->pai = *Arvore_PV;
 (*Arvore_PV)->cor = 'P';
 return 0;}
 if((*Arvore_PV)->numero_arvore == noh->numero_arvore){
 printf(" Numero duplicado, Coloque outro numero !!\n\n");
 return NULL;}
 while(x != vazio){
 y = x;
 if(noh->numero_arvore < x->numero_arvore){
 x = x->esquerda;
 }else{
 x = x->direita;}
 }
 noh->pai = y;
 if(noh->numero_arvore < y->numero_arvore){
 y->esquerda = noh;
 }else if(noh->numero_arvore > y->numero_arvore){
 y->direita = noh;}
 else if(noh->numero_arvore == y->numero_arvore){
 printf("Numeros iguais, Tente outro numero !!\n\n");}
 noh->esquerda = vazio;
 noh->direita = vazio;
 noh->cor = 'V';
 inserirCorVP(&(*Arvore_PV), noh);
 return noh;
}
// Insere a Cor do nó e faz o balaceamento caso precisar
void inserirCorVP(nohVP **Arvore_PV, nohVP *noh){
 nohVP *y;
 while(noh->pai->cor == 'V'){
 if(noh->pai == noh->pai->pai->esquerda){
 y = noh->pai->pai->direita;
 if(y->cor == 'V'){
 noh->pai->cor = 'P';
 y->cor = 'P';
 noh->pai->pai->cor = 'V';
 noh = noh->pai->pai;
 }else{
 if(noh == noh->pai->direita){
 noh = noh->pai;
 rotacaoEsquerda(&(*Arvore_PV), noh);}
 noh->pai->cor = 'P';
 noh->pai->pai->cor = 'V';
 rotacaoDireita(&(*Arvore_PV), noh->pai->pai);}
 }else{
 y = noh->pai->pai->esquerda;
 if(y->cor == 'V'){
 noh->pai->cor = 'P';
 y->cor = 'P';
 noh->pai->pai->cor = 'V';
 noh = noh->pai->pai;
			}else{
 if(noh == noh->pai->esquerda){
 noh = noh->pai;
 rotacaoDireita(&(*Arvore_PV), noh);}
 noh->pai->cor = 'P';
 noh->pai->pai->cor = 'V';
 rotacaoEsquerda(&(*Arvore_PV), noh->pai->pai);
 }
 }
 }
 (*Arvore_PV)->cor = 'P';
}
// Remove o noh da Arvore
nohVP *removerVP(nohVP **Arvore_PV, nohVP *noh){
 nohVP *y, *x;
 if((noh->esquerda == vazio) || (noh->direita == vazio)){
 y = noh;
 }else{
 y = sucessorVP(noh);}
 if(y->esquerda != vazio){
 x = y->esquerda;
 }else{
 x = y->direita;}
 x->pai = y->pai;
 if(y->pai == vazio){
 *Arvore_PV = x;
 }else if(y == y->pai->esquerda){
 y->pai->esquerda = x;
 }else{
 y->pai->direita = x;}
 if(y != noh){
	noh->numero_arvore = y->numero_arvore;} //Aqui os dados sao transferidos
 if(y->cor == 'P'){
 if((*Arvore_PV)->direita == vazio && (*Arvore_PV)->esquerda->direita != vazio){
 rotacaoEsquerda(&(*Arvore_PV), (*Arvore_PV)->esquerda);
 removerCorVP(&(*Arvore_PV), (*Arvore_PV)->esquerda);
 rotacaoDireita(&(*Arvore_PV), (*Arvore_PV));
 }else{
 if((*Arvore_PV)->esquerda == vazio && (*Arvore_PV)->direita->esquerda != vazio){
 rotacaoDireita(&(*Arvore_PV), (*Arvore_PV)->direita);
 removerCorVP(&(*Arvore_PV), (*Arvore_PV)->direita);
 rotacaoEsquerda(&(*Arvore_PV), (*Arvore_PV));}
 }
 removerCorVP(&(*Arvore_PV), x);
 }
 return y;
 free(y);
 free(x);
}
// Faz o balaceamento da cor caso tenha alguma incosistencia
void removerCorVP(nohVP **Arvore_PV, nohVP *noh){
 nohVP *aux;
 while(((*Arvore_PV) != noh) && (noh->cor == 'P')){
 if(noh == noh->pai->esquerda){
 aux = noh->pai->direita;
 if(aux->cor == 'V'){
 aux->cor = 'P';
 noh->pai->cor = 'V';
 rotacaoEsquerda(&(*Arvore_PV), noh->pai);
 aux = noh->pai->direita;}
 if((aux->esquerda->cor == 'P') && (aux->direita->cor == 'P')){
 aux->cor = 'V';
 noh = noh->pai;
 }else if(aux->direita->cor == 'P'){
 aux->esquerda->cor = 'P';
 aux->cor = 'V';
 rotacaoDireita(&(*Arvore_PV), aux);
 aux = noh->pai->direita;
 aux->cor = noh->pai->cor;
 noh->pai->cor = 'P';
 aux->direita->cor = 'P';
 rotacaoEsquerda(&(*Arvore_PV), noh->pai);
 noh = *Arvore_PV;}
 }else{
 aux = noh->pai->esquerda;
 if(aux->cor == 'V'){
 aux->cor = 'P';
 noh->pai->cor = 'V';
 rotacaoDireita(&(*Arvore_PV), noh->pai);
 aux = noh->pai->esquerda;}
 if((aux->esquerda->cor == 'P') && (aux->direita->cor == 'P')){
 aux->cor = 'V';
 noh = noh->pai;
 }else if(aux->esquerda->cor == 'P'){
 aux->direita->cor = 'P';
 aux->cor = 'V';
 rotacaoEsquerda(&(*Arvore_PV), aux);
 aux = noh->pai->esquerda;
 aux->cor = noh->pai->cor;
 noh->pai->cor = 'P';
 aux->esquerda->cor = 'P';
 rotacaoDireita(&(*Arvore_PV), noh->pai);
 noh = *Arvore_PV;}
 }
 }
 noh->cor= 'P';
}
// Sucessor do noh para o balaceamento
nohVP* sucessorVP(nohVP *noh){
 nohVP *aux;
 if(noh->direita != vazio){
 return minimoVP(noh->direita);}
 aux = noh->pai;
 while((aux != vazio) && (noh == aux->direita)){
 noh = aux;
 aux = aux->pai;}
 return aux;
}
// Maximo da Arvore
nohVP* maximoVP(nohVP *noh){
 while(noh->direita != vazio){
 noh = noh->direita;}
 return noh;
}
// Minimo da Arvore
nohVP* minimoVP(nohVP *noh){
 while(noh->esquerda != vazio){
 noh = noh->esquerda;}
 return noh;
}
// Cria o no para a Arvore
nohVP* criaNovoNoh(){
 nohVP *novo;
 novo = (nohVP*)malloc(sizeof(nohVP));
 printf("Informe um numero para a Arvore...: ");
 scanf("%d", &novo->numero_arvore);
 if(novo->numero_arvore < 0){
 printf("Numero Invalido! Tente Novamente !!!\n");
 return criaNovoNoh();}
 novo->cor = 'V'; // todo novo noh eh vermelho
 novo->pai = vazio;
 novo->direita = vazio;
 novo->esquerda = vazio;
 return novo;
}
// Função de Listagem dos dados
void visitarEmOrdem(nohVP* Arvore_PV){
 if (Arvore_PV != vazio){
 mostraDadosNoh(Arvore_PV);
 visitarEmOrdem(Arvore_PV->esquerda);
 visitarEmOrdem(Arvore_PV->direita);}
}
// Mostra os dados da Arvore
void mostraDadosNoh(nohVP* noh){
 printf("Endereco do noh....................: %p\n", noh);
 printf("Valor do noh.......................: %d\n", noh->numero_arvore);
 printf("Cor do noh.........................: %c\n\n", noh->cor);
 printf("Pai do noh.........................: %p\n", noh->pai);
 printf("Filho da esquerda..................: %p\n", noh->esquerda);
 printf("Filho da direita...................: %p\n\n", noh->direita);
 printf("\n\n");
}
//Menu do Usuario
int menu(){
 int opcao;
 printf("1.Inserir noh na arvore...:\n");
 printf("2.Mostrar arvore (RED)....:\n");
 printf("3.Calcular altura preta...:\n");
 printf("4.Remover noh da arvore...:\n");
 printf("5.Alterar noh da arvore...:\n");
 printf("0.Sair do programa........:\n");
 printf("?: ");
 scanf("%d", &opcao);
 return opcao;
}
// Calculo do balaceamento
int calcularAlturaPreta(nohVP *noh){
 int alt_esquerda = 0, alt_direita = 0;
 if(!noh){
 return 0;}
 if (noh == vazio){
 return 1;}
 if (noh->cor == 'P'){
 alt_esquerda += calcularAlturaPreta(noh->esquerda);
 alt_direita += calcularAlturaPreta(noh->direita);
 }else{
 calcularAlturaPreta(noh->esquerda);
 calcularAlturaPreta(noh->direita);}
 if (alt_esquerda > alt_direita){
 return alt_esquerda + 1;
 }else{
 return alt_direita + 1;}
}
// Localizar o noh da Arvore para devidas alteracoees ou remocoes
nohVP* localizar_Noh_Arvore(nohVP* noh, int numero_arvore){
 if ((noh == vazio) || (noh->numero_arvore == numero_arvore)){
 return noh;}
 if (numero_arvore < noh->numero_arvore){
 return localizar_Noh_Arvore(noh->esquerda, numero_arvore);
	}else{
 return localizar_Noh_Arvore(noh->direita, numero_arvore);}
}
Tabela 1 - Implementação da Árvore rubro-negra
�
Inserção
A inserção de um novo nó (chave) precisa manter as regras básicas. A operação de inserção com rebalanceamento da ARN pode atingir O(log (n+i)), se ocorrerem i inserções na árvore que contenha, inicialmente, n folhas. 
Para inserir um novo nó, primeiramente, percorre-se toda a árvore a partir da raiz até os nós que tenham valores mais próximos ao valor do novo nó, a fim de colocá-lo na posição correta.Por exemplo, a inclusão de um novo nó vermelho, sendo seu superior (pai) também vermelho, deve-se rebalancear a árvore a fim de mantê-la como ARN. O mesmo ocorre para os nós superiores a esse último. Nesse caso, chama-se recursivamente a mesma função para equilibrar e manter a quantidade de nós negros da raiz às folhas. (Soisalon-Soininen, 2013).
Como descrito acima, as inserções alterarão o diagrama da árvore de quatro formas diferentes:
Rotação Direita: realocação do nó p, que vira a raiz e se torna preto, e do nó a, que se torna nó à direita.
Figura 2 – Rotação Direita
Rotação Esquerda: realocação do nó p, que vira a raiz e se torna preto, e do nó a, que se torna nó à esquerda.
Figura 3 – Rotação Esquerda
	
Dupla Rotação Esquerda: realocação do nó p com o nó x à direita, que vira a o filho mais novo, e, posteriormente, move-se o nó a para a esquerda, que se torna filho. O nó x vira a raiz e se torna preto, e do nó p, que se torna nó à direita.
Figura 4 – Dupla Rotação Esquerda
Dupla Rotação Direita: realocação do nó p com o nó x à esquerda, que vira a o filho mais novo, e, posteriormente, move-se o nó a para a direita, que se torna filho. O nó x vira a raiz e se torna preto, e do nó p, que se torna nó à esquerda.
Figura 5 – Dupla Rotação Esquerda
Remoção
A remoção pode ser efetuada de duas formas distintas. A primeira delas, Remoção Efetiva (física), retira-se o nó e aplicam-se as propriedades da árvore, de acordo com operações de rotação e alteração de cor. A segunda, Remoção Preguiçosa (virtual), trata o nó a ser retirado como inativo, sem alterar a estrutura da árvore. Dessa maneira, os mecanismos de busca devem reconhecer o nó como “ausente”.
Para efetuar essa função, a árvore é previamente balanceada, o item requerido é encontrado, e, finalmente, remove-o. A remoção não ocorre sem a prévia análise: O pai tem que ser um nó vermelho com dois filhos-folhas, ou uma folha. Para tanto, permite-se somente duas rotações ou uma rotação mais uma dupla rotação, afim de atender às regras da ARN, mantendo a complexidade do algoritmo. O mesmo ocorre utilizando a chamada recursiva do pai do item selecionado, sem alterar a estrutura pré-definida.
Complexidade do Algoritmo
A complexidade de um algoritmo limita-se a distinguir a quantidade de passos realizados em um determinado tempo, obtendo-se a resposta à requisição dada. Dessa forma, insere-se o conceito da importância da eficiência desse algoritmo na busca, ordenação e balanceamento da árvore.
No caso de uma ARN, a complexidade mantêm-se como O(log n), podendo atingir O(log (n+i)), dependendo do número i de folhas, sendo a quantidade n de nós mantida constante.
Conclusão
A Árvore Rubro-Negra(ARN) é uma árvore binária balanceada que usa um método de busca com quatro premissas, nas quais dividem a árvore composta por pais negros, filhos vermelhos e folhas descartáveis. A abrangência da aplicabilidade desse algoritmo permite a sua utilização desde um dicionário de dados à criação e remoção de dados com referenciados de acordo com as regras da ARN. Como o retorno da pesquisa requerida de uma das formas mais velozes existentes, esse é um método excelente, com a complexidade de O(log n). 
Nesse trabalho, objetivou-se a apresentação da ARN com as funções de inserção e remoção dos nós da árvore. Com as funções descritas nas tabelas, pode-se verificar a utilização recursiva para manter a eficácia desse método, tanto para incluir novos nós e balancear a árvore, quanto equilibrar a árvore e remover o item especificado.
Verificou-se que a recursividade é um excelente artifício para acelerar a atuação dos ponteiros no algoritmo. Dessa forma, diz-se da Árvore Rubro-Negra como um processo eficiente e eficaz, mantendo a flexibilidade e organização de uma estrutura de dados excepcional.
Bibliografia Consultada
PRINCETON UNIVERSITY DEPARTMENT OF COMPUTER SCIENCE. Left-leaning Red-Black Trees. Robert Sedgewick. Disponível em < https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf>. Acesso em 15 de Junho de 2015.
PRINCETON UNIVERSITY DEPARTMENT OF COMPUTER SCIENCE. Left-leaning Red-Black Trees. Robert Sedgewick. Disponível em < https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf>.Acesso em 16 de Junho de 2015.
SAN DIEGO STATE UNIVERSITY: CS 660: RedBlack tree notes. Roger Whitney Disponível em <
(http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2) >. Acesso em: 18 de Junho de 2015.
UFRN – Ciências Exatas e da Terra Departamento de Informática e Matemática. David Déharbe. Disponível em < http://ufrn.academia.edu/DavidDeharbe>. Acesso em: 13 de Julho de 2015.
UNICAMP. Árvores binárias de busca balanceadas: ênfase em rubro-negras. Giovani Chiachia. Disponível em: <http://www.ic.unicamp.br/~rocha/teaching/2014s1/mc202/aulas/aula-arvores-rubro-negras.pdf> Acesso em 22 de Junho de 2015
Wikipédia, a enciclopédia livre. Árvore rubro-negra. Disponível em: <https://pt.wikipedia.org/wiki/%C3%81rvore_rubro-negra>. Acesso em 10 de Junho de 2015.