Árvores Binárias
Definição
Uma árvore binária é uma estrutura de dados hierárquica onde cada nó possui no máximo dois filhos, chamados de filho à esquerda e filho à direita. Ela é amplamente utilizada em algoritmos de ordenação, busca e representação de expressões matemáticas ou lógicas.
Inserção e Busca
Em uma árvore binária de busca (Binary Search Tree — BST), os elementos são organizados de forma que, para qualquer nó:
- Todos os valores da subárvore esquerda são menores que o valor do nó;
- Todos os valores da subárvore direita são maiores que o valor do nó.
Essa propriedade permite realizar buscas eficientes com complexidade média de tempo:
\[ \mathcal{O}(\log n) \]
No entanto, no pior caso (árvore degenerada, como uma lista encadeada), a complexidade pode se tornar:
\[ \mathcal{O}(n) \]
Percursos (Traversals)
Os principais tipos de percurso em árvores binárias são:
➤ Em ordem (in-order)
Percorre a subárvore esquerda, visita o nó atual e depois a subárvore direita. Em uma BST, esse percurso retorna os valores em ordem crescente.
➤ Pré-ordem (pre-order)
Visita o nó atual, depois percorre a subárvore esquerda e em seguida a direita. Útil para copiar árvores e gerar prefixos de expressões.
➤ Pós-ordem (post-order)
Percorre a subárvore esquerda, depois a direita e, por fim, visita o nó atual. Útil para liberar memória ou gerar sufixos de expressões.
Esses percursos são tipicamente implementados de forma recursiva, mas também podem ser feitos de forma iterativa com uso de pilhas.