Árvore rubro-negra

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Uma árvore rubro-negra é um tipo de árvore de busca binária balanceada, uma estrutura de dados usada em ciência da computação, tipicamente para implementar vetores associativos. A estrutura original foi inventada em 1972 por Rudolf Bayer[carece de fontes?] que a chamou de "Árvores Binárias B Simétricas", mas adquiriu este nome moderno em um artigo de 1978 escrito por Leonidas J. Guibas e Robert Sedgewick..[1] 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.

Terminologia[editar | editar código-fonte]

Uma árvore rubro-negra é um tipo especial de árvore binária, usada em ciência da computação para organizar dados que possam ser comparáveis. Nas árvores rubro-negras, os nós folhas não são relevantes e não contém dados. Estas folhas não precisam ser mantidas em memória de computador - basta apenas um ponteiro para nulo para identificá-las — mas algumas operações em árvores rubro-negras são simplificadas se os nós folha forem explicitados. Para economizar memória, algumas vezes um nó sentinela interpreta o papel de todos os nós folha; todas as referência dos nós internos para os nós folha apontam para o nó sentinela.

Árvores rubro-negras, como todas as árvores de busca binárias, permitem travessia em-ordem de elementos de maneira eficiente, pois é possível 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).

Propriedades[editar | editar código-fonte]

Um exemplo de árvore rubro-negra

Uma árvore rubro-negra é uma árvore de busca binária onde cada nó tem um atributo de cor, vermelho ou preto. Além dos requisitos ordinários impostos pelas árvores de busca binárias, as árvores rubro-negras tem os seguintes requisitos adicionais:

  1. Um nó é vermelho ou preto.
  2. A raiz é preta. (Esta regra é usada em algumas definições. Como a raiz pode sempre ser alterada de vermelho para preto, mas não sendo válido o oposto, esta regra tem pouco efeito na análise.)
  3. Todas as folhas(nil) são pretas.
  4. Ambos os filhos de todos os nós vermelhos são pretos.
  5. Todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos.

Essas regras asseguram uma propriedade crítica das árvores rubro-negras: que o caminho mais longo da raiz a qualquer folha não seja mais do que duas vezes o caminho mais curto da raiz a qualquer outra folha naquela árvore. O resultado é que a árvore é aproximadamente balanceada. Como as operações de inserção, remoção, e busca de valores necessitam de tempo de pior caso proporcional à altura da árvore, este limite proporcional a altura permite que árvores rubro-negras sejam eficientes no pior caso, diferentemente de árvore de busca binária.

Para perceber por que essas propriedades garantem isto, basta observar que nenhum caminho pode ter dois nós vermelhos sucessivos, devido à propriedade 4. O caminho mais curto possível tem todos os nós pretos, e o caminho mais longo possível alterna entre nós vermelhos e pretos. Desde que todos os caminhos máximos têm o mesmo número de nós pretos, pela propriedade 5, isto mostra que nenhum caminho é mais do que duas vezes mais longo que qualquer outro caminho.

Em muitas das representações de estruturas de dados em árvore, é possível para um nó para ter só um filho, e os nós folha contêm dados. É possível representar árvores rubro-negras neste paradigma, mas ele modifica várias propriedades e deixa os algoritmos mais complexos. Por essa razão, este artigo usa "folhas nulas", que não contêm nenhum dado e simplesmente servem para indicar onde a árvore termina, como mostrado acima. Esses nós muitas vezes são omitidos dos desenhos, resultando em uma árvore que parece contradizer os princípios acima mencionados, mas que de fato não faz. Uma conseqüência disto é que todo nó interno (não-folha) têm dois filhos, embora um ou ambos filhos possam ser folhas nulas.

Alguns explicam uma árvore rubro-negra como uma árvore de busca binária cujas bordas, em vez de nós, são coloridas em vermelho ou preto, mas isto não faz nenhuma diferença. A cor de um nó na terminologia deste artigo corresponde à cor da borda que une o nó ao seu pai, exceto que o nó de raiz é sempre preto (propriedade 2) ao passo que a borda correspondente não existe.

Analogia com árvores B de ordem 4[editar | editar código-fonte]

A mesma árvore rubro-negra do exemplo acima vista como uma árvore B.

Uma árvore rubro-negra tem estrutura similar a uma árvore B de ordem 4, onde cada nó pode conter de 1 até 3 valores e (consequentemente) entre 2 e 4 ponteiros para filhos. Nesta árvore B, cada nó contem apenas um valor associado ao valor de um nó negro da árvore rubro-negra, com um valor opcional antes e/ou depois dele no mesmo nó. Estes valores opcionais são equivalentes a um nós vermelhos na árvore rubro-negra.

Uma maneira de visualizar esta equivalência é "subir" com os nós vermelhos na representação gráfica da árvore rubro-negra de modo a alinhá-los horizontalmente com seus pais negros, assim criando uma lista de nós na horizontal. Tanto na árvore B quanto na representação modificada da árvore rubro-negra, todos as folhas estão no mesmo nível.

Entretanto, esta árvore B é mais geral que uma árvore rubro-negra, já que a árvore B pode ser convertida de mais de uma maneira em uma árvore rubro-negra. Se a lista de valores de um nó da árvore B contém somente 1 valor, então esse valor corresponde a um nó negro com dois filhos. Se a lista contém 3 valores, então o valor central corresponde a um nó negro e os outros dois valores correspondem a filhos vermelhos. Se a lista contém 2 valores, então podemos fazer qualquer um dos valores negro e o outro valor corresponde a seu filho vermelho.

Operações[editar | editar código-fonte]

As operações somente-leitura em uma árvore rubro-negra não necessitam nenhuma modificação daquelas usadas em uma árvore binária, porque toda árvore rubro-negra é um caso especial de uma árvore de busca binária simples. Contudo, o resultado imediato de uma inserção ou remoção pode violar as propriedades de uma árvore rubro-negra. Restaurar as propriedades rubro-negras requer um pequeno número (O(log n) ou O(1)) de modificações de cores (que na prática são muito rápidas) e não mais do que três rotações de árvore (duas para a inserção). Embora operações de inserção e remoção sejam complicadas, seus tempos permanecem O(log n).

Inserção[editar | editar código-fonte]

A cada vez que uma operação é realizada na árvore, testa-se este conjunto de propriedades e são efetuadas rotações e ajuste de cores até que a árvore satisfaça todas estas regras.

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 rotacionados.

Ao inserir-se um elemento em uma árvore rubro-negra, esta é comparada com os elementos e alocada em sua posição conforme a regra 2. Ao inserir-se um elemento ele é sempre da cor vermelha (exceto se for o nó raiz). A seguir a árvore analisa o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 4.

Uma inserção começa pela adição de um nó de forma semelhante a uma inserção em árvore binária, pintando-se o nó em vermelho. Diferentemente de uma árvore binária onde sempre adicionamos uma folha, na árvore rubro-negra as folhas não contém informação, então inserimos um nó vermelho na parte interna da árvore, com dois nós filhos pretos, no lugar de uma folha preta.

O que acontece a seguir depende da cor dos nós vizinhos. O termo nó tio será usado para referenciar o irmão de um nó pái, como em uma árvore genealógica. Note que a:

  • Propriedade 3 (todos as folhas são pretas) sempre se mantém;
  • Propriedade 4 (ambos os filhos de um nó vermelho são pretos) é tratada somente pela adição de um nó vermelho, repintura de um nó preto como vermelho ou uma rotação;
  • Propriedade 5 (todos os caminhos de um dado nó até suas folhas contém o mesmo número de nós pretos) é tratada apenas pela adição de um nó preto, repintura de um nó vermelho em preto ou uma rotação.
Nota: O rótulo N será usado para denotar no novo nó sendo inserido. P denotará o pai de N', enquanto que G será o avô (grandparent) de N', e U (uncle) será o tio do nó N'. Note-se que entre em alguns casos, os papéis e os rótulos dos nós são trocadas, mas em cada caso, cada etiqueta continua a representar o mesmo nó que representava no início do caso. Qualquer cor exibida no diagrama ou é assumida no seu caso ou implícita por essas hipóteses.

Cada caso será demonstrado com exemplos em código C. O tio e o avô de um nó podem ser encontrados pelas seguintes funções:

struct node *
avo(struct node *n)
{
	if ((n != NULL) && (n->pai != NULL))
		return n->pai->pai;
	else
		return NULL;
}
 
struct node *
tio(struct node *n)
{
	struct node *g = avo(n);
	if (g == NULL)
		return NULL; // Não ter avô significa não ter tio
	if (n->pai == g->esquerda)
		return g->direita;
	else
		return g->esquerda;
}

Case 1: O novo nó N está na raiz da árvore. Neste caso, este nó é repintado de preto para satisfazer a Propriedade 2. Como esta ação adiciona um nó preto em todos os caminhos da árvore de uma só vez, a Propriedade 5 não é violada.

void
insercao_caso1(struct node *n)
{
	if (n->pai == NULL)
		n->cor = PRETA;
	else
		insercao_caso2(n);
}

Case 2: O pai do novo nó P é preto. Neste caso a Propriedade 4 claramente não é invalidada. A Propriedade 5 tampouco é ameaçada pois o novo nó N tem como filhos dois nós-folha pretos, e sendo N vermelho, os caminhos passando por cada um dos seus filhos têm o mesmo número de nós pretos - da mesma forma que os caminhos que passavam pelo nó-folha preto que foi substituído por N. Por fim, neste caso, a árvore continua válida após a inserção, não sendo necessária mais alterações.

void
insercao_caso2(struct node *n)
{
	if (n->pai->cor == PRETA)
		return; /* Árvore ainda é válida */
	else
		insercao_caso3(n);
}
Nota: Nos 3 casos a seguir pode-se assumir que N tem um nó-avô G pois o seu pai P é vermelho (sendo vermelho P não é a raiz da árvore). Tendo um avô, N obrigatoriamente também tem um nó-tio U, podendo este ser um nó-folha nos casos 4 e 5.
Diagrama do caso 3

Caso 3: Quando ambos o pai P e o tio U são vermelhos, então ambos podem ser repintados de preto e o avô G torna-se vermelho para manter a Propriedade 5. Agora, o novo nó vermelho N tem um pai na cor preta. Dado que todos os caminhos que passam pelo pai ou tio de N devem passar pelo seu avô, o número de nós pretos nestes caminhos não foi alterado. Porém, o avô G pode estar violando agora a Propriedade 2 ou 4. Para consertar isso, uma "chamada recursiva" do procedimento de insercao_caso1 é iniciada passando G como parâmetro (chamada recursiva aqui está em destaque pois a invocação ao caso 1 apenas PODE levar ao caso 3).

Nota: como a invocação da recursão é sempre no final do algoritmo (tail-recursive call) o mesmo pode ser reescrito facilmente como um loop; sendo este o único loop do algoritmo, e todas as rotações acontecendo após o loop, isso prova que um número constante de rotações é realizado.
void
insercao_caso3(struct node *n)
{
	struct node *u = tio(n), *g;
 
	if ((u != NULL) && (u->cor == VERMELHA)) {
		n->pai->cor = PRETA;
		u->cor = PRETA;
		g = avo(n);
		g->cor = VERMELHA;
		insercao_caso1(g);
	} else {
		insercao_caso4(n);
	}
}
Nota: Nos casos restantes (4 e 5), é assumido que o nó-pai P é o filho a esquerda do seu pai. No caso contrário, de ser o filho a direita, faz-se necessário apenas a inversão dos conceitos de esquerda e direita. Os códigos de exemplo já fazem este tratamento.
Diagrama do caso 4

Caso 4: O pai P é vermelho mas o tio U é preto; além disso, o novo nó N é o filho a direita de P, e P o filho a esquerda do seu pai G. Neste caso, uma rotação a esquerda que troca os papéis do novo nó N e de seu pai P deve ser realizada. Quando isso acontecer o antigo nó-pai P precisa ser tratado usando o Caso 5 (renomeando N e P) isso porque a Propriedade 4 ainda está sendo violada. Além disso, a rotação faz com que alguns caminhos (aqueles na sub-árvore denominada "1" na figura abaixo) passem pelo novo nó de forma diferente ao que acontecia antes, mas como os dois nós desta sub-árvore são vermelhos a Propriedade 5 não é violada (pela rotação).

void
insercao_caso4(struct node *n)
{
	struct node *g = avo(n);
 
	if ((n == n->pai->direita) && (n->pai == g->esquerda)) {
		rotacionar_esquerda(n->pai);
		n = n->esquerda;
	} else if ((n == n->pai->esquerda) && (n->pai == g->direita)) {
		rotacionar_direita(n->pai);
		n = n->direita;
	}
	insercao_caso5(n);
}
Diagrama do caso 5

Caso 5: O pai P é vermelho mas o tio U é preto, o novo nó N é o filho esquerdo de seu pai P, e P é o filho esquerdo de seu pai, G. Neste caso, umarotação a direita no pai de P é realizada. O resultado é uma árvore onde o antigo pai P é agora pai tanto do novo nó N quanto do avô de N, G. É sabido que G é preto, já que seu antigo filho P não poderia ser vermelho. Então as cores de P e G são trocadas, e a árvore resultante satisfaz a propriedade 4 (ambos os filhos de cada nó vermelho são pretos). A propriedade 5 (Todos os caminhos de um determinado nó até suas folhas contém o mesmo número de nós pretos) também se mantém satisfeita, já que todos os caminhos os caminhos até as folhas passam pelo nó G antes, e agora todos passam pelo P. Em cada caso, este é o único nó preto da sub-árvore.

void
insercao_caso5(struct node *n)
{
	struct node *g = avo(n);
 
	n->pai->cor = PRETA;
	g->cor = VERMELHA;
	if ((n == n->pai->esquerda) && (n->pai == g->esquerda)) {
		rotacionar_direita(g);
	} else {
		/*
		 * Aqui, (n == n->pai->direita) && (n->pai == g->direita).
		 */
		rotacionar_esquerda(g);
	}
}

Note that inserting is actually in-place, since all the calls above use tail recursion.

Remoção[editar | editar código-fonte]

Existem dois tipos de remoção em uma árvore. De acordo com a remoção efetiva (física), com as operações de rotação e alteração de cor, remove-se o nó e estabelece-se as propriedades da árvore. De acordo com a remoção preguiçosa (virtual), marca-se um nó como removido, mas efetivamente não o retira. Sendo desta maneira nenhuma alteração é efetuada na árvore, porém são necessários novos mecanismos de busca e inserção para que reconheçam o nó como "ausente".

Bibliografia[editar | editar código-fonte]

Ver também[editar | editar código-fonte]

Referências

  1. Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees FOCS 1978: 8-21

Ligações externas[editar | editar código-fonte]

Demonstrações[editar | editar código-fonte]

Implementações[editar | editar código-fonte]