Estrutura

Estrutura de Dados – SPI (P2)

Árvores rubro-negras

Robson Porto de Lucena – 1120190031Kelyanne Gualberto de Oliveira – 1410190144

Árvores rubro-negrasDefinição

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. As árvores rubro-negras possuem um bit extra para armazenar a cor de cada nó, que pode ser vermelho ou preto.


1. Por convenção, a raiz é preta;2. Todo nó é vermelho ou preto.3. Toda folha é preta;4. Se um nó é vermelho, os filhos serão pretos;5. Para cada nó, todos os caminhos do nó para folhas descendentes contém o

mesmo número de nós pretos.


Quando usar: Quando não usar:

• conjunto rico de operações • dados dinâmicos • garantia de desempenho

• dados mudam pouco • não requer todas essas operações

Árvores rubro-negrasDefinição – Estrutura da árvore

Árvores rubro-negrasDefinição – Estrutura do nó

Árvores rubro-negrasOperações - Inserção

• Uma inserção se inicia de forma semelhante a uma inserção em árvore binária, pois se trata apenas da adição de um nó na estrutura de dados.

• O elemento que é inserido na árvore rubro-negra possui sempre a cor vermelha, porém este é comparado com os outros elementos nas suas posições conforme as propriedades.

Árvores rubro-negrasOperações – Inserção – Inserção 1 (árvore vazia)

Todo nó inserido na árvore será a principio vermelho, portanto é necessário alterar a cor do primeiro nó para preto. Dessa forma a propriedade 1 (a raiz é sempre preta) não será violada.

Árvores rubro-negrasOperações – Inserção – Inserção 2 (pai vermelho)

Nesta condição, o pai do elemento a ser inserido é vermelho, portanto é necessário fazer modificações na árvore tendo em vista que a propriedade 4 (Se um nó é vermelho, os filhos serão pretos) está sendo violada. A inserção do novo nó depende da cor do tio, filho direito da raiz, se este for vermelho é feita a troca de cores do tio, pai e avo.

nó inseridonó não inserido

pai tio

avo

pai tio

avo

Árvores rubro-negrasOperações – Inserção – Inserção 3 (tio preto)

Esse procedimento também observa se o pai é vermelho, porém depende do tio ser preto. Neste caso, o nó será inserido a esquerda do pai e para esse procedimento é realizada uma rotação a direita e uma mudança de cor do pai e do avo.

avo

pai ex-avo

ex-tio

tio

pai

Árvores rubro-negrasOperações – Inserção – Inserção 3 (tio preto)

Caso o nó filho seja inserido a direita do pai é necessário proceder uma rotação a esquerda entre o novo nó e seu avo. Como consequencia da rotação, o novo nó se tornará filho esquerdo do seu pai.

pai

filho ex-pai

ex-filho

Árvores rubro-negrasOperações - Remoção

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

1. A remoção efetiva (fisica), com as operações de rotação e alteração de cor, remove-se o nó e estabelece-se as propriedades da árvore;

2. 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”.

Árvores rubro-negrasOperações – Remoção – Remoção 1 (nó rubro)

Se o nó que será removido for rubro não é necessário fazer nenhum ajust e na árvore, pois a remoção de nó vermelho não altera o balanceamento das árvores.

As ilustrações a seguir exemplificam a remoção do elemento 49 de acordo com a remoção 1.

Árvores rubro-negrasOperações – Remoção – Remoção 2 (nó rubro 2)

Se o nó for rubro e o seu sucessor também for rubro, faz -se uma referencia do nó que será removido para o seu sucessor e então o exclui da subárvore do sucessor. Nesse procedimento não é necessário modificar a coloração do nó que foi referenciado

As ilustrações a seguir exemplificam a remoção do elemento 47 de acordo com a remoção 2

Árvores rubro-negrasOperações – Remoção– Remoção 3 (filho rubro 3)

Se o nó que será removido for negro e seu filho for rubro, faz a troca da cor do filho para negro e dessa forma mantém os números de nós pretos de todos os caminhos iguais.

As ilustrações a seguir exemplificam a remoção do elemento 47 de acordo com a remoção 3

Árvores rubro-negrasAplicações

• A árvore VP, assim com a AVL, necessita de no máximo 1 rotação para balancear na inserção.

• Na remoção, a VP faz no máximo 1 rotação (simples ou dupla), enquanto a AVL pode necessitar de mais de uma.

• A árvore VP tem melhor pior caso que a árvore AVL - isso faz com que a árvore seja utilizada em aplicações de tempo real (criticas)

• Pode ser usada para construir blocos em outras estruturas de dados que precisam de garantias no pior caso. Por exemplo: estruturas de dados em geometria computacional podem ser baseadas em árvores VP.

• Em programas que apresentem dados dinâmicos e que necessitam de garantia em seu desempenho.

Internet

Estrutura