Depois de dominar as estruturas básicas (listas, dicionários, conjuntos) e a busca e ordenação clássicas, vem o nível que separa quem monta programas de quem projeta soluções: pilhas, filas, listas ligadas, árvores, grafos e tabelas hash, com os algoritmos que operam sobre elas. Este guia explica cada estrutura, quando usar qual e em que ordem estudar, sem matemática pesada. Para aprender tudo isso na prática, com um laboratório de algoritmos e projeto final, use o Curso de Lógica de Programação Avançado, que é gratuito e fecha a Trilha Lógica.
Resposta rápida
- As estruturas avançadas centrais são pilha, fila, lista ligada, árvore, grafo e tabela hash.
- Os algoritmos que operam nelas são BFS e DFS (percurso de grafos), merge sort e quick sort (ordenação) e backtracking e memoização.
- Recursão é o motor por trás da maioria: uma função que chama a si mesma até um caso base.
- Estude na ordem: primeiro as lineares, depois a tabela hash, depois árvores e, por fim, grafos.
Estruturas lineares: pilha, fila e lista ligada
Antes de mergulhar nas estruturas ramificadas, vale firmar as lineares, que guardam itens em sequência mas com regras de acesso próprias. A pilha segue o modelo LIFO: o último item a entrar é o primeiro a sair, como uma pilha de pratos onde você só pega o de cima. Ela é a estrutura do botão desfazer, do histórico de navegação e da forma como o próprio computador controla chamadas de função. A fila segue o oposto, FIFO: quem chega primeiro é atendido primeiro, como a fila do caixa. Serve para processar tarefas na ordem em que surgiram, de mensagens a impressões. Já a lista ligada encadeia elementos onde cada um aponta para o próximo, o que torna inserir e remover no meio barato, sem empurrar todos os vizinhos como uma lista comum faria. O custo é que você não pula direto para uma posição: precisa seguir os ponteiros. Entender ponteiro aqui é o que destrava as árvores e os grafos depois.
Tabela hash: a busca instantânea por trás do dicionário
Quando você usa um dicionário e a linguagem acha o valor de uma chave na hora, quem faz esse trabalho é a tabela hash. A ideia é elegante: uma função de hash converte a chave (um nome, um código) em um número que aponta direto para uma posição na memória. Guardar e recuperar vira acesso direto ao endereço, sem varrer item por item, por isso o custo médio é O(1), tempo constante mesmo com milhões de registros. O detalhe que todo estudante precisa conhecer são as colisões: às vezes duas chaves diferentes geram o mesmo endereço, e a estrutura resolve isso guardando os dois numa pequena lista naquele ponto ou procurando o próximo espaço livre. Saber que a tabela hash existe por baixo do dicionário explica por que buscar por chave é tão mais rápido que buscar por valor, e ajuda a escolher a estrutura certa em vez de varrer listas à toa.
Árvores: hierarquia e busca eficiente
A árvore organiza dados em hierarquia: um nó raiz que se ramifica em filhos, que por sua vez têm filhos, como um organograma ou a estrutura de pastas do computador. A mais estudada é a árvore binária de busca, em que cada nó tem no máximo dois filhos e vale uma regra simples: valores menores vão para a esquerda, maiores para a direita. Isso permite buscar, inserir e remover em cerca de O(log n) passos quando a árvore está equilibrada, muito mais rápido que percorrer uma lista. Percorrer uma árvore também tem seus métodos (em ordem, pré-ordem, pós-ordem), e cada um serve a um propósito, de listar valores ordenados a copiar a estrutura inteira. As árvores são o primeiro contato de verdade com recursão aplicada, porque percorrer uma árvore é naturalmente recursivo: para visitar um nó, você visita suas subárvores, que são árvores menores.
Altura, tipos de árvore binária, AVL, heap e trie
Na árvore binária, cada nó tem no máximo dois filhos, o esquerdo e o direito. A medida que mais cai em prova e em entrevista é a altura: o dicionário de algoritmos do NIST, o instituto de padrões dos Estados Unidos, a define como a maior distância de um nó até a raiz, de modo que a árvore com um nó só tem altura zero. O cálculo é recursivo: a altura de um nó é 1 mais a maior altura entre as duas subárvores.
class No:
def __init__(self, valor, esquerda=None, direita=None):
self.valor = valor
self.esquerda = esquerda
self.direita = direita
def altura(no):
if no is None:
return -1 # assim a árvore de um nó só tem altura 0
return 1 + max(altura(no.esquerda), altura(no.direita))
raiz = No(8, No(3, No(1), No(6)), No(10))
print(altura(raiz)) # 2: o caminho mais longo é 8, 3, 1Alguns livros contam nós em vez de arestas e chegam a um número uma unidade maior; na prova, siga a convenção do enunciado. Os tipos de árvore binária também têm nomes que variam entre autores: o NIST registra que alguns livros chamam de cheia a árvore que ele chama de perfeita. Na tabela, as três primeiras definições são as do NIST:
| Tipo | Regra |
|---|---|
| Cheia (full) | Todo nó tem zero ou dois filhos |
| Completa | Todos os níveis cheios, menos talvez o último, que é preenchido da esquerda para a direita |
| Perfeita | Todas as folhas na mesma profundidade e todo nó interno com dois filhos |
| Degenerada | Cada nó, menos a folha do fim, tem um filho só, e a árvore vira, na prática, uma lista |
| De busca (BST) | Menores à esquerda, maiores à direita, o que permite buscar sem percorrer tudo |
A árvore de busca tem um problema: se os valores chegam já em ordem, ela fica degenerada e a busca volta a ser lenta. A árvore AVL resolve isso. Segundo o verbete AVL tree do NIST, ela é uma árvore binária de busca balanceada em que, em todo nó, a altura das duas subárvores difere em no máximo um; quando uma inserção ou remoção quebra essa regra, a árvore se reorganiza com rotações, e busca, inserção e remoção ficam em O(log n). O nome vem dos criadores, os matemáticos soviéticos Georgii Adelson-Velskii e Evgenii Landis, que publicaram a estrutura em 1962.
O heap é outra árvore binária completa, com uma regra diferente: cada pai é menor ou igual aos filhos, no heap de mínimo, ou maior ou igual, no heap de máximo. A raiz guarda sempre o menor (ou o maior) valor, o que faz do heap a estrutura da fila de prioridade e do algoritmo heapsort. Em Python, o módulo heapq da biblioteca padrão monta o heap sobre uma lista comum, e a aula deque, heapq e bisect no Python mostra quando ele vale a pena.
A trie, ou árvore de prefixos, guarda palavras letra por letra: palavras que começam igual dividem o mesmo caminho a partir da raiz. É a estrutura do autocompletar e do corretor ortográfico, porque chegar ao ponto da árvore onde ficam todas as palavras com um prefixo custa o tamanho do prefixo, e não o total de palavras guardadas. O mesmo raciocínio de nós e ponteiros vale para o grafo, que solta a regra da hierarquia, como mostra a aula o que é um grafo, e para a tabela hash por dentro, tema de outro módulo do curso.
Quer aprender com prática guiada? O Curso de Lógica de Programação Avançado cobre pilhas, filas, árvores, grafos e tabelas hash com um laboratório de algoritmos, diagramas em cada aula, exercícios e um projeto final. É gratuito e continua a partir do nível intermediário.
Grafos: representando conexões com BFS e DFS
O grafo é a estrutura mais abstrata e uma das mais poderosas: ele representa coisas (os nós) e as relações entre elas (as arestas). Rede social, mapa de cidades com estradas, dependências entre tarefas, tudo isso é grafo. Diferente da árvore, um grafo pode ter ciclos e vários caminhos entre dois pontos, o que exige algoritmos para percorrê-lo sem se perder. Os dois fundamentais são a busca em largura (BFS), que explora primeiro todos os vizinhos próximos antes de ir fundo, usando uma fila, ideal para achar o caminho com menos passos; e a busca em profundidade (DFS), que segue um caminho até o fim antes de voltar, usando uma pilha ou recursão, boa para explorar todas as possibilidades ou detectar ciclos. Repare como as estruturas lineares reaparecem: BFS usa fila, DFS usa pilha. É por isso que se estuda tudo na ordem certa, cada peça sustenta a seguinte.
Algoritmos que amarram tudo: ordenação, backtracking e memoização
Com as estruturas na mão, alguns algoritmos merecem estudo próprio porque ensinam padrões que se repetem. O merge sort e o quick sort ordenam dados dividindo o problema em partes menores, resolvendo cada uma e juntando o resultado, a estratégia de dividir para conquistar, com custo O(n log n). O backtracking resolve problemas testando caminhos e voltando atrás quando um deles não leva a lugar nenhum, como montar um labirinto de decisões ou preencher um sudoku: é a base de quebra-cabeças e de buscas com restrição. Já a memoização guarda resultados de cálculos já feitos para não repetir trabalho, o que transforma soluções recursivas lentas em rápidas, um primeiro passo em direção à programação dinâmica. Os três têm a recursão como fio condutor, e é aí que aquele conceito de função que chama a si mesma finalmente mostra a que veio.
Como estudar estruturas avançadas na ordem certa
A sequência que rende começa pelas estruturas lineares (pilha, fila, lista ligada), porque elas firmam a ideia de ponteiro e de ordem de acesso. Em seguida vem a tabela hash, que conecta com o dicionário que você já domina do nível intermediário. Depois entram as árvores (binária de busca e os percursos), primeiro grande exercício de recursão aplicada. Por último, os grafos com BFS e DFS, que reúnem fila, pilha e recursão num só lugar. Os algoritmos de ordenação, backtracking e memoização se estudam junto das estruturas em que aparecem, nunca soltos. Estudar assim, um pouco por dia, com um diagrama para visualizar e código para testar, fixa muito mais que uma maratona. É exatamente essa progressão que o curso avançado de lógica segue, com laboratório e um projeto que junta tudo no fim.
Erros comuns de quem chega no nível avançado
O primeiro é tentar decorar implementações em vez de entender a ideia: você esquece o código, mas o raciocínio de dividir para conquistar ou de percorrer em largura fica para sempre. O segundo é ignorar a eficiência e escolher a estrutura errada por costume, como varrer uma lista quando uma tabela hash resolveria na hora. O terceiro é escrever recursão sem caso base claro, o que gera laços infinitos e estouro de pilha. O quarto é estudar grafos antes de firmar fila e pilha, e travar por falta de base. Conhecer esses tropeços de antemão poupa horas de frustração, e cada um deles vira um hábito melhor com prática guiada e feedback.
Estruturas de dados avançadas e seus algoritmos são o passo que transforma quem resolve exercícios em quem projeta sistemas, e o conteúdo aparece em entrevistas técnicas e em qualquer linguagem. Para aprender com método, laboratório de algoritmos e diagramas, continue pelo Curso de Lógica de Programação Avançado e, quando quiser conhecer os outros temas, veja todos os cursos gratuitos do ValorFinal.