Árvores rubro-negras

Árvore Rubro Negra
Prof: Sergio Souza Costa

Sobre mim
Sérgio Souza Costa
Professor - UFMA
Doutor em Computação Aplicada (INPE) [e-mail] https://sites.google.com/site/profsergiocosta/home http://www.slideshare.net/skosta/presentations?order=popular https://twitter.com/profsergiocosta http://gplus.to/sergiosouzacosta ●

●

●

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

●

2
3

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.

2
3

Essa é uma árvore rubro negra ?

●

r

Insere 1

1

1

●
●

r

Insere 2

1

1

1
2

2

●
●

●

Insere 4

r
2
1

2

2
3

1

1
3
4

3
4

Caso 1, o pai e o tio são vermelhos, muda as cores do do do pai,
Verifica as tio e avô. propriedades para o avô

Insere 4

r
2
1

2

2
3

1

1

3
4

2
O avô é raiz, muda a cor

1

3
4

3
4

●
●

●
●

●
●

●
●

Neste ponto, sabemos que esta desbalanceada e precisaremos fazer rotações. O pai está a direita do avô, e o no está a esquerda do pai r Insere 2
Caso 2

1

1

1

Rotaciona o pai, transformando para o caso 3

2
3

3

3
2

O pai está a direita do avô, e o no está a esquerda do pai r Insere 2
Caso 2

1

1

1

Rotaciona o pai, transformando para o caso 3

2
3

3

3
2

2
>Caso 4b
1

3

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 r Insere 2
Caso 2

1

1

1

Rotaciona o pai, transformando para o caso 3

2
3

3

3
2

Este procedimento é aplicado para ambos lados Pelo caso 3, mudamos as

2
>Caso 4b
1

3

cores do avo e do pai do nó, e rotacionamos. Insere10 – raiz
10

Insere10 – raiz (muda a cor)
10

Insere 85,