Tarefa 6: AVL

Dando continuidade às tarefas de MC202, vou comentar sobre o laboratório 6, que consistia em implementar uma árvore AVL.

A árvore AVL é uma árvore binária balanceada de busca. Isso garante que a altura da árvore fica em torno de log n, onde n é o número de elementos na árvore. Tal propriedade é que possibilita busca, insersão e remocão em tempo log n. Porém, para mantear a árvore balanceada são necessárias operações chamadas de rotação (esquerda ou direita), o que torna a implementação de tal estrutura relativamente complexa.

Considerando que o laboratório pudesse ser complicado demais para se fazer em duas semanas, decidi fornecer um conjunto de cabeçalhos das funções, mais a estrutura da árvore para guiar os alunos na implementação. Isso ainda serve para evitar que os alunos enviassem código pronto copiado da internet, uma vez que dificilmente haverá um código que utiliza a mestra estrutura que eu defini.

Além do mais, optei por cobrar apenas a insersão na árvore, ficando os alunos incumbidos de implementar as rotações. A deleção me pareceu complicada demais a primeira vista e preferi não exigir.

O resultado foi melhor do que eu esperava. O número de submissões que vinha decrescendo a cada laboratório, voltou a atingir 40 (lembrando que para a tarefa Python, esse número fora 27). A minha impressão é de que uma boa parte da dificuldade dos alunos menos experientes é definir as estruturas e funções que servirão de base para a implementação. Ao fornecer a estrutura básica, deixei a eles apenas o trabalho de aplicar os algoritmos da teoria.

O único porém é que uma das minhas funções consistia em, dado um nó i, calcular a altura da subárvore a partir dele. Como havia um campo altura na estrutura do nó, minha ideia era, sempre que houvesse algum tipo de rotação envolvendo i, atualizar sua altura com o máximo da altura do filho esquerdo e do filho direito mais um. Só que essa função deveria ser O(1), uma vez que já temos calculado os valores das alturas do filho esquerdo e direito (hipótese). O problema é que a maior parte dos alunos calculou tal altura recursivamente, chamando a função novamente tanto para o filho esquerdo quanto para o direito, e isso torna a complexidade O(n), o que inutiliza a eficiência da inserção, que era O(log n).

Apesar de tudo, fiquei satisfeito com o resultado e sinto que desta forma os alunos focam mais em entender e aplicar a teoria do que desenvolvimento de sofware. Entretanto essa última habilidade é igualmente importante e deve ser trabalhada. No próximo laboratório, optei por um esquema parecido com o da AVL, mas pretendo deixar a implementação do último trabalho, o qual ainda não defini.

Os comentários estão fechados.

%d bloggers like this: