Árvores Rubro Negra

1. Árvore Rubro Negra
Prof: Sergio Souza Costa

2. Sobre mim
Sérgio Souza Costa
Professor - UFMA
Doutor em Computação Aplicada (INPE)


[email protected]
https://sites.google.com/site/profsergiocosta/home
https://twitter.com/profsergiocosta
http://gplus.to/sergiosouzacosta
http://www.slideshare.net/skosta/presentations?order=popular

3. ●
●

4. ●

5. ●
Algumas
implementações
usam uma sentinela
(apontando para a
raiz) no lugar de NIL.

7. 3
2
Essa é uma
árvore rubro
negra ?

8. 3
2
Essa é uma
árvore rubro
negra ?

Não:
Pela propriedade 5,
todo caminho até as
folhas devem ter o
mesmo números de
nós pretos.

10. ●

11. 1
Insere 1
r
1

12. ●
●

13. 2
Insere 2r
1
1
2
1

14. ●
●
●

15. 3
2
1
r
Insere 4
3
2
1
4
3
2
1
4

16. 3
2
1
r
Insere 4
3
2
1
4
3
2
1
4
3
2
1
4
Verifica as
propriedades
para o avô
O avô é
raiz, muda
a cor
Caso 1, o pai e o tio são vermelhos, muda as cores do do do pai,
tio e avô.

17. ●
●
●
●

18. ●
●
●
●
Neste ponto,
sabemos que esta
desbalanceada e
precisaremos fazer
rotações.

19. O pai está a direita do avô, e o no está a esquerda do pai
3
1
2
r Insere 2
3
1
3
2
1
Caso 2
Rotaciona o pai,
transformando
para o caso 3

20. 3
1
2
r Insere 2
3
1
3
2
1
Caso 2
Rotaciona o pai,
transformando
para o caso 3
3
2
1
>Caso 4b
Pelo caso 3, mudamos as
cores do avo e do pai do nó, e
rotacionamos.
O pai está a direita do avô, e o no está a esquerda do pai

21. 3
1
2
r Insere 2
3
1
3
2
1
Caso 2
Rotaciona o pai,
transformando
para o caso 3
3
2
1
>Caso 4b
Pelo caso 3, mudamos as
cores do avo e do pai do nó, e
rotacionamos.
O pai está a direita do avô, e o no está a esquerda do pai
Este procedimento é
aplicado para ambos
lados

22. Insere10 – raiz
10

23. Insere10 – raiz (muda a cor)

10

24. Insere 85, pai e preto, nao faz nada.

10
85

25. Insere 15, o pai e vermelho e o tio preto.

10
85
15

26. Rotaciona e muda cores.
15
10 85

27. Insere 70, o pai e vermelho e o tio e vermelho.

15
10 85
70

28. Muda cores
15
10 85
70

29. Insere 20, pai vermelho e tio preto.
20
15
10 85
70

30. Rotaciona e muda cores
15
10 70
20
85

31. Insere 60 , pai vermelho e tio vermelho.
15
10 70
20
85
60

32. Muda cores
15
10 70
20
85
60

33. Insere 30, pai vermelho e tio preto.
15
10 70
20
85
60
30

34. Rotaciona e muda cores.
15
10 70
30
85
6020

35. Insere 50, pai vermelho e tio vermelho
15
10 70
30
85
6020
50

36. Insere 50, muda cores


15
10 70
30
85
6020
50
Oops, vermelho e vermelho (70
e 30)

37. Rotaciona.
30
15 70
20
85
10
60
50

38. Rotaciona e muda cores.
30
15 70
20
85
10
60
50

39. Rotaciona e muda cores.
30
15 70
20
85
10
60
50

42. typedef enum Cor { VERMELHA, PRETA } Cor;
struct RubroNegra {
int key;
struct RubroNegra *dir, *esq, **pai;
Cor cor;

};

43. void rotacao_esq (RubroNegra **x){
RubroNegra* y = (*x)->dir;
(*x)->dir = y->esq;
y->esq = *x;
*x = y;
}

44. void insert(int k, RubroNegra** x){
RubroNegra** y = NULL;
while (*x != NULL ) {
y = x;
if (k < key(*x) )
x = &(*x)->esq;
else
x = &(*x)->dir;
}
(*x) = cria_no (k);
(*x)->pai = y;
verificaPropriedades (x);
}

45. Continua ....
void verificaPropriedades ( RubroNegra** r) {
RubroNegra **p, *u, **g;
p = (*r)->pai;
if ( p == NULL) {
(*r)->cor = PRETA;
}else if ((*p)->cor == VERMELHA ) {
u = tio (r);
g = avo (r);
if (u !=NULL && u->cor == VERMELHA ){
g = avo (r);
(*p)->cor = PRETA;
u->cor = PRETA;
(*g)->cor = VERMELHA;
verificaPropriedades(g);

46. Continuação
} else { // já sei que o tio e preto, ou vazio
if ( *p == (*g)->dir ) {
if ( key(*r) < key (*p) ) {
rotacao_dir(p);
r = &(*g)->dir->dir;
(*r)->pai = &((*g)->dir);
(*g)->dir->pai = g;
}
(*p)->cor = PRETA;
(*g)->cor = VERMELHA;
rotacao_esq(g);
(*g)->pai = (*g)->esq->pai;
(*g)->esq->pai = g;
(*g)->dir->pai = g;
}
}

47. Continuação
} else { // já sei que o tio e preto, ou vazio
if ( *p == (*g)->dir ) {
if ( key(*r) < key (*p) ) {
rotacao_dir(p);
r = &(*g)->dir->dir;
(*r)->pai = &((*g)->dir);
(*g)->dir->pai = g;
}
(*p)->cor = PRETA;
(*g)->cor = VERMELHA;
rotacao_esq(g);
(*g)->pai = (*g)->esq->pai;
(*g)->esq->pai = g;
(*g)->dir->pai = g;
}
}
Ainda falta considerar
a rotação o
desbalanceamento
para o outro lado.

48. Concluem e testem a implementação da rubro-negra.