Algoritmos e Estruturas de Dados/Á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.

Visualização de uma árvore rubro-negra

Regras da rubro-negra

editar

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

editar

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

editar

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

editar

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

Remoção efetiva

editar

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

editar

Esta remoção marca 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

Ligações externas

editar

Implementações

editar