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.