Observações sobre os Comentários

1. ARTHUR MATHEUS DOS SANTOS LIMA - complementou a questão 6.

2. BRENDA MARTINS BARROS DE ALMEIDA PAZ - fez uma observação do porque não poder ter duas folhas vermelhas consecultivas.

3. CARLOS GABRIEL SANTOS DE MELO - deu uma ideia de como fazer as inserções em uma árvore rubro negra de como que não seria preciso fazer rotações, mas teria que ordenar os valores que seriam inseridos. Não entendi completamente a ideia, mas ele representou a árvore em um vetor de forma incorreta.

        - fez uma pergunta sobre como manter as árvores rubro negras em arquivos.

4. CRISTIANO LIMA OLIVEIRA - fez uma comparação entre árvores binárias de busca e árvores rubro negras.

5. DAYVID WESLLEY LOPES DOS SANTOS - complementou a questão 4 dando exemplos de onde usar cada tipo de árvore.

6. EDILSON LEITE SANTOS JUNIOR - complementou o comentário de Jose Vitor, falando sobre a necessidade de alterar as cores.

7. ERICK SOUSA SANTOS - deu sua opinião sobre as árvores rubro negras.

8. FÁBIO FIGUEIREDO FREIRE - fez o mesmo complemento que Filipe sobre a questão 4.

9. FILIPE NASCIMENTO ALMEIDA - complementou a questão 4 que não estava bem detalhada.

10. GABRIEL SANTANA DE CARVALHO - falou sobre a altura máxima da árvore rubro negra.

11. GLENIO ANDRADE LÔBO - fez uma observação sobre a altura máxima de uma árvore rubro negra.

12. HÉLISSON OLIVEIRA MAGALHÃES CERQUEIRA - complementou a questão 4.

13. IURY PATRICK GOIS SANTOS - tentou fazer um comparação entre as árvores AVL e as rubro negras, mas acabou só repetindo o que o grupo respondeu na questão 4.

14. JEREMIAS DOS SANTOS FRANCELINO - falou sobre a eficiência de fazer a implementação dinâmica das árvores.

15. JOAO MANOEL FIDELIS SANTOS - fez observações interessantes sobre a utilidade das árvores rubro negras e onde são usadas.

16. JOÃO VICTOR ANDRADE RODRIGUES - fez uma comparação entre as AVL e as rubro negras.

17. JOSE VITOR SANTOS SILVA - deu sua opinião sobre as árvores rubro negras.

18. LETICIA ARAGAO DE FREITAS DE OLIVEIRA - apresentou uma ideia de como fazer o aterramento que eu não tinha visto ainda. Segundo ela seria um modo de economizar espaço mas não vi como isso aconteceria já que usando simplesmente o NULL do C para aterrar usaria menos espaço que a ideia dela.

19. Lucas Santana de Oliveira - fez uma pergunta sobre a resposta da questão 10.

20. LUCAS WAGNER DE FARIAS RIBEIRO - complementou o comentário de Marcel.

21. MARCEL REINAN SA DOS SANTOS - fez uma observação sobre um tipo diferente de rubro negra (BST).

22. MARCELO CARVALHO DA CONCEICAO - deu sua opinião sobre as árvores rubro negras e disse o que achou interessante nelas.

23. MATEUS CARDOSO DA SILVA - complementou a questão 3, falando sobre as complexidades e as operações executadas.

      - complementou a questão 6, dando uma outra definição e uso.

24. NATANAEL OLIVEIRA GOIS - sobre questão 3: não acrescentou nada de novo. Só repetiu o que o grupo já havia dito.

      sobre questão 7: repetiu o que Leticia já havia dito em seu comentário anterior.

25. OSNI MARIO VIEIRA ARAUJO - respondeu a pergunta, sobre como manter árvores rubro negras em arquivos, de Carlos.

      - fez um complemento sobre os modos de implementar as árvores rubro negras.

      - tentou complementar a questão 4 mas só repetiu o que o grupo já havia dito.

26. REINALDO LIMA MENDONÇA JUNIOR - fez uma observação sobre o tipo a ser usada para a cor na estrutura. Achou que um char economizaria mais espaço e ainda manteria as operações simples.

27. THIAGO SANTOS FRANCA - fez o mesmo complemento que Filipe, só que não tão bom, sobre a questão 4.

28. WENDEL LIMA OLIVEIRA - fez uma pergunta sobre como seria a implementação da árvore da questão 9.

     - fez uma observação de como calcular a altura de uma árvore rubro negra.

29.  WESLEY ALVES SANTANA - rebateu os comentários de Lucas Wagner e Erick Sousa, falando o motivo pelo qual se deve usar o tipo booleano.

      - falou sobre a árvore rubro caída para a esquerda.

Grupo A: João Pedro Souza Rolemberg (Líder)

Grupo 1: Helisson Oliveira

            João Rolemberg

           Lucas Wagner

1- árvores rubro-negras também são arvores binárias balanceadas, onde a principal diferença é a utilização de um sistema de cores preto e vermelho para o balanceamento. Elas também utilizam rotações para corrigir o balanço dos seus nós.

2- struct NO{

            int valor;

            struct NO *esquerdo;

            struct NO *direito;

            int cor;

};

Grupo 2: Edilson Leite (líder)
                  Micael Jordy
                  Rodrigo dos Santos
                  

3- o custo das operações na arvore Rubro-negra é semelhante à arvore AVL: O(n) pra busca total e O(log n) pra inserção, remoção e busca especifica.

4- a escolha do tipo de arvore a ser usada depende da função a ser executada; enquanto a arvore Rubro-negra tem maior eficiência em guardar Uma grande quantidade de dados, a AVL e mais útil para leitura de dados

Grupo 3: Gabriel Thiago (Líder)

                 Reinaldo Lima

                 Wesley Alves

                 Jeremias dos Santos

5- O uso de ponteiro para ponteiro na raiz da árvore rubro-negra, permite, caso seja necessária alguma operação na árvore, como uma rotação, a alteração do nó da raiz com uma maior facilidade.

6- Uma árvore rubro-negra é uma árvore binária, de busca e balanceada em que cada nó é constituído dos seguintes campos:

·         Cor: vermelho ou preto;

·         Dado: valor armazenado;

·         Esquerda, direita: ponteiros que apontam para a subárvore esquerda e direita, respectivamente;

·         Pai: ponteiro para o nó pai.

Porém, há algumas propriedades adicionais:

·         O campo pai da raiz aponta para nil;

·         Todo nó da árvore é vermelho ou é preto;

·         A raiz é preta;

·         Toda folha é preta;

·         Se um nó é vermelho, então ambos os filhos serão pretos;

·         Para todo nó, todos os caminhos do nó até as folhas descendentes contêm o mesmo número de nós pretos.

Grupo 4- Arthur Matheus

                  José Vitor

                 Wesley Brasil

7- Porque há uma propriedade em árvore rubro – negra em que nós vermelhos só podem ter filhos pretos, no entanto nós pretos podem possuir filhos pretos e vermelhos. E com base nessa propriedade, os nós nulos devem possuir a cor preta, para que possam ter filhos pretos e vermelhos.

8- Sim, porque seria menos complicado de se trabalhar com 1 bit do que um char ou string, e o uso de 1 bit como booleano economizaria espaço na memória.

 Grupo 5- Gabriel Carvalho

                   Erick Sousa

9-

10-

Não, pois o filho esquerdo (5) da raiz (8) deveria ser vermelho, mas não é.

CORREÇÃO

1. Questão 1 - Correta e completa.

2. Questão 2 - Correta e completa.

3. Questão 3 - Correta e completa.

4. Questão 4 - Correta mas poderia ser mais detalhada. Poderia ter explicado o porque da Rubro negra ser mais eficiente em inserção/remoção e a AVL mais eficiente em consultas.

5. Questão 5 - Correta e completa.

6. Questão 6 - Correta e completa. Colocou o ponteiro para o nó pai na definição, que não é obrigatório na implementação, mas não a torna errada.

7. Questão 7 - Incorreta. Pareceu entender o motivo de dar cor para as folhas (null) mas não soube como dizer. Se atrapalhou ao escrever que "os nós nulos devem possuir a cor preta, para que possam ter filhos pretos e vermelhos", mas creio que o motivo seja para que o pai sempre tenha dois filhos (no caso o null esquerdo e o null direito) e a cor deve ser preta para que o pai possa ser um nó vermelho se necessário.

8. Questão 8 - Correta e completa. Considerando uma linguagem que tenha o tipo booleano.

9. Questão 9 - Incorreta. Já na raiz quebra o critério que diz que "para todo nó, todos os caminhos do nó até as folhas descendentes contêm o mesmo número de nós pretos".

10. Questão 10 - Incorreta. Tornando o filho esquerdo da raiz um nó vermelho (como sugerido) o critério de que todo caminho de um nó até uma folha deve ter o mesmo número de nós pretos, seria quebrado.

Grupo B - Árvores Rubro-Negras - Aula Invertida

Grupo 6 – Marcelo Carvalho, Filipe Nascimento Almeida, Marcel Reinan, João Manoel Fidelis Santos:

1. Qual a relação entre as arvores AVL e as arvores rubro-negras?

 Ambas são um tipo de árvore binária balanceada, a diferença é que a árvore AVL usa a altura de suas sub-árvores, e a árvore rubro-negra utiliza um esquema de coloração de nós para manter o balanceamento da árvore.

2. Escreva a declaracao do registro, em C, para composicao de arvores rubro-negras?

struct no{

            int info;

            struct no *esq;

            struct no *dir;

 int cor;

};

Grupo 7 – Iury Patrick Góis Santos, Letícia Aragão de Freitas, Thiago Santos França, Vitor Neves Varjão:

3. Qual o custo das operações sobre arvores rubro-negras? (a) em inserções (b) em remoções (c) em consulta especifica (d) em consulta total.

O custo de todas as operações são Log(n), exceto a consulta total que é linear o(n)

4. Que critério usar para decidir se aplicar AVL ou rubro-negra numa aplicação? Justifique.

Se o objetivo for armazenamento de dados usa-se rubro negra, se for busca, usa-se AVL.

Grupo 8 – Glenio Andrade, Cristiano Lima, João Victor Andrade Rodrigues, Brenda Martins Barros de Almeida. 

5. Por que usar ponteiro para ponteiro para manter a raiz da arvore rubro-negra? Justifique.

O uso de um ponteiro para ponteiro é para o caso em que a raiz necessitar ser alterada, como nos processos de rebalanceamento.

6. Qual a definição de arvore rubro-negra?

É uma árvore binária de busca que contém um bit adicional em sua estrutura, o que indica a cor.

As propriedades são:

• Todo nó da árvore é vermelho ou preto;
• A raiz é preta;
• Toda folha (nil) é preta;
• Se um nó é vermelho, então ambos os filhos são pretos;
• Para todo nó, todos os caminhos do nó até as folhas descendentes contêm o mesmo número de nós pretos.

Grupo 9 – Mateus Cardoso da Silva, Natanael Oliveira Gois, Osni Mario Vieira Araujo:

7. Na implementação de arvore rubro-negra, por que definir a cor das folhas (null), ou seja, apontadores aterrados.

Devido a todo nó folha (null) ser preto, sendo esta terceira propriedade da árvore rubro negra que satisfaz e todos os caminhos a partir da raiz até qualquer folha passa pelo mesmo número de nós pretos.

8. A melhor forma de se implementar o campo cor na implementação dos nos de composição de arvores rubro-negras e por meio do tipo boolean? Justifique.

Sim, pois a função de mudança de cor trabalha com inversões constantemente, com uso de um tipo boolean esta operação de inversão torna-se bem mais fácil.



Grupo 10 – Carlos Gabriel Santos de Melo, Wendel Lima Oliveira, Dayvid Wesley Lopes dos Santos, Lucas Santana de Oliveira.

9. Apresentar a construção da arvore rubro-negra composta pelos itens 13 – 23 – 35 – 43 – 52 – 63 – 99.

Insere o nó 13 que é a raiz. Insere nó 23 a direita da raiz. Insere nó 35 a direita do nó 13.

10. A arvore dada eh rubro-negra? Justifique sua resposta.

Não pois o nó s, filho esquerdo da raiz é preto, mas deveria ser vermelho. 

CORREÇÃO:

1. Questão 1 - Correta e completa.

2. Questão 2 - Correta e completa.

3. Questão 3 - Contém erro. Apresentou a notação de forma incorreta (usou Log(n) quando deveria ser O(log n)), mas considerando como um erro ao digitar, a resposta foi correta.

4. Questão 4 - Correta mas poderia ser mais detalhada. Poderia ter explicado o porque da Rubro negra ser mais eficiente em inserção/remoção e a AVL mais eficiente em consultas.

5. Questão 5 - Correta mas poderia ser mais detalhada. Poderia ter dito o porque usar o ponteiro para ponteiro para essa alteração da raiz.

6. Questão 6 - Correta e completa.

7. Questão 7 - incorreta. A resposta foi confusa e usou um dos critérios para justificar a folha (null) ser preta, mas a árvore pode ser abstraída de forma a desconsiderar os ponteiros aterrados e sendo assim a resposta não justifica o motivo.

8. Questão 8 - Correta e completa. Considerando uma linguagem que tenha o tipo booleano.

9. Questão 9 - Incorreta. Já na raiz quebra o critério que diz que "para todo nó, todos os caminhos do nó até as folhas descendentes contêm o mesmo número de nós pretos".

10. Questão 10 - Incorreta. Tornando o filho esquerdo da raiz um nó vermelho (como sugerido) o critério de que todo caminho de um nó até uma folha deve ter o mesmo número de nós pretos, seria quebrado.

DINÂMICA - AULA INVERTIDA – ARVORES RUBRO-NEGRAS

U n i v e r s i d a d e F e d e r a l d e S e r g i p e

Centro de Ciencias Exatas e Tecnologia

Departamento de Computacao

Prof. Kenia Kodel

E s t r u t u r a d e D a d o s

AULA INVERTIDA – ARVORES RUBRO-NEGRAS

DINÂMICA – 1^o Dia – 0,5 ponto:

• Compor 10 grupos com, inicialmente, 3 alunos, cada. Quando todos os grupos completos, podem ser adicionado 1 aluno a cada gupo.
• Os grupos definem um líder que é responsável por orquestrar as discussões e registrar as respostas, em 20 minutos.
• Grupos de 01 a 05, formam grupo A, e definem 1 líder, reunem-se e cada grupo apresenta suas conclusões para os restantes, em 40 minutos. O mesmo vale para Grupos de 06 a 10, formando o Grupo B.

PARA GRUPOS DE TRABALHO 01, 06:

1. Qual a relacao entre as arvores AVL e as arvores rubro-negras?

2. Escreva a declaracao do registro, em C, para composicao de arvores rubro-negras?

PARA GRUPOS DE TRABALHO 02, 07:

3. Qual o custo das operacoes sobre arvores rubro-negras? (a) em insercoes (b) em remocoes (c) em consulta especifica (d) em consulta total.

4. Que criterio usar para decidir se aplicar AVL ou rubro-negra numa aplicacao? Justifique.

PARA GRUPOS DE TRABALHO 03, 08:

5. Por que usar ponteiro para ponteiro para manter a raiz da arvore rubro-negra? Justifique.

6. Qual a definicao de arvore rubro-negra?

PARA GRUPOS DE TRABALHO 04, 09:

7. Na implementacao de arvore rubro-negra, por que definir a cor das folhas (null), ou seja, apontadores aterrados.

8. A melhor forma de se implementar o campo cor na implementacao dos nos de composicao de arvores rubro-negras e por meio do tipo boolean? Justifique.

PARA GRUPOS DE TRABALHO 05, 10:

9. Apresentar a construcao da arvore rubro-negra composta pelos itens 13 – 23 – 35 – 43 – 52 – 63 – 99.

10. A arvore dada eh rubro-negra? Justifique sua resposta.

IMPORTANTE: nil equivale a aterrado.

DINÂMICA – 2^o Dia (até 21-jul) – 0,5 ponto:

• Líderes publicam as conclusões em EduBlog.
• Individualmente os alunos comentam a postagem do grupo alheio.