Árvore rubro-negra
Origem: Wikipédia, a enciclopédia livre.
Árvore rubro-negra é uma estrutura de dados criada em 1972 com o nome de árvores binárias simétricas. Assim como as árvores binárias comuns, as árvores rubro-negras possuem um conjunto de operações (tais como inserção, remoção e busca), porém são geralmente mais eficientes devido ao fato de estarem sempre balanceadas. Este balanceamento se dá justamente pela característica que dá nome à á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.
Índice |
[editar] Regras
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 é associada 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.
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 nodos 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 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.
Existem dois tipos de remoção em uma árvore. De acordo com a 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. De acordo com a remoção preguiçosa, marca-se 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".
[editar] 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. 2.ed. MIT Press and McGraw-Hill, 2001. 273-301 p. ISBN 0-262-03293-7
[editar] Ver também
[editar] Ligações externas
[editar] Demonstrações
[editar] Implementações
- Implementação eficiente de uma árvore rubro-negra
- RBT: uma implementação para SmallEiffel
- libredblack: uma implementação para C
- Uma implementação para Java
