inf01203 rubronegras

Árvores Rubro-Negras
• Árvore Binária de Pesquisa (ABP) com nodos coloridos de vermelho e preto
– Árvore balanceada

Árvores Rubro-Negras
(Vermelho-Preta)

• Qualquer caminho da raiz até as folhas, nenhum caminho será maior que duas vezes o comprimento de qualquer outro – Aproximadamente balanceada

10

– Número menor de rotações/reestruturações
• Comparada com AVL

5

11

3

6
7

Estrutura da Árvore

Estrutura da Árvore

• Cada nodo contem os seguintes campos:

• Cada nodo contem os seguintes campos:

–
–
–
–

Chave
Ponteiro para subárvores esquerda
Ponteiro para subárvores direita
Cor

10
5

3

–
–
–
–

Chave
Ponteiro para subárvores esquerda
Ponteiro para subárvores direita
Cor

10
5

11

6

11

3 nil 7

• Propriedade
– Todo nodo da árvore é ou vermelho ou preto

• Propriedade

6 nil nil

nil

nil

7 nil nil

– Todo nodo da árvore é ou vermelho ou preto

Propriedades

Propriedades - RESUMO
10
5

I.
II.
III.
IV.
V.

10

11

Todo nodo é vermelho ou preto
3
6 nil nil
A raiz é preta nil nil nil
7
Toda folha (nil) é preta nil nil
Se um nodo é vermelho, então ambos os seus filhos são pretos
Para cada nodo, todos os caminhos desde um nodo até as folhas descendentes contêm o mesmo número de nodos pretos
BALANCEAMENTO

• RAIZ
– A raiz é preta

• NODOS EXTERNOS

5

11
6 nil nil

3 nil nil nil

7

– Todo nodo externo é preto

• NODOS INTERNOS

nil nil

– Os filhos de um nodo vermelho são pretos

• PROFUNDIDADE
– Todos os nodos externos têm a mesma profundidade preta que é definida como o número de ancestrais pretos menos 1

Inserção
• Encontra a posição na árvore
– Substitui nil pelo nodo com 2 filhos nil

• Primeiro nodo (RAIZ)

INSERÇÃO

– PRETO

• demais nodos
– VERMELHO

50

Inserção

Inserção

• Encontra a posição na árvore

• Encontra a posição na árvore

– Substitui nil pelo nodo com 2 filhos nil

• Primeiro nodo (RAIZ)

– Substitui nil pelo nodo com 2 filhos nil

• Primeiro nodo (RAIZ)

20

– PRETO

• demais nodos

• demais nodos

50

– VERMELHO

50

–