TAD Dicionário: AVL vs Lista Encadeada

Projeto didático em C (C99) que implementa o Tipo Abstrato de Dados (TAD) Dicionário de duas maneiras e as compara:

1. Árvore AVL (avl.c) — árvore binária de busca balanceada.
2. Lista encadeada simples (lista.c) — a abordagem mais direta possível.

O que é o TAD Dicionário

Um dicionário (ou mapa) é uma coleção de pares chave → valor, em que cada chave é única. Como num dicionário de verdade: a palavra é a chave e a definição é o valor. Aqui chave e valor são strings.

Operações da interface (dicionario.h):

Operação	Descrição
dic_criar	cria um dicionário vazio
dic_destruir	libera toda a memória
dic_inserir	insere o par; se a chave já existe, atualiza o valor
dic_buscar	retorna o valor de uma chave (ou NULL)
dic_remover	remove uma chave (retorna 1 se removeu, 0 se não havia)
dic_tamanho	número de pares armazenados
dic_imprimir	imprime todos os pares
dic_nome_impl	nome da implementação ("AVL" ou "Lista encadeada")

O tipo Dicionario é opaco: quem usa não enxerga os campos internos. Por isso a mesma interface tem duas implementações intercambiáveis, e tanto os testes quanto o benchmark são escritos uma única vez e compilados contra cada implementação. Esse é o ponto central da ideia de TAD.

Comparação das implementações

Operação	AVL	Lista encadeada
Buscar	O(log n)	O(n)
Inserir	O(log n)	O(n)¹
Remover	O(log n)	O(n)
Espaço	O(n)	O(n)

¹ A lista insere o nó novo em O(1), mas precisa varrer a lista (O(n)) para verificar se a chave já existe e, nesse caso, atualizar o valor.

Vantagem extra da AVL: o percurso em-ordem visita as chaves em ordem alfabética, então dic_imprimir sai ordenado. Na lista, sai na ordem interna de armazenamento.

A lista é muito mais simples de escrever e entender — boa para poucos elementos. A AVL é mais elaborada (rotações, balanceamento), mas escala muito melhor.

Como compilar e rodar

Requer um compilador C e make.

# Compila e roda os testes funcionais nas DUAS implementações:
make test

# Compila e roda os benchmarks de desempenho nas duas:
make bench

# Compila tudo sem rodar:
make

# Remove os binários gerados:
make clean

Binários gerados: testes_avl, testes_lista, bench_avl, bench_lista.

Resultados esperados do benchmark

make bench imprime, para cada implementação, uma tabela com os tempos de inserção, busca e remoção para N = 1.000, 5.000, 10.000 e 50.000.

• Na AVL, ao multiplicar N por 10 os tempos crescem pouco (fator ~log).
• Na lista, os tempos de busca e remoção crescem aproximadamente com N² no total (cada operação é O(n), e fazemos N delas), ficando ordens de grandeza mais lenta para N grande.

Isso evidencia, na prática, a diferença entre O(log n) e O(n).

Verificação de memória (opcional)

Para confirmar que não há vazamentos:

valgrind ./testes_avl
valgrind ./testes_lista

Arquivos

Arquivo	Conteúdo
dicionario.h	interface do TAD (tipo opaco + operações)
avl.c	implementação como árvore AVL
lista.c	implementação como lista encadeada simples
testes.c	casos de teste funcionais (usam só a interface)
benchmark.c	medição de desempenho
Makefile	alvos de compilação e execução