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.