Árvores rubro-negras
Prof: Sergio Souza Costa
Sobre mim
Sérgio Souza Costa
Professor - UFMA
Doutor em Computação Aplicada (INPE) prof.sergio.costa@gmail.com 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,