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.