4. Árvore de Busca & Estrutura da Recursão
- Como a árvore de busca é estruturada
- Como a recursão se mapeia na árvore
- A relação entre profundidade e decisões
- Como a pilha de chamadas evolui durante a execução
- Por que o backtracking segue naturalmente DFS
Algoritmos de backtracking exploram uma estrutura conceitual: a árvore de busca.
Ao mesmo tempo, eles são implementados usando recursão. Entender como essas duas visões se alinham é essencial.
4.1 A árvore de busca
O espaço de busca de um problema de backtracking pode ser visualizado como uma árvore.
- A raiz representa a solução vazia
- Cada nível corresponde a uma decisão
- Cada aresta representa uma escolha
- Cada nó representa uma solução parcial
Um nó na profundidade i corresponde à sequência (x₁, …, xᵢ).
4.2 Profundidade e níveis de decisão
A profundidade de um nó na árvore corresponde diretamente ao número de decisões tomadas.
Se um problema possui n variáveis, a árvore tem no máximo n níveis.
4.3 Recursão como travessia da árvore
Cada chamada recursiva corresponde a um nó na árvore de busca.
- Entrar em uma chamada recursiva = descer na árvore
- Retornar de uma chamada = subir na árvore
Portanto, o algoritmo realiza uma travessia em profundidade (DFS) da árvore de busca.
4.4 A pilha de chamadas
A pilha de recursão armazena o caminho da raiz até o nó atual.
Em qualquer momento, a pilha contém:
- a solução parcial atual
- a sequência ativa de decisões
Profundidade da pilha = profundidade da árvore.
4.5 Por que backtracking usa DFS
O backtracking segue naturalmente uma estratégia em profundidade, pois explora um ramo completamente antes de tentar outro.
Isso é eficiente porque:
- usa pouca memória (apenas um caminho por vez)
- permite poda antecipada de ramos inválidos
4.6 Intuição visual
Você pode pensar no backtracking como:
- Descer em um caminho (fazendo escolhas)
- Encontrar um beco sem saída ou solução
- Voltar (desfazer)
- Tentar outro ramo
4.7 Por que isso importa
Entender essa estrutura é fundamental porque:
- explica como a recursão funciona internamente
- mostra como a poda reduz a complexidade
- ajuda a analisar desempenho
Sem esse modelo mental, o backtracking muitas vezes parece apenas “recursão mágica”.
Próximo: Parte 5 — Poda
Agora que entendemos a estrutura da busca, o próximo passo é torná-la eficiente.
Na Parte 5, estudamos como a poda elimina grandes partes da árvore de busca e melhora drasticamente o desempenho.