A Árvore Binária de Busca (Binary Search Tree, ou BST) é uma das estruturas de dados mais fundamentais da ciência da computação. Ela organiza elementos de forma hierárquica, onde cada nó possui no máximo dois filhos: o filho esquerdo contém valores menores e o filho direito contém valores maiores que o nó atual. Essa propriedade permite buscas, inserções e remoções em tempo O(log n) no caso médio.
Na prática, BSTs são a base para estruturas mais sofisticadas como árvores AVL, Red-Black Trees e B-Trees. Em Rust, a implementação de árvores é um excelente exercício para compreender o sistema de ownership, já que cada nó é proprietário de seus filhos por meio de Box<Node>, e a ausência de filhos é representada com Option.
Como Funciona
A BST mantém uma invariante fundamental: para qualquer nó com valor v, todos os valores na subárvore esquerda são menores que v, e todos os valores na subárvore direita são maiores que v.
Inserção dos valores: 50, 30, 70, 20, 40, 60, 80
Passo 1: Inserir 50 Passo 2: Inserir 30 Passo 3: Inserir 70
50 50 50
/ / \
30 30 70
Passo 4: Inserir 20 Passo 5: Inserir 40 Passo 6-7: Inserir 60, 80
50 50 50
/ \ / \ / \
30 70 30 70 30 70
/ / \ / \ / \
20 20 40 20 40 60 80
Busca pelo valor 40:
50 (40 < 50, vai para esquerda)
/ \
[30] 70 (40 > 30, vai para direita)
/ \
20 [40] ← Encontrado!
Travessia in-order (esquerda → nó → direita):
20 → 30 → 40 → 50 → 60 → 70 → 80 (valores em ordem crescente!)
A remoção é a operação mais complexa, com três casos:
Caso 1: Nó folha (sem filhos) — simplesmente remove
Caso 2: Nó com um filho — substitui pelo filho
Caso 3: Nó com dois filhos — substitui pelo sucessor in-order
Exemplo: Remover 30 (caso 3 — dois filhos)
50 50
/ \ / \
30 70 → 40 70
/ \ / \ / / \
20 40 60 80 20 60 80
(Substitui 30 pelo sucessor in-order: 40)
Complexidade
| Operação | Melhor/Médio | Pior Caso | Espaço |
|---|---|---|---|
| Busca | O(log n) | O(n) | O(n) |
| Inserção | O(log n) | O(n) | O(n) |
| Remoção | O(log n) | O(n) | O(n) |
| Travessia | O(n) | O(n) | O(n) |
| Mínimo/Máximo | O(log n) | O(n) | O(1) |
- Caso médio O(log n): quando a árvore está razoavelmente balanceada, cada operação percorre apenas a altura da árvore.
- Pior caso O(n): ocorre quando os elementos são inseridos em ordem crescente ou decrescente, degenerando a árvore em uma lista encadeada.
- Espaço O(n): cada elemento ocupa um nó na árvore, e a recursão pode usar O(h) espaço na pilha, onde h é a altura.
Implementação em Rust
A estrutura usa Option<Box<No<T>>> — um padrão idiomático em Rust para representar ponteiros opcionais a dados alocados no heap. O Box garante ownership exclusivo, e Option representa a possibilidade de ausência.
use std::fmt::Display;
/// Nó da árvore binária de busca.
/// Cada nó possui um valor e ponteiros opcionais para filhos esquerdo e direito.
#[derive(Debug)]
struct No<T: Ord + Display> {
valor: T,
esquerda: Option<Box<No<T>>>,
direita: Option<Box<No<T>>>,
}
impl<T: Ord + Display> No<T> {
/// Cria um novo nó folha.
fn novo(valor: T) -> Self {
No {
valor,
esquerda: None,
direita: None,
}
}
}
/// Árvore Binária de Busca.
#[derive(Debug)]
struct Bst<T: Ord + Display> {
raiz: Option<Box<No<T>>>,
}
impl<T: Ord + Display> Bst<T> {
/// Cria uma BST vazia.
fn nova() -> Self {
Bst { raiz: None }
}
/// Insere um valor na árvore. Valores duplicados são ignorados.
fn inserir(&mut self, valor: T) {
Self::inserir_rec(&mut self.raiz, valor);
}
fn inserir_rec(no: &mut Option<Box<No<T>>>, valor: T) {
match no {
None => {
*no = Some(Box::new(No::novo(valor)));
}
Some(ref mut n) => {
if valor < n.valor {
Self::inserir_rec(&mut n.esquerda, valor);
} else if valor > n.valor {
Self::inserir_rec(&mut n.direita, valor);
}
// Valores iguais são ignorados
}
}
}
/// Verifica se um valor existe na árvore.
fn buscar(&self, valor: &T) -> bool {
Self::buscar_rec(&self.raiz, valor)
}
fn buscar_rec(no: &Option<Box<No<T>>>, valor: &T) -> bool {
match no {
None => false,
Some(n) => {
if *valor == n.valor {
true
} else if *valor < n.valor {
Self::buscar_rec(&n.esquerda, valor)
} else {
Self::buscar_rec(&n.direita, valor)
}
}
}
}
/// Remove um valor da árvore, se existir.
fn remover(&mut self, valor: &T) {
Self::remover_rec(&mut self.raiz, valor);
}
fn remover_rec(no: &mut Option<Box<No<T>>>, valor: &T) {
if let Some(ref mut n) = no {
if *valor < n.valor {
Self::remover_rec(&mut n.esquerda, valor);
} else if *valor > n.valor {
Self::remover_rec(&mut n.direita, valor);
} else {
// Encontrou o nó a ser removido
match (n.esquerda.take(), n.direita.take()) {
// Caso 1: nó folha
(None, None) => {
*no = None;
}
// Caso 2: apenas filho esquerdo
(esq, None) => {
*no = esq;
}
// Caso 2: apenas filho direito
(None, dir) => {
*no = dir;
}
// Caso 3: dois filhos — encontrar o menor da subárvore direita
(esq, mut dir) => {
// Encontra o valor mínimo da subárvore direita (sucessor in-order)
let min = Self::extrair_minimo(&mut dir);
// Reconstrói o nó com o valor do sucessor
let mut novo_no = Box::new(No::novo(min));
novo_no.esquerda = esq;
novo_no.direita = dir;
*no = Some(novo_no);
}
}
}
}
}
/// Extrai (remove e retorna) o menor valor de uma subárvore.
fn extrair_minimo(no: &mut Option<Box<No<T>>>) -> T {
if no.as_ref().unwrap().esquerda.is_none() {
// Este é o menor — extraia-o
let removido = no.take().unwrap();
*no = removido.direita;
removido.valor
} else {
Self::extrair_minimo(&mut no.as_mut().unwrap().esquerda)
}
}
/// Retorna os elementos em ordem crescente (travessia in-order).
fn em_ordem(&self) -> Vec<&T> {
let mut resultado = Vec::new();
Self::em_ordem_rec(&self.raiz, &mut resultado);
resultado
}
fn em_ordem_rec<'a>(no: &'a Option<Box<No<T>>>, resultado: &mut Vec<&'a T>) {
if let Some(n) = no {
Self::em_ordem_rec(&n.esquerda, resultado);
resultado.push(&n.valor);
Self::em_ordem_rec(&n.direita, resultado);
}
}
/// Retorna o menor valor da árvore.
fn minimo(&self) -> Option<&T> {
let mut atual = &self.raiz;
let mut min = None;
while let Some(n) = atual {
min = Some(&n.valor);
atual = &n.esquerda;
}
min
}
/// Retorna o maior valor da árvore.
fn maximo(&self) -> Option<&T> {
let mut atual = &self.raiz;
let mut max = None;
while let Some(n) = atual {
max = Some(&n.valor);
atual = &n.direita;
}
max
}
/// Retorna a altura da árvore (0 para árvore vazia).
fn altura(&self) -> usize {
Self::altura_rec(&self.raiz)
}
fn altura_rec(no: &Option<Box<No<T>>>) -> usize {
match no {
None => 0,
Some(n) => {
let h_esq = Self::altura_rec(&n.esquerda);
let h_dir = Self::altura_rec(&n.direita);
1 + h_esq.max(h_dir)
}
}
}
}
fn main() {
let mut arvore = Bst::nova();
// Inserindo valores
for v in [50, 30, 70, 20, 40, 60, 80] {
arvore.inserir(v);
}
println!("Em ordem: {:?}", arvore.em_ordem());
println!("Altura: {}", arvore.altura());
println!("Mínimo: {:?}", arvore.minimo());
println!("Máximo: {:?}", arvore.maximo());
// Busca
println!("\nBuscar 40: {}", arvore.buscar(&40));
println!("Buscar 45: {}", arvore.buscar(&45));
// Remoção
arvore.remover(&30);
println!("\nApós remover 30: {:?}", arvore.em_ordem());
arvore.remover(&50);
println!("Após remover 50: {:?}", arvore.em_ordem());
}
Exemplo de Execução
Em ordem: [20, 30, 40, 50, 60, 70, 80]
Altura: 3
Mínimo: Some(20)
Máximo: Some(80)
Buscar 40: true
Buscar 45: false
Após remover 30: [20, 40, 50, 60, 70, 80]
Após remover 50: [20, 40, 60, 70, 80]
Trace detalhado da remoção de 30:
Árvore antes da remoção de 30:
50
/ \
30 70
/ \ / \
20 40 60 80
Passo 1: 30 < 50, desce para esquerda
Passo 2: 30 == 30, encontrou o nó
Passo 3: Nó tem dois filhos (20 e 40)
Passo 4: Encontrar sucessor in-order (menor da subárvore direita)
Subárvore direita de 30 = 40 (folha, é o menor)
Passo 5: Substituir 30 por 40
Árvore após remoção:
50
/ \
40 70
/ / \
20 60 80
Variações e Otimizações
1. Travessia Pré-Ordem e Pós-Ordem
Além da travessia in-order, as travessias pré-ordem e pós-ordem são úteis para serialização e destruição da árvore, respectivamente.
use std::fmt::Display;
struct No<T: Ord + Display> {
valor: T,
esquerda: Option<Box<No<T>>>,
direita: Option<Box<No<T>>>,
}
impl<T: Ord + Display> No<T> {
fn novo(valor: T) -> Self {
No { valor, esquerda: None, direita: None }
}
}
/// Travessia pré-ordem: nó → esquerda → direita
/// Útil para serializar e reconstruir a árvore.
fn pre_ordem<T: Ord + Display>(no: &Option<Box<No<T>>>, resultado: &mut Vec<String>) {
if let Some(n) = no {
resultado.push(format!("{}", n.valor));
pre_ordem(&n.esquerda, resultado);
pre_ordem(&n.direita, resultado);
}
}
/// Travessia pós-ordem: esquerda → direita → nó
/// Útil para liberar memória (bottom-up).
fn pos_ordem<T: Ord + Display>(no: &Option<Box<No<T>>>, resultado: &mut Vec<String>) {
if let Some(n) = no {
pos_ordem(&n.esquerda, resultado);
pos_ordem(&n.direita, resultado);
resultado.push(format!("{}", n.valor));
}
}
fn main() {
// Construção manual para demonstração
let arvore = Some(Box::new(No {
valor: 50,
esquerda: Some(Box::new(No {
valor: 30,
esquerda: Some(Box::new(No::novo(20))),
direita: Some(Box::new(No::novo(40))),
})),
direita: Some(Box::new(No {
valor: 70,
esquerda: Some(Box::new(No::novo(60))),
direita: Some(Box::new(No::novo(80))),
})),
}));
let mut pre = Vec::new();
pre_ordem(&arvore, &mut pre);
println!("Pré-ordem: {}", pre.join(", "));
let mut pos = Vec::new();
pos_ordem(&arvore, &mut pos);
println!("Pós-ordem: {}", pos.join(", "));
}
2. BST Iterativa (Busca sem Recursão)
Para evitar o consumo de pilha em árvores muito profundas, podemos implementar a busca iterativamente.
use std::fmt::Display;
struct No<T: Ord + Display> {
valor: T,
esquerda: Option<Box<No<T>>>,
direita: Option<Box<No<T>>>,
}
/// Busca iterativa — não consome pilha de chamadas.
fn buscar_iterativo<T: Ord + Display>(raiz: &Option<Box<No<T>>>, alvo: &T) -> bool {
let mut atual = raiz;
while let Some(no) = atual {
if *alvo == no.valor {
return true;
} else if *alvo < no.valor {
atual = &no.esquerda;
} else {
atual = &no.direita;
}
}
false
}
fn main() {
let arvore = Some(Box::new(No {
valor: 50,
esquerda: Some(Box::new(No {
valor: 30,
esquerda: None,
direita: None,
})),
direita: Some(Box::new(No {
valor: 70,
esquerda: None,
direita: None,
})),
}));
println!("Buscar 30: {}", buscar_iterativo(&arvore, &30));
println!("Buscar 99: {}", buscar_iterativo(&arvore, &99));
}
3. Contagem de Nós e Verificação de BST
use std::fmt::Display;
struct No<T: Ord + Display> {
valor: T,
esquerda: Option<Box<No<T>>>,
direita: Option<Box<No<T>>>,
}
/// Conta o número total de nós na árvore.
fn contar_nos<T: Ord + Display>(no: &Option<Box<No<T>>>) -> usize {
match no {
None => 0,
Some(n) => 1 + contar_nos(&n.esquerda) + contar_nos(&n.direita),
}
}
/// Verifica se uma árvore binária é realmente uma BST válida.
fn eh_bst_valida<T: Ord + Display>(no: &Option<Box<No<T>>>, min: Option<&T>, max: Option<&T>) -> bool {
match no {
None => true,
Some(n) => {
if let Some(min_val) = min {
if n.valor <= *min_val {
return false;
}
}
if let Some(max_val) = max {
if n.valor >= *max_val {
return false;
}
}
eh_bst_valida(&n.esquerda, min, Some(&n.valor))
&& eh_bst_valida(&n.direita, Some(&n.valor), max)
}
}
}
fn main() {
let arvore = Some(Box::new(No {
valor: 50,
esquerda: Some(Box::new(No {
valor: 30,
esquerda: Some(Box::new(No { valor: 20, esquerda: None, direita: None })),
direita: Some(Box::new(No { valor: 40, esquerda: None, direita: None })),
})),
direita: Some(Box::new(No {
valor: 70,
esquerda: None,
direita: None,
})),
}));
println!("Total de nós: {}", contar_nos(&arvore));
println!("É BST válida: {}", eh_bst_valida(&arvore, None, None));
}
Aplicações Práticas
- Dicionários e conjuntos ordenados: BSTs são a base interna de
BTreeMapeBTreeSetna biblioteca padrão do Rust (embora estas usem B-Trees, não BSTs binárias simples). - Autocompletar: armazenar palavras em uma BST permite encontrar rapidamente sugestões em um intervalo lexicográfico.
- Bancos de dados: índices de bancos de dados relacionais frequentemente usam variantes de árvores de busca para localizar registros rapidamente.
- Sistemas de arquivos: diretórios podem ser organizados em árvores para busca eficiente por nome.
- Agendadores de processos: o Linux CFS (Completely Fair Scheduler) usa uma Red-Black Tree (variante balanceada de BST) para gerenciar processos.
Comparação com Alternativas
| Característica | BST | Árvore AVL | Tabela Hash | Vec ordenado |
|---|---|---|---|---|
| Busca (médio) | O(log n) | O(log n) | O(1) | O(log n) |
| Inserção (médio) | O(log n) | O(log n) | O(1) | O(n) |
| Remoção (médio) | O(log n) | O(log n) | O(1) | O(n) |
| Pior caso busca | O(n) | O(log n) | O(n) | O(log n) |
| Ordenação | Sim (in-order) | Sim (in-order) | Não | Sim |
| Consulta de faixa | Sim | Sim | Não | Sim |
| Implementação | Simples | Complexa | Média | Simples |
A BST simples é ideal para aprendizado, mas para uso em produção, prefira estruturas balanceadas como AVL ou Red-Black Trees para garantir O(log n) no pior caso.
Exercícios Práticos
K-ésimo menor elemento: Implemente uma função que encontre o k-ésimo menor elemento da BST sem converter para vetor. Dica: faça uma travessia in-order com contador.
Ancestral comum mais baixo (LCA): Dados dois valores presentes na BST, encontre o ancestral comum mais baixo (Lowest Common Ancestor). Dica: se ambos são menores que o nó atual, vá para a esquerda; se ambos são maiores, vá para a direita; caso contrário, o nó atual é o LCA.
Serialização e desserialização: Implemente funções para converter a BST em uma
String(usando pré-ordem) e reconstruir a árvore a partir dessa string. Isso é útil para persistência em disco.Balanceamento: Dada uma BST possivelmente desbalanceada, implemente uma função que a converta em uma BST balanceada. Dica: extraia os elementos em ordem (vetor ordenado) e reconstrua a árvore dividindo o vetor ao meio recursivamente.
Veja Também
- Árvore AVL em Rust — BST auto-balanceada com rotações
- Tabela Hash do Zero em Rust — alternativa O(1) quando não é necessário ordenação
- Box — Alocação no Heap — como Rust gerencia dados no heap
- Option — Valores Opcionais — representação de presença/ausência
- Vec — Vetores Dinâmicos — estrutura usada nas travessias
- Eq e Ord — Comparação e Ordenação — traits necessárias para comparação de elementos