Árvore Rubro-Negra
Organização e Recuperação da Informação
Grupo: Osmir – Valmor – Victor
Tópicos Abordados







Introdução
Propriedades principais
Conceitos
Definição básica da estrutura
Inserção
Remoção
Comparação entre tipos de árvores
Introdução



Inventada em 1972, 10 anos depois da AVL
por Rudolf Bayer, sob o nome B-árvores
binárias simétricas
Adquirindo em 1978 seu atual nome, por Leo
J. Guibas and Robert Sedgewick
Árvore rubro-negra (do inglês Red-Black
trees)
Árvore Rubro-Negra



A árvore rubro-negra tem esse nome devido
a “coloração” de seus nós
Uma árvore rubro negra (ARN) é uma árvore
binária de busca com um campo adicional
que armazena se o nó é rubro ou negro
O fato de um nó ser rubro ou negro é usado
como fator de balanceamento da ARN
Propriedades




1 - Cada nó tem uma cor que é rubro ou negro. Por
convenção, uma árvore não vazia (ou subárvore)
tem a cor de sua raiz e uma árvore vazia é negra
2 - A raiz é negra
3 - Qualquer caminho da raiz até uma subárvore
vazia tem um número igual de nós negros
4 - As subárvores de um nó rubro são sempre
negras
-> Propriedade óbvia resultando da quarta condição é que num
caminho da raiz até uma subárvore vazia não pode haver dois
nós rubros consecutivos
Conceitos

(Altura negra) A altura negra de uma árvore rubro-negra A,
denotada an(A) é o número de nós negros que se encontram nos
caminhos da raiz até uma folha.
47
68
32
54
15
88
60
40
5
61
75
90
50

Observe que, pela terceira condição da definição de árvore
rubro-negra, esse número é bem definido. No caso da árvore
acima, a altura negra é 3
Conceitos



A altura de qualquer árvore rubro-negra é
logarítmica no número de chaves
armazenadas
A busca nas árvores rubro-negra tem
complexidade logarítmica.
Uma ARN impede que uma subárvore fique
com o dobro da altura da outra subárvore de
um nó.
Definição do nó

Estrutura interna de um nó
Chave
Cor(Rubro ou Negra)
Ptr Esquerda
Ptr Direita
Definição dos tipos
class ARN
{ Private:
typedef enum {RUBRO, NEGRO} cor;
typedef struct no *ptr;
struct no {
t chave;
ptr esq;
ptr dir;
cor tipo;
};
ptr raiz;
Public:
// métodos...
}
Inserção



Todo nó a ser inserido por convenção é rubro (pois
se fosse negro não seguiria a propriedade 3)
Se após a inserção for quebrada qualquer
propriedade da ARN devem ser feitas rotações e/ou
inversão de cores dos nós para que sejam
satisfeitas todas as propriedades
As regras de inserção levam em consideração a cor
do “tio” (o outro filho do pai do nó que recebeu o
novo nó) do nó inserido
Casos
w
“tio”
v
q
φ

t
ω
Ω
Φ
π
Se t for rubro: o pai de t torna-se rubro e, os filhos
de w tornam-se negros. Caso w seja a raiz, basta
trocar sua cor para negro

Se t for rubro: o pai de t torna-se rubro e, os filhos
de w tornam-se negros. Caso w seja a raiz, basta
trocar sua cor para negro
raiz
w
w
v
q
φ
v
t
ω
Ω
q
Φ
w
v
q
φ
t
ω
π
Ω
ω
π
φ
π
Φ
t
Ω
Φ
Casos
w
v
q
φ

t
ω
Ω
Φ
π
Se t for negro: neste caso faz-se uma operação
de rotação e, se necessário, uma inversão de
cores. Há 4 subcasos a considerar:
1º Subcaso

Se q é filho esquerdo de v e v é filho esquerdo de w
é realizada uma rotação simples a direita e as cores
de v e w são invertidas.
( Antes )
( Depois )
w
v
q
v
Ω
q
φ
w
ω
π
φ
π
ω
Ω
2º Subcaso

Se q é filho direito de v e v é filho esquerdo de w é
realizada uma rotação dupla a direita e as cores de q
e w são invertidas.
( Antes )
( Depois )
w
q
v
v
Ω
q
ω
φ
w
ω
π
φ
π
Ω
3º e 4º Subcasos

Os outros dois subcasos são simétricos aos
dois subcasos anteriores
Inserção




A complexidade da inserção, que é a da inserção
em árvore binária de busca, é logarítmica
O pior caso da fase de balanceamento é se tiver
que aplicar a inversão de cores até a raiz
Como o tamanho do caminho da raiz até qualquer
folha é logarítmico, o número de operações
também é logarítmico
Em conclusão, a complexidade da inserção em
árvores rubro-negras é logarítmica
Boolean Inserir (const int chave, ptr & filho, ptr & pai, ptr &avo)
{
if (filho == NULL)
{ filho = criar(chave);
return true;
}
else if (chave != filho->chave)
{ boolean e;
if (chave < filho->chave)
e = Inserir(chave, filho->esq, filho, pai);
else
e = Inserir(chave, filho->dir, filho, pai);
if (eh_rubro(filho))
if (e)
if (chave < filho->chave)
{ Remanejar(filho->esq, filho, pai) ;
return false;
}
else
{ Remanejar(filho->dir, filho, pai);
return false;
}
else
return true;
else
return false;
}
else
return eh_rubro(filho);
}
Inserção
Animação de uma Árvore Rubro-Negra

Applet (ARN) - Inserção
Remoção


A remoção em árvores rubro-negras pode
ser realizada também com um número
logarítmico de operações
O procedimento de remoção é composto de
uma etapa de remoção em árvore binária de
busca seguido de uma etapa de
balanceamento, caso as propriedades rubronegras teriam sido destruídas durante a
operação
Remoção

Se o nó removido for rubro, a árvore continua rubronegra, pois todas as condições da definição ficam
válidas:
–
–
–
–
1. Os nós resultantes tem cor rubro ou negro
2. A raiz, que era negra, não foi removida
3. Nenhum nó negro foi removido, portanto todos os
caminhos da raiz até uma folha tem um número igual de
nós negros
4. Os filhos de todos os nós rubros não removidos não
foram alterados e portanto ficam negros
Remoção

Se o nó removido for negro, o número de nós de pelo menos um
caminho foi decrementado e consequentemente a terceira
condição ficou inválida. Quando isto acontece, dois tipos de
solução são possíveis:
–
–
remoção preguiçosa- A remoção preguiçosa consiste em marcar o
nó como removido, mas sem tira-lo da árvore. Nenhum
remanejamento é necessário. Em compensação, os algoritmos de
inserção e busca devem ser modificados para levar em conta que
alguns nós da árvore devem ser considerados como ausentes. A
adoção desta solução é possível quando as árvores rubro-negras
são usadas no contexto de uma aplicação com poucas operações
de remoção
remoção efetiva - Através de um número logarítmico de operações,
a remoção efetiva restabelece as propriedades para que a árvore
seja rubro-negra. Essas operações são detalhadas em seguida
Remoção Efetiva

Caso o nó y a ser removido for rubro, as
propriedades da ARN não são afetadas.
( Antes )
( Depois )
v
v
x
y
Ω
q
φ
q
ω
x
φ
Ω
ω
Remoção Efetiva

Quando o nó a remover y é negro, todos os caminhos da raiz
até uma folha passando por esse nó tem um nó negro a
menos. Seja x o nó que passar a ocupar a posição de y na
árvore. O problema da remoção efetiva é resolvido atribuindo
negro a cor de x. Assim permanece igual a altura negra de
todos os caminhos contendo x, antes e depois da inserção.
( Antes )
( Depois )
v
v
y
Ω
q
φ
x
ω
x
q
φ
Ω
ω
Remoção Efetiva



Porém, se x já era negro, ele agora passa a ser duas
vezes negro, o que torna inválida a definição da ARN,
e é preciso remanejar a árvore para eliminar essa
situação.
No caso de x ser a raiz, então basta torná-lo
simplesmente negro: a altura negra de todos os
caminhos da árvore e decrementada, e a terceira
condição permanece verdadeira.
x não sendo a raiz, seja v seu pai, e w seu irmão. A
seguir é considerado o caso de x ser o filho, o outro
caso simétrico é omitido.
1º Subcaso – Remoção Efetiva


O primeiro caso, ilustrado abaixo considera a situação onde w
é rubro. Nesta situação, é realizada uma rotação simples a
esquerda de v, e as cores de v e w são modificadas.
O resultado desta modificação é que x permanece duplamente
negro. Porém, o seu irmão agora também é negro, e o
tratamento de um dos casos apresentados a seguir deve ser
aplicado.
( Depois )
( Antes )
w
v
v
x
w
x
ω
€
π
ω
£
φ
π
€
φ
£
2º Subcaso – Remoção Efetiva


O segundo caso configura a situação onde ambas sub-árvores
de w são negras e é ilustrado abaixo.
Este remanejamento consiste em subir um ponto negro dos
nós x e w, que passam a ser negro e rubro respectivamente,
no nó v. Se ele era anteriormente rubro, ele torna-se negro. Se
ele era anteriormente negro, ele torna-se duplamente negro, e
um novo remanejamento é necessário no nível superior.
( Antes )
( Depois )
vc
vc
x
x
w
ω
ω
€
w
£
φ
π
€
£
φ
π
3º Subcaso – Remoção Efetiva


No terceiro caso, ilustrado abaixo, a sub-árvore esquerda de w
é rubra, e a direita é negra. Seja z o filho esquerdo de w. É
então realizada uma rotação simples a direita de w, e uma
inversão das cores de w e z.
O nó x permanece duplamente negro, mas configura-se agora
uma situação diferente, onde a sub-árvore direita w é rubra,
cujo tratamento é apresentado a seguir.
( Depois )
( Antes )
vc
vc
x
x
w
ω
ω
€
z
z
Ω
£
€
w
£
φ
π
φ
π
Ω
4º Subcaso – Remoção Efetiva


O quarto e último caso corresponde portanto à situação onde a
sub-árvore direita de w é rubra. Seja z o filho direito de w.
A solução consiste em fazer uma rotação simples a esquerda
de v, atribuir aos nós v e z a cor negra, e a w a cor que era a
de v.
( Depois )
( Antes )
wc
vc
x
ω
€
v
w
z
£
x
φ
π
Ω
€
z
φ
£
π
Ω
Comparação entre árvores
Árvore
AVL
Árvore B
Rubro Negra
Fator de
balanceamento
Cada nó possui um campo
bal, que pode ser
0 (balanceada),
1 (desbalanceada a direita)
e -1 (desbalanceada a
esquerda).
Total de chaves de uma
página (ordem-1).
Cada nó possui um campo
cor que pode ser rubro
ou negro.
Método de
balanceamento
Se uma subárvore de um nó
estiver 2 níveis maior que a
outra subárvore
(bal = 1 ou -1) ocorre
uma rotação.
O nó que excede o número
de chaves é dividido em dois
novos nós (split).
Caso haja dois nós rubros
consecutivos ou a quantidade
de nós negros até qualquer
folha não sejam iguais ocorre
uma rotação e, se preciso
troca de cores.
Tolerância de
desbalanceamento
Uma subárvore pode estar 1
nível maior que a outra
subárvore de um nó
Zero. Ela sempre está
balanceada.
Uma subárvore não
pode estar 2 vezes maior que
a outra subárvore de um nó.
Crescimento
De cima pra baixo
(raiz  folhas)
De baixo pra cima
(folhas  raiz)
De cima pra baixo
(raiz  folhas)
Bibliografia


http://en.wikipedia.org/wiki/Red-black_tree
Árvores Balanceadas, David Déharbe,
Universidade Federal do Rio Grande do Norte