05_-_Árvores_red_black[1]

Prévia do material em texto

ALGORITMOS E ESTRUTURAS DE DADOS II 
Árvores Red-Black 
Prof. Rafael Fernandes Lopes 
http://www.dai.ifma.edu.br/~rafaelf 
rafaelf@ifma.edu.br 
Baseado nos slides gentilmente cedidos pelo prof. Omar 
Introdução 
 São também árvores binárias de busca 
 Conhecidas também como árvores Rubro-Negras 
 Foram inventadas em 1972 com o nome de 
árvores binárias simétricas 
 Possuem dois novos campos: 
o Um bit extra para armazenar a cor de cada nó 
o Um ponteiro para o nó pai 
 A árvore é aproximadamente balanceada, pois 
nenhum caminho será duas vezes maior do que 
qualquer caminho para uma folha 
 
Introdução 
A altura máxima de uma árvore RB com n nós 
internos é: 
 
Por serem balanceadas as operações levam o 
tempo: 
 
Possuem melhor desempenho em árvores de 
alturas maiores 
 
)1log(2 += nh
)(log nO
Comparação: árvores AVL e rubro-negras 
 Árvores AVL: 
o primeira árvore binária de busca com balanceamento; 
proposta por Adel’son-Vel’skii e Landis em 1962 
o altura: entre log2(n + 1) e 1.4404 log2(n + 2) − 0.328, 
portanto, O(log n) 
 Árvores rubro-negras: 
o proposta por Guibas e Sedgewick em 1978 
o altura: 2 log2(n + 1), portanto, O(log n) 
 Comparação: árvores AVL são mais rigidamente 
balanceadas que árvores rubro-negras, levando a 
inserção e remoção mais lentas, porém recuperação 
(busca) mais rápida 
Propriedades 
1. Todo nó é vermelho ou preto 
2. A raiz da árvore necessariamente é preta 
3. Toda folha Nil é preta 
4. Nós vermelhos que não seja folhas possuem 
apenas filhos pretos 
5. Todos os caminhos a partir da raiz até suas 
folhas passam pela mesma quantidade de nós 
pretos 
6. Não podem existir dois nós vermelhos 
consecutivos 
Mais Propriedades 
Toda vez que um nó é inserido ou removido 
todas as propriedades devem ser testadas 
Caso uma ou mais propriedades não sejam 
satisfeitas então rotações e/ou mudanças de 
cores devem ser feitas 
o Rotações e mudanças de cores são feitas para 
manter o balanceamento 
O bh ou black-high de cada nó indica a 
quantidade de nós pretos encontrados entre 
a raiz e qualquer folha 
Exemplo 
27 20 
18 
22 10 
13 3 
5 1 16 
4 
3 
2 2 
3 
3 
2 2 2 
3 
12 
17 14 
2 2 
2 2 
19 21 2 24 40 1 1 
Inserção 
Todo nó ao ser inserido é vermelho 
o Objetiva não mudar o bh dos nós 
o Se um nó inserido for preto ele fere a 
propriedade 5 
 
 
 
 
 Se um nó for inserido na árvore vazia então 
basta mudar a cor do nó de vermelho para 
preto 
 
p p 
x 
Inserção 
Caso 1 
o Se um nó for vermelho e não tiver pai, então ele 
é a raiz e deve ser transformado em preto 
Caso 2 
o Um nó x esta sendo inserido, e seu tio é 
vermelho então é necessário recolorir o pai, o tio 
e o avô 
p 
x 
t 
a 
p 
x 
t 
a 
Inserção 
Caso 3 
o Se o nó a tiver um pai vermelho um nova 
operação deve ser feita 
Caso 4 
o Supondo que x esta sendo inserido em um nó 
vermelho e seu tio é nil (preto), então deve ser 
feita uma rotação 
Caso 3 
 Subcaso 1 – Caso os nós estejam à esquerda 
deve-se fazer uma rotação à direita 
o Os nós devem ser recoloridos 
Caso 3 
 Subcaso 2 – Caso os nós estejam à direita 
deve-se fazer uma rotação à esquerda 
o Os nós devem ser recoloridos 
Caso 3 
 Subcaso 3 – caso os nós estejam à direita e x 
seja o filho à esquerda de p, então deve-se se 
fazer uma rotação à direita com p e uma 
rotação à esquerda com a 
a 
t 
p 
x 
x 
a p 
t 
a 
t 
x 
p 
Rotação simples à esquerda 
Rotação simples à direita 
 
Recoloração de x e a 
Caso 3 
 Subcaso 4 - caso os nós estejam à esquerda e 
x seja o filho à direita de p, então deve-se se 
fazer uma rotação à esquerda com p e uma 
rotação à direita com a 
a 
t 
x 
p 
x 
p a 
t 
a 
t 
p 
x 
Rotação simples à direita 
 
Rotação simples à esquerda Recoloração de x e a 
Rotações com Sub-árvores 
y 
x 
A B 
C 
x 
y 
A 
B C 
à direita 
à esquerda 
Exemplo 
 Inserindo o nó 7 na árvore abaixo 
2 
1 4 
3 5 
6 
7 
- Propriedade 4 violada 
- Caso 3 
- Subcaso 2 → Rotação à 
esquerda no nó 5 
Exemplo 
 Inserindo o nó 7 na árvore abaixo 
 
2 
1 4 
3 
7 5 
6 
- Propriedade 4 violada 
- Basta re-colorir os nós 5, 6 e 7 
Exemplo 
 Inserindo o nó 7 na árvore abaixo 
 
2 
1 4 
3 
7 
6 
5 
Casos para Correção de Cores 
Existem 3 casos para correção das cores: 
oCaso 1 – o tio do elemento inserido é 
vermelho 
Mudar cores 
oCaso 2 – O tio do elemento inserido é 
preto e o elemento inserido é à direita 
oCaso 3 – O tio do elemento inserido é 
preto e o elemento inserido é à esquerda 
Nos casos 2 e 3 - Mudam-se as cores e 
fazem-se uma ou duas rotações 
Exemplo: inserindo o nó 4 
Caso 1: o tio do nó inserido é vermelho 
Exemplo: Inserindo o nó 4 
Caso 2: 7 é vermelho e 14 (tio) é preto 
Rotação nos elementos 2 e 7 
Violação 
Rotação à esquerda 
x = 2 
y = 7 
Exemplo: Inserindo o nó 4 
 Caso 3 o tio do elemento inserido à esquerda 
é preto; nós 7 e 2 continuam violando a 
propriedade 4 
Rotacionar 7 e 11 para a direita 
Exemplo: Inserindo o nó 4 
 Pela propriedade 1 o nó 7 passa a ser preto 
O nós 8 e 14 são pretos, logo o nó 11 passa a 
ser vermelho 
Algoritmo de Rotação 
Left_rotate(Tree T, obj x) 
 y ← right[x] 
 right[x] ← left[y] 
 if left[y] ≠ nil[T] then 
 pai[left[y]] ← x 
 end if 
 pai[y] ← pai[x] 
 if pai[x] = nil[T] then 
 T ← y 
 else 
 if x = left[pai[x]] then 
 left[pai[x]] ← y 
 else 
 right[pai[x]] ← y 
 end if 
 end if 
 left[y] ← x 
 pai[x] ← y 
O algoritmo de 
rotação à direita é 
análogo 
Algoritmo de Inserção 
RB-insert(Tree T, obj z) 
 y ← nil[T] 
 x ← T 
 while x ≠ nil[T] do 
 y ← x 
 if key[z] < key[x] then 
 x ← left[x] 
 else 
 x ← right[x] 
 end if 
 end while 
 pai[z] ← y 
 if y = nil[T] then 
 T ← z 
 else 
 if key[z] < key[y] then 
 
 left[y] ← z 
 else 
 right[y] ← z 
 end if 
end if 
left[z] ← nil[T] 
right[z] ← nil[T] 
cor[z] ← vermelho 
RB-insert-fixup(T, z) 
 
Algoritmo de Re-Estruturação 
RB-insert-fixup(Tree T, obj z) 
1: while cor[pai[z]] = vermelho do 
2: if pai[z] = left[pai[pai[z]]] then 
3: y ← right[pai[pai[z]]] 
4: if cor[y] = vermelho then 
5: cor[pai[z]] ← preto 
6: cor[y] ← preto 
7: cor[pai[pai[z]]] ← vermelho 
8: z ← pai[pai[z]] 
9: else 
10: if z = right[pai[z]] then 
11: z ← pai[z] 
12: left-rotate(T, z) 
13: end if 
14: cor[pai[z]] ← preto 
15: cor[pai[pai[z]]] ← vermelho 
16: right-rotate(T, pai[pai[z]]) 
17: end if 
18: else 
19: {o mesmo do caso then (linhas 3 a 16) 
 trocando entre si right com left} 
20: end if 
21: end while 
22: cor[T] ← preto 
// caso 1 
// caso 2 
// caso 3 
Exercícios 
 Insira os valores os valores 9, 20 e 16 na 
árvore do exemplo anterior 
Pesquise como fazer a remoção de nós 
 Implemente os algoritmos demonstrados 
para inserção de nós em uma árvore RB 
http://gauss.ececs.uc.edu/Users/Franco/Red
BlackTester/redblack.html 
 
	Algoritmos e Estruturas de Dados II
	Slide Number 2
	Slide Number 3
	Slide Number 4
	Slide Number 5
	Slide Number 6
	Slide Number 7
	Slide Number 8
	Slide Number 9
	Slide Number 10
	Slide Number 11
	Slide Number 12
	Slide Number 13
	Slide Number 14
	Slide Number 15
	Slide Number 16
	Slide Number 17
	Slide Number 18
	Slide Number 19
	Slide Number 20
	Slide Number21
	Slide Number 22
	Slide Number 23
	Slide Number 24
	Slide Number 25
	Slide Number 26
	Slide Number 27