17_Arvore PV

Prévia do material em texto

1
Árvores Preto e Vermelho
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estrutura de Dados e 
Algoritmos
Árvore PV
2
� É uma árvore binária de busca cujo nó contém uma
informação extra: cor.
� Através de restrições (invariantes ou propriedades) 
é possível se atingir uma configuração
aproximadamente balanceada. 
� Todo caminho em uma árvore vermelho-preto nunca é 
maior que o dobro de qualquer outro caminho.
2
Árvore PV
3
� Invariantes (propriedades)
� Cada nó possui uma cor: ou preta ou vermelha
� Toda folha (NIL) é preta
� A raiz é preta
� Todos os filhos de um nó vermelho são pretos
� Todo caminho simples de um nó a uma folha
descendente contém o mesmo número de nós pretos.
� Black-height
Árvore PV
4
� Exemplo
3
Exercício 
5
� Quais destas árvores são preto-vermelho?
42
5044
42
5040
42
5040
Black Height
6
� Black-height de um elemento X:
� Não contamos X;
� Contamos NIL;
� Black-height da raiz é o black-height da árvore;
4
Exercício
7
Black-Height do nó X =
Black-Height da raiz =
X
Exercício
8
Black-Height do nó X = 2
Black-Height da raiz = 3
X
5
POSCOMP 2009
9
POSCOMP 2009
10
6
Árvore PV
11
� Lema: uma árvore preto-vermelho com n nós 
internos tem no máximo a altura de:
� Consequência imediata:
� Busca, Máximo e Mínimo podem ser implementados em
O(lg n).
� Inserções e remoções são um pouco diferente: 
devem garantir as propriedades de uma árvore PV.
h ≤ 2.lg(n+1)
Árvore PV (Exercício)
12
� Desenhe uma árvore binária completa com os
valores {1, 2, …, 15}, e os nós vazios. 
� Em seguida pinte os nós de três formas diferentes
tal que o black-height das arvores PV resultantes
sejam 2, 3 e 4.
7
Árvore PV (Exercício)
13
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Árvore PV (Exercício)
14
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Bh= 2
8
Árvore PV (Exercício)
15
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Bh= 3
Árvore PV (Exercício)
16
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Bh= 3
9
Árvore PV (Exercício)
17
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Bh= 3
Árvore PV (Exercício)
18
8
4 12
2
1 3
6
5 7
10 14
9 11 13 15
Bh= 4
10
Árvore PV
19
� Como representar o nó e uma árvore PV em Java?
� É possível reusar algo anterior?
Árvore PV
20
� Como representar o nó e uma árvore PV em Java?
� É possível reusar algo anterior?
public class RBNode<T extends Comparable<T>> 
extends BSTNode<T> {
enum Color {BLACK, RED};
protected Color color;
public RBNode() {
this.color = Color.BLACK;
}
@Override
public boolean equals(Object obj) { 
return super.equals(obj) 
&& this.colour == ((RBNode<T>) obj).getColour();
}
}
11
Árvore PV
21
� Como representar o nó e uma árvore PV em Java?
� É possível reusar algo anterior?
...
@Override
public String toString(){
String resp = "NIL";
if(!isEmpty()){
resp = "(" + data.toString();
if(colour == Colour.RED){
resp = resp + ",R)"; 
}else{
resp = resp + ",B)";
}
}
return resp;
}
Árvore PV
22
� Como representar o nó e uma árvore PV em
Java?
� É possível reusar algo anterior?
public interface RBTree<T extends Comparable<T>> 
extends AVLTree<T>{
public RBNode<T>[] extendedPreOrder();
}
public class RBTreeImpl<T extends Comparable<T>> 
extends AVLTreeImpl<T> implements RBTree<T> {
}
12
Árvore PV
23
� Como representar o nó e uma árvore PV em
Java?
� É possível reusar algo anterior?
public interface RBTree<T extends Comparable<T>> 
extends AVLTree<T>{
public RBNode<T>[] extendedPreOrder();
}
public class RBTreeImpl<T extends Comparable<T>> 
extends AVLTreeImpl<T> implements RBTree<T> {
}
Que métodos precisarão ser sobrescritos?
Árvore PV
24
� Como representar o nó e uma árvore PV em
Java?
� É possível reusar algo anterior?
public interface RBTree<T extends Comparable<T>> 
extends AVLTree<T>{
public RBNode<T>[] extendedPreOrder();
}
public class RBTreeImpl<T extends Comparable<T>> 
extends AVLTreeImpl<T> implements RBTree<T> {
public void insert(T elem);
public void remove(T elem); //não implementar
}
Que métodos auxiliares precisam ser implementados?
13
Árvore PV
25
public class RBTreeImpl<T extends Comparable<T>> 
extends AVLTreeImpl<T> implements RBTree<T> {
public void insert(T elem);
public void remove(T elem);
int blackHeight();
protected boolean verifyProperties(){
return verifyNodesColour() &&
verifyNILNodeColour() && 
verifyRootColour() && 
verifyChildrenOfRedNodes() && 
verifyBlackHeight();
}
void fixUpInsert(RBNode<T> node);
}
Árvore PV
26
� Como é feita a pesquisa em uma árvore PV?
14
Árvore PV
27
� Como é feita a pesquisa em uma árvore PV?
� A pesquisa realizada em uma árvore preto-vermelho é 
igual a realizada em uma árvore binária de pesquisa
� Tempo = O(log n)
Árvore PV
28
� Inserções
� Insira o nó 51 na árvore abaixo. 
� Qual a melhor cor para o novo nó? Por quê?
15
Árvore PV
29
� Inserções
� Insira o nó 51 na árvore abaixo. 
� Qual a melhor cor para o novo nó? Por quê?
51
Árvore PV
30
� Inserções
� Insira o nó 87. Preserva o invariante?
16
Árvore PV
31
� Inserções
� Insira o nó 87. Preserva o invariante?
87
Árvore PV
32
� Inserções
� Insira o nó 87. Preserva o invariante?
87Como manter o invariante de uma
árvore PV após uma inserção?
17
Árvore PV
33
� Inserções
� Novo nó tem sempre cor vermelha
� Insere o novo elemento normalmente como na BST
� Se violar invariantes tem que consertar a árvore
� Considerar 5 casos sequenciais: 1 � 2 � 3 � 4 � 5
� Dica: focar no tio do novo nó
Árvore PV
34
� Inserções
RB-INSERT(N)
TREE-INSERT(N)
color[N] ← RED
FIXUP_CASE1(N)
18
Árvore PV
35
� Inserções
FIXUP_CASE1(N){
if (N is root)
N.color = BLACK
else
FIXUP_CASE2(N)
}
N N
Árvore PV
36
� Inserções
FIXUP_CASE2(N){
if (N.parent.color = BLACK)
//OK.
else
FIXUP_CASE3(N)
}
N
P
OK
19
Árvore PV
37
� Inserções
FIXUP_CASE3(N){
if (U.color = RED)
P.color = BLACK
U.color = BLACK
G.color = RED
FIXUP_CASE1(G)
else
FIXUP_CASE4(N)
}
FIXUP_CASE4(N){
Next = N
if (N is right child and P is left child)
leftRotation(P)
Next = N.left
else if (N is left child P is right child)
rightRotation(P)
Next = N.right
FIXUP_CASE5(Next)
}
Árvore PV
38
20
Árvore PV
39
FIXUP_CASE4(N){
Next = N
if (N is right child and P is left child)
leftRotation(P)
Next = N.left
else if (N is left child P is right child)
rightRotation(P)
Next = N.right
FIXUP_CASE5(Next)
}
Árvore PV
40
//N is left child and P is left child
FIXUP_CASE5(N){
P.color = BLACK
G.color = RED
if (N is left child)
rightRotation(G)
else
leftRotation(G)
}
21
Árvore PV
41
//N is left child and P is left child
FIXUP_CASE5(N){
P.color = BLACK
G.color = RED
if (N is left child)
rightRotation(G)
else
leftRotation(G)
}
Exemplo
42
� Insira o nó 8
8
FIXUP_CASE1(8)
22
Exemplo
43
� Insira o nó 8
8
FIXUP_CASE1(8)
Exemplo
44
� Insira o nó 4
8
FIXUP_CASE1(4)
FIXUP_CASE2(4)
4
23
Exemplo
45
� Insira o nó 4
8
FIXUP_CASE1(4)
FIXUP_CASE2(4)
if P.color = BLACK
//OK4
Exemplo
46
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
if P.color = BLACK
//OK
else
FIXUP_CASE3(2)
4
2
24
Exemplo
47
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
if (U.color = RED)
...
else
FIXUP_CASE4(N)
4
2
Exemplo48
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
if (U.color = RED)
...
else
FIXUP_CASE4(N)
4
2
N
25
Exemplo
49
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
FIXUP_CASE4(N)4
2
N
Exemplo
50
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
FIXUP_CASE4(2)
Next = 2
if (N is right child and P is left child)
...
else if (N is left child P is right child)
...
FIXUP_CASE5(Next)
4
2
N
26
Exemplo
51
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
FIXUP_CASE4(2)
FIXUP_CASE5(2)
P.color = BLACK
G.color = RED
if (N is left child)
rightRotation(G)
else
leftRotation(G)
4
2
N
P
G
Exemplo
52
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
FIXUP_CASE4(2)
FIXUP_CASE5(2)
P.color = BLACK
G.color = RED
if (N is left child)
rightRotation(G)
else
leftRotation(G)
4
2
N
P
G
27
Exemplo
53
� Insira o nó 2
8
FIXUP_CASE1(2)
FIXUP_CASE2(2)
FIXUP_CASE3(2)
FIXUP_CASE4(2)
FIXUP_CASE5(2)
P.color = BLACK
G.color = RED
if (N is left child)
rightRotation(G)
else
leftRotation(G)
4
2
Árvore PV (Remoções)
54
� Como remover um nó de uma árvore PV?
� Podemos usar a remoção de BST?
� As remoções da BST preservam os invariantes da
árvore PV?
� Que tipos de remoções causam problema?
28
Árvore PV (Remoções)
55
� Remover uma folha vermelha (6)
Árvore PV (Remoções)
56
� Remover uma folha vermelha (6)
29
Árvore PV (Remoções)
57
� Remover um nó interno vermelho (17) com filho 
substituto vermelho (22)
Árvore PV (Remoções)
58
� Remover um nó interno vermelho (17) com filho 
substituto vermelho (22)
30
Árvore PV (Remoções)
59
� Remover um nó interno vermelho (17) com filho 
substituto vermelho (22)
Árvore PV (Remoções)
60
� Remover folha preta (11)
31
Árvore PV (Remoções)
61
� Remover folha preta (11)
� Violação do black-height � foca no irmão (1) e sobrinho 
mais próximo (6)
Árvore PV (Remoções)
62
� Remover nó interno preto (13) com substituto preto 
(15)
32
Árvore PV (Remoções)
63
� Remover nó interno preto (13) com substituto preto 
(15)
� Violação do black-height � foca no irmão (25) e sobrinho 
mais próximo (22)
Remoção
64
� Caso 1: Irmão preto e filho vermelho
� Rotação + troca de cores
� Caso 2: Irmão preto e filhos pretos
� Troca cor
� Caso 3: Irmão vermelho
� Rotação
33
Remoção
65
� Caso 1: Irmão preto e filho vermelho
Remoção
66
� Caso 2: Irmão preto e filhos pretos
� Troca cor
34
Remoção
67
� Caso 3: Irmão vermelho
� Rotação
Referências
68
� Capítulo 14
� 1a edição