Algoritmos e estruturas de dados · Estruturas de dados · 6 min de leitura
Árvores e árvore binária de busca (BST)
Menores à esquerda, maiores à direita: a BST busca em O(log n) quando está equilibrada — e degenera em O(n) se você inserir em ordem. Percursos e árvores balanceadas.
Arraste para o lado para ver o diagrama inteiro.
A regra da BST
Em cada nó, tudo à esquerda é menor e tudo à direita é maior. Buscar, inserir e remover descem um caminho da raiz até uma folha: o custo é a altura da árvore. Equilibrada, a altura é cerca de log₂ n — um milhão de nós em uns 20 níveis.
Quando degenera
Inserir 1, 2, 3, 4… numa BST simples gera uma "árvore" que é uma lista torta: altura n, busca O(n). Por isso as bibliotecas usam árvores auto-balanceadas (rubro-negra no TreeMap do Java, AVL, B-trees nos índices dos bancos de dados).
Percursos
- Em ordem (esquerda, nó, direita): devolve os valores ordenados.
- Pré-ordem (nó primeiro): copiar ou serializar a árvore.
- Pós-ordem (nó por último): apagar ou calcular tamanhos de pastas.
- Por níveis: busca em largura com uma fila.
No código
final class No {
let valor: Int
var esq: No?, dir: No?
init(_ v: Int) { valor = v }
}
func inserir(_ raiz: No?, _ v: Int) -> No {
guard let r = raiz else { return No(v) }
if v < r.valor { r.esq = inserir(r.esq, v) } else { r.dir = inserir(r.dir, v) }
return r
}
func contem(_ raiz: No?, _ v: Int) -> Bool {
var atual = raiz
while let n = atual {
if v == n.valor { return true }
atual = v < n.valor ? n.esq : n.dir // descarta metade
}
return false
}A busca é iterativa (sem estourar a pilha numa árvore degenerada); a inserção recursiva é mais curta. Em produção, prefira uma estrutura balanceada pronta.
Em resumo
- Esquerda menor, direita maior.
- Custo = altura: O(log n) equilibrada, O(n) degenerada.
- Bibliotecas usam árvores balanceadas (TreeMap).
- Percurso em ordem devolve os valores ordenados.
- Índices de banco usam B-trees, a prima larga da BST.
Exercícios
Responda e confira na hora. Complexidades valem com ou sem espaços, como O(n log n).
-
Insira 8, 3, 10, 1 e 6 (nessa ordem) numa BST vazia. Qual é a raiz?
Ver a solução
Resposta: 8. O primeiro valor inserido vira a raiz e nunca sai de lá numa BST simples.
-
Qual o percurso em ordem dessa árvore? Escreva os números separados por vírgula.
Ver a solução
Resposta: 1, 3, 6, 8, 10. Em ordem visita esquerda, nó, direita — o resultado sai ordenado.
-
Inserindo 1, 2, 3, …, n em ordem numa BST simples, qual a complexidade de uma busca?
Ver a solução
Resposta: O(n). Cada valor vira filho direito do anterior: a árvore tem altura n, como uma lista.
Perguntar à IA
Monte um prompt pronto sobre Árvores e árvore binária de busca (BST) na sua linguagem e no seu caso, e abra num chat gratuito.
O prompt vai para o site que você escolher. Não cole senhas, tokens nem dados reais de clientes. Para Gemini e outros, copie e cole.