Árvore Rubro Negra

Prévia do material em texto

Árvore Rubro Negra
Adriana Scrobote
Aleffer Rocha
scrobote@alunos.utfpr.edu.br
aleffer@alunos.utfpr.edu.br
Universidade Tecnológica Federal do Paraná
Junho de 2015
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 1 / 1
Roteiro
Introdução;
Características;
Desempenho;
Propriedades;
Exemplo de Árvore Rubro Negra;
Rotações;
Coloração;
Inserção;
Busca;
Remoção;
Comparações;
Questão;
Conclusão;
Referências.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 2 / 1
Introdução
É uma árvore binária de pesquisa balanceada;
Inventada em 1972 por Rudolf Bayer qual a chamou de "Árvore Binária B Simétrica";
O atual nome foi adquirido em 1978 em um artigo escrito por Leonidas J. Guibas e Robert
Sedgewick.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 3 / 1
Características
É uma árvore binária de pesquisa balanceada;
Insere e remove os nós de forma inteligente;
Leva o nome de árvore rubro negra por conta da coloração dos nós;
Sua altura com N nós possui altura no máximo 2log(n + 1);
É conhecida por vários nomes:
Árvore Rubro Negra;
Árvore Vemelho Preta;
Árvore Vermelho e Preto;
Árvore Red-black;
Red-black Tree.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 4 / 1
Desempenho
Como toda árvore de pesquisa balanceada, a Árvore Rubro Negra possui desempenho
logarítmico:
Caso Médio Pior Caso
Espaço O(n) O(n)
Busca O(log n) O(log n)
Inserção O(log n) O(log n)
Remoção O(log n) O(log n)
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 5 / 1
Propriedades
Para uma árvore binária de pesquisa ser Rubro Negra, ela precisa satisfazer as seguintes
propriedades:
1. Todo nó é rubro ou negro;
2. O nó raiz é negro;
3. Todo nó folha NULL é negro;
4. Se um nó é rubro, então seus filhos são negros;
5. Para cada nó, todos os caminhos de um nó até as folhas descendentes possuem o mesmo
número de nós negros.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 6 / 1
Exemplo de Árvore Rubro Negra
Exemplo de Árvore Rubro Negra.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 7 / 1
Rotações
Quando ocorrem as rotações?
Quando a árvore atual não atende as propriedades da Árvore Rubro Negra;
Se não atende as propriedades então significa que no contexto a árvore está desbalanceada;
Como parte do balanceamento, em alguns casos, será preciso rotacionar os nós.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 8 / 1
Rotações
Rotação Simples à Esquerda
Rotação Simples à Esquerda.
Adaptado Introduction To Algorithms página 213.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 9 / 1
Rotações
Rotação Simples à Direita
Rotação Simples à Direita.
Adaptado de Introduction To Algorithms página 213.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 10 / 1
Rotações
Rotação Dupla à Esquerda
Rotação Dupla à Esquerda.
Adaptado de Introduction To Algorithms página 213.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 11 / 1
Rotações
Rotação Dupla à Direita
Rotação Dupla à Direita.
Adaptado de Introduction To Algorithms página 213.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 12 / 1
Rotações
Tabela de Rotações
Tabela de Rotações.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 13 / 1
Coloração
A coloração ocorre quando o pai e o tio do nó inserido são rubros:
Tio e pai passam a ser negros;
Avô passa a ser rubro;
Caso o avô seja raiz ele volta a ser negro;
O algoritmo continua no avô caso ele não seja raiz.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 14 / 1
Inserção
Todo novo nó é rubro.
Novo Nó
Exemplo Novo Nó 5
Novo Nó.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 15 / 1
Inserção
Se a árvore está vazia, é feita a inserção de um nó raiz;
Obs: Considerando uma implementação cuja struct possui campo pai, para um nó raiz, este
campo pai possui valor nulo e a cor deste nó é negro, atendendo a primeira propriedade da
Árvore Rubro Negra.
Inserção Nó Raiz
Inserindo o nó 5
Inserção Nó Raiz.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 16 / 1
Inserção
Inserção Caso 1: Se o pai do nó inserido é negro:
A inserção ocorre normalmente.
Exemplo Inserção Caso 1
Inserindo o nó 8
Exemplo Inserção Caso 1.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 17 / 1
Inserção
Inserção Caso 2: Se o pai do nó inserido é rubro e seu tio é negro:
Rotação Simples se o nó for externo;
Rotação Dupla se o nó for interno;
Antigo pai passa a ser negro;
Antigo avô passa a ser rubro;
Exemplo Inserção Caso 2:
Inserindo o nó 11
Exemplo Inserção Caso 2.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 18 / 1
Inserção
Inserção Caso 3: Se o pai do nó inserido é rubro e seu tio é também é rubro:
É um exemplo de coloração;
Tio e pai passam a ser negros;
Antigo avô passa a ser rubro;
Se avô é raiz, passa a ser negro;
O algoritmo continua no avô.
Exemplo Inserção Caso 3:
Inserindo o nó 14
Exemplo Inserção Caso 3.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 19 / 1
Inserção
Inserção Caso 3: Se o pai do nó inserido é rubro e seu tio é também é rubro:
Tio e pai passam a ser negros;
Antigo avô passa a ser rubro;
Se avô é raiz, passa a ser negro;
O algoritmo continua no avô.
Exemplo Inserção Caso 3:
Inserindo o nó 14
Exemplo Inserção Caso 3.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 20 / 1
Busca
Mesmo procedimento de busca em qualquer árvore binária de pesquisa:
Os campos chave com menor valor encontram-se do lado esquerdo da árvore;
Os campos chave com maior valor encontram-se do lado direito da árvore;
Valores chaves estes comparados com o valor chave da raiz.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 21 / 1
Remoção
Remoção Caso 1: Se o nó a ser removido é rubro, propriedade alguma se quebra, então
a remoção pode ser feita normalmente.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 22 / 1
Remoção
Remoção Caso 1
Remoção Caso 1.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 23 / 1
Remoção
Remoção Caso 2: Irmão do nó a ser removido é negro e o filho deste irmão é rubro.
Remove o nó;
Filho rubro do irmão negro do nó removido passa a ser negro;
Realiza rotação.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 24 / 1
Remoção
Remoção Caso 2
Remoção Caso 2.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 25 / 1
Remoção
Remoção Caso 3: Irmão do nó a ser removido é negro e os filhos deste irmão também
são negros:
Remove nó;
Pai do nó removido passa a ser negro;
Irmão do nó removido passa a ser rubro.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 26 / 1
Remoção
Remoção Caso 3
Remoção Caso 3.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 27 / 1
Remoção
Caso 4: Irmão do nó a ser removido é rubro:
Remove nó;
Realiza rotação.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 28 / 1
Remoção
Remoção Caso 4
Remoção Caso 4.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 29 / 1
Comparações
Alturas de Árvores Balanceadas:
Comparação de alturas de árvores balanceadas.
Adaptado de "Árvores Rubro-Negras", Letícia Rodrigues Bueno - UFABC, slide 7.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 30 / 1
Comparações
Alturas de Árvores Balanceadas:
Exemplo Árvore Rubro Negra e Árvore AVL.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 31 / 1
Comparações
Alturasde Árvores Balanceadas:
Exemplo Comparação de Alturas Árvore Rubro Negra e AVL.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 32 / 1
Comparações
Tempo, em segundos, para 1.000 execuções de cada conjunto de teste de simulação VMA, e número de comparações durante cada execução.
Performance Analysis BSTs in System Software, Ben Pfaff.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 33 / 1
Questão
23) Assinale a alternativa em que todas as propriedades de uma árvore vermelho
e preto são verdadeiras:
a) Todo nó é vermeho ou preto. A raiz pode ser vermelha ou preta. Todas as folhas são
vermelhas.
b) A raiz é preta. Todas as folhas são vermelhas. Para cada nó, todos os caminhos, desde
um nó até as folhas descendentes, contêm um mesmo número de nós pretos.
c) Toda folha é preta. Todo nó é vermelho ou preto. A raiz é preta.
d) Se um nó é vermelho, ambos os filhos são vermelhos. A raiz pode ser vermelha ou preta.
Todas as folhas são pretas.
e) Toda as folhas são vermelhas. Todo nó é vermeho ou preto. A raiz pode ser vermelha ou
preta.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 34 / 1
Questão
23) Assinale a alternativa em que todas as propriedades de uma árvore vermelho
e preto são verdadeiras:
a) Todo nó é vermeho ou preto. A raiz pode ser vermelha ou preta. Todas as folhas são
vermelhas.
b) A raiz é preta. Todas as folhas são vermelhas. Para cada nó, todos os caminhos, desde
um nó até as folhas descendentes, contêm um mesmo número de nós pretos.
c) Toda folha é preta. Todo nó é vermelho ou preto. A raiz é preta.
d) Se um nó é vermelho, ambos os filhos são vermelhos. A raiz pode ser vermelha ou preta.
Todas as folhas são pretas.
e) Toda as folhas são vermelhas. Todo nó é vermeho ou preto. A raiz pode ser vermelha ou
preta.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 35 / 1
Conclusão
Uma Árvore Rubro Negra possui um ótimo desempenho, logarítmico, porém, para seu uso
cada caso é um caso, como visto na tabela de comparações apresentada no slide 33.
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 36 / 1
Referências Bibliográficas
Site: Árvore rubro-negra, acesso em maio de 2015, disponível em:
http://pt.wikipedia.org/wiki/Árvore_rubronegra
Site: Red-black tree, acesso em maio de 2015, disponível em:
http://en.wikipedia.org/wiki/Red-black_tree
Site: Sociedade Brasileira de Computação - SBC / Documentos - 2010, disponível em:
http://www.sbc.org.br/index.php?option=com_jdownloads&Itemid=195&task=viewcategory&catid=82
Notas de aula: Árvore Rubro-Negra, Siang Wun Song 2008 - USP.
Notas de aula: Introduction To Algorithms, Prof. Erik Demaine 2005.
Artigo: Performance Analysis of BSTs in System Software, Ben Pfaff - Stanford University.
Notas de aula: Árvores Rubro-Negras, Letícia Rodrigues Bueno - UFABC.
Notas de aula: Árvores Rubro-Negras (Vermelho-Preta) - UFRGS.
Applet: Acesso em Junho de 2015, disponível em: http://people.ksp.sk/ kuko/bak/
Adriana Scrobote - Aleffer Rocha () Árvore Rubro Negra 2015 37 / 1