Estruturas de Dados Intermediário/Árvores Rubro-Negras

Árvore rubro-negra (Red-Black tree) é uma estrutura de dados de programação criada em 1972 com o nome de árvores binárias simétricas. Como as árvores binárias comuns às rubro-negras possuem um conjunto de operações (inserção, remoção, busca), porém são geralmente mais eficientes devido ao fato da rubro-negra estar sempre balanceada. Este balanceamento se dá justamente pela característica que dá nome a árvore, que vem de um bit extra em cada nodo que determina se esta é "vermelha" ou "preta" dentro do conjunto de regras que rege a árvore. Além desde bit, cada nodo também conta com os campos dados do nodo, filho esquerdo do nodo, filho direito do nodo e pai do nodo.

Regras da rubro-negra

Uma árvore rubro-negra estará sempre balanceada pois segue o seguinte conjunto de regras:

cada nodo da árvore possui um valor
a cada novo nodo inserido na árvore obedecerá o esquema de menor para o lado esquerdo e maior para o lado direito.
a cada nodo é associado uma cor: vermelha ou preta.
o nodo raiz é sempre preto.
nodos vermelhos que não sejam folhas possuem apenas filhos pretos.
todos os caminhos a partir da raiz até qualquer folha passa pelo mesmo número de nodos pretos.

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.

Rotações

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

Inserções

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 um elemento ele é sempre da cor vermelha (exceto se for o nodo raiz). A seguir a árvore analisa se o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a regra 6.

Remoções

Existem dois tipos de remoção em uma árvore:

Remoção efetiva

Com as operações de rotação e alteração de cor, remove-se o nodo e estabelece-se as propriedades da árvore.

Remoção preguiçosa

Esta remoção marca um nodo 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 nodo como "ausente".

Bibliografia

Mathworld: Red-Black Tree
San Diego State University: CS 660: Red-Black tree notes, por Roger Whitney
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp.273–301.

Ligações externas

Demos

Red/Black Tree Demonstration, um demo interativo em Java
Red-Black Tree Animation
aiSee: Visualization of a Sorting Algorithm, uma animação em gif (200 Kb)
Red-Black Tree Demonstration,um demo em Java criado por David M. Howard
AVL Tree Applet