Introdução
A Árvore de Busca Binária (Binary Search Tree ou BST) é uma árvore binária com uma propriedade fundamental: para cada nó, todos os valores na subárvore esquerda são menores e todos os valores na subárvore direita são maiores. Essa propriedade de ordenação permite buscas eficientes em O(log n) no caso médio, tornando a BST uma das estruturas de dados mais utilizadas em programação.
Em Rust, a implementação de uma BST nos permite exercitar conceitos como ownership de referências mutáveis, recursão com Box<T> e o trait Ord para comparação de valores. Neste artigo, construiremos uma BST completa com inserção, busca, remoção e verificaremos seus limites de desempenho.
Conceito e Teoria
A Propriedade BST
A regra fundamental é simples: esquerda < nó < direita, aplicada recursivamente a cada nó.
[50]
/ \
[30] [70]
/ \ / \
[20] [40][60] [80]
Propriedade verificada para cada nó:
- Nó 50: esq(30) < 50 < dir(70) ✓
- Nó 30: esq(20) < 30 < dir(40) ✓
- Nó 70: esq(60) < 70 < dir(80) ✓
Busca na BST
A busca é eficiente porque a cada comparação eliminamos metade da árvore:
Buscar o valor 40:
Passo 1: 40 < 50 → vai para esquerda
[50]
/
[30]
Passo 2: 40 > 30 → vai para direita
[30]
\
[40] ← Encontrado!
O Problema da Árvore Degenerada
Quando os elementos são inseridos em ordem crescente (ou decrescente), a BST degenera em uma lista encadeada:
Inserção: 10, 20, 30, 40, 50
[10] Árvore balanceada (ideal):
\ [30]
[20] / \
\ [10] [40]
[30] \ \
\ [20] [50]
[40]
\ Altura: 2 → O(log n)
[50]
Altura: 4 → O(n)
Esse é o motivo pelo qual árvores balanceadas (AVL, rubro-negra) foram inventadas.
Complexidade
| Operação | Caso Médio | Pior Caso (Degenerada) |
|---|---|---|
| Busca | O(log n) | O(n) |
| Inserção | O(log n) | O(n) |
| Remoção | O(log n) | O(n) |
| Mínimo/Máximo | O(log n) | O(n) |
| Travessia | O(n) | O(n) |
| Espaço | O(n) | O(n) |
Nota: O pior caso O(n) ocorre quando a árvore se torna degenerada. Para garantir O(log n) sempre, utilize árvores AVL ou rubro-negras.
Implementação em Rust
use std::fmt::Display;
/// Nó da árvore de busca binária
#[derive(Debug)]
struct No<T: Ord + Display + Clone> {
valor: T,
esquerda: Arvore<T>,
direita: Arvore<T>,
}
/// Tipo alias para a árvore (Option de Box)
type Arvore<T> = Option<Box<No<T>>>;
/// Árvore de Busca Binária
#[derive(Debug)]
struct BST<T: Ord + Display + Clone> {
raiz: Arvore<T>,
tamanho: usize,
}
impl<T: Ord + Display + Clone> BST<T> {
/// Cria uma BST vazia
fn nova() -> Self {
BST {
raiz: None,
tamanho: 0,
}
}
/// Retorna o número de elementos
fn tamanho(&self) -> usize {
self.tamanho
}
/// Verifica se a árvore está vazia
fn esta_vazia(&self) -> bool {
self.tamanho == 0
}
/// Insere um valor na BST
fn inserir(&mut self, valor: T) {
if Self::inserir_rec(&mut self.raiz, valor) {
self.tamanho += 1;
}
}
/// Inserção recursiva — retorna true se inseriu, false se já existia
fn inserir_rec(no: &mut Arvore<T>, valor: T) -> bool {
match no {
None => {
*no = Some(Box::new(No {
valor,
esquerda: None,
direita: None,
}));
true
}
Some(ref mut atual) => {
if valor < atual.valor {
Self::inserir_rec(&mut atual.esquerda, valor)
} else if valor > atual.valor {
Self::inserir_rec(&mut atual.direita, valor)
} else {
false // Valor duplicado, não insere
}
}
}
}
/// Busca um valor na BST
fn buscar(&self, valor: &T) -> bool {
Self::buscar_rec(&self.raiz, valor)
}
fn buscar_rec(no: &Arvore<T>, valor: &T) -> bool {
match no {
None => false,
Some(atual) => {
if *valor < atual.valor {
Self::buscar_rec(&atual.esquerda, valor)
} else if *valor > atual.valor {
Self::buscar_rec(&atual.direita, valor)
} else {
true // Encontrou
}
}
}
}
/// Retorna o menor valor da BST
fn minimo(&self) -> Option<&T> {
Self::minimo_rec(&self.raiz)
}
fn minimo_rec(no: &Arvore<T>) -> Option<&T> {
match no {
None => None,
Some(atual) => {
if atual.esquerda.is_none() {
Some(&atual.valor)
} else {
Self::minimo_rec(&atual.esquerda)
}
}
}
}
/// Retorna o maior valor da BST
fn maximo(&self) -> Option<&T> {
Self::maximo_rec(&self.raiz)
}
fn maximo_rec(no: &Arvore<T>) -> Option<&T> {
match no {
None => None,
Some(atual) => {
if atual.direita.is_none() {
Some(&atual.valor)
} else {
Self::maximo_rec(&atual.direita)
}
}
}
}
/// Remove um valor da BST
fn remover(&mut self, valor: &T) {
if Self::remover_rec(&mut self.raiz, valor) {
self.tamanho -= 1;
}
}
/// Remoção recursiva — trata os três casos:
/// 1. Nó folha: simplesmente remove
/// 2. Nó com um filho: substitui pelo filho
/// 3. Nó com dois filhos: substitui pelo sucessor in-order
fn remover_rec(no: &mut Arvore<T>, valor: &T) -> bool {
match no {
None => false,
Some(atual) => {
if *valor < atual.valor {
Self::remover_rec(&mut atual.esquerda, valor)
} else if *valor > atual.valor {
Self::remover_rec(&mut atual.direita, valor)
} else {
// Encontrou o nó a ser removido
if atual.esquerda.is_none() {
// Caso 1 ou 2: sem filho esquerdo
*no = atual.direita.take();
} else if atual.direita.is_none() {
// Caso 2: sem filho direito
*no = atual.esquerda.take();
} else {
// Caso 3: dois filhos — encontra o sucessor in-order
let sucessor = Self::extrair_minimo(&mut atual.direita);
atual.valor = sucessor;
}
true
}
}
}
}
/// Extrai (remove e retorna) o menor valor de uma subárvore
fn extrair_minimo(no: &mut Arvore<T>) -> T {
if no.as_ref().unwrap().esquerda.is_none() {
let removido = no.take().unwrap();
*no = removido.direita;
removido.valor
} else {
Self::extrair_minimo(&mut no.as_mut().unwrap().esquerda)
}
}
/// Travessia em ordem (produz valores em ordem crescente)
fn em_ordem(&self) -> Vec<T> {
let mut resultado = Vec::new();
Self::em_ordem_rec(&self.raiz, &mut resultado);
resultado
}
fn em_ordem_rec(no: &Arvore<T>, resultado: &mut Vec<T>) {
if let Some(atual) = no {
Self::em_ordem_rec(&atual.esquerda, resultado);
resultado.push(atual.valor.clone());
Self::em_ordem_rec(&atual.direita, resultado);
}
}
/// Calcula a altura da árvore
fn altura(&self) -> i32 {
Self::altura_rec(&self.raiz)
}
fn altura_rec(no: &Arvore<T>) -> i32 {
match no {
None => -1,
Some(atual) => {
let h_esq = Self::altura_rec(&atual.esquerda);
let h_dir = Self::altura_rec(&atual.direita);
1 + h_esq.max(h_dir)
}
}
}
}
/// Implementa Display para exibir a árvore em ordem
impl<T: Ord + Display + Clone> std::fmt::Display for BST<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let elementos = self.em_ordem();
let strs: Vec<String> = elementos.iter().map(|e| format!("{}", e)).collect();
write!(f, "[{}]", strs.join(", "))
}
}
fn main() {
let mut bst = BST::nova();
// Inserção de valores
let valores = vec![50, 30, 70, 20, 40, 60, 80];
for v in &valores {
bst.inserir(*v);
}
println!("BST em ordem: {}", bst);
println!("Tamanho: {}", bst.tamanho());
println!("Altura: {}", bst.altura());
println!("Mínimo: {:?}", bst.minimo());
println!("Máximo: {:?}", bst.maximo());
// Busca
println!("\nBuscar 40: {}", bst.buscar(&40));
println!("Buscar 25: {}", bst.buscar(&25));
// Remoção
println!("\n--- Remoção do nó 30 (dois filhos) ---");
bst.remover(&30);
println!("BST após remover 30: {}", bst);
println!("Tamanho: {}", bst.tamanho());
}
Métodos Principais
| Método | Descrição |
|---|---|
nova() | Cria uma BST vazia |
inserir(v) | Insere o valor v mantendo a propriedade BST |
buscar(v) | Retorna true se o valor existe na árvore |
remover(v) | Remove o valor v da árvore |
minimo() | Retorna referência ao menor valor (nó mais à esquerda) |
maximo() | Retorna referência ao maior valor (nó mais à direita) |
em_ordem() | Retorna vetor com elementos em ordem crescente |
altura() | Calcula a altura da árvore |
tamanho() | Retorna o número de elementos na árvore |
Os Três Casos da Remoção
Caso 1 — Nó folha (sem filhos):
[50] [50]
/ \ / \
[30] [70] → [30] [70]
/
[20] ← remover
Caso 2 — Nó com um filho:
[50] [50]
/ \ / \
[30] [70] → [20] [70]
/
[20]
↑ remover [30], substituir por [20]
Caso 3 — Nó com dois filhos:
[50] [50]
/ \ / \
[30] [70] → [40] [70]
/ \ /
[20][40] [20]
↑ remover [30], substituir pelo sucessor in-order [40]
Exemplo Prático: Dicionário / Agenda Telefônica
use std::fmt;
/// Entrada da agenda: nome e telefone
#[derive(Debug, Clone)]
struct Contato {
nome: String,
telefone: String,
}
impl Contato {
fn novo(nome: &str, telefone: &str) -> Self {
Contato {
nome: nome.to_string(),
telefone: telefone.to_string(),
}
}
}
impl fmt::Display for Contato {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}: {}", self.nome, self.telefone)
}
}
impl PartialEq for Contato {
fn eq(&self, other: &Self) -> bool {
self.nome == other.nome
}
}
impl Eq for Contato {}
impl PartialOrd for Contato {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Contato {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.nome.cmp(&other.nome)
}
}
fn main() {
let mut agenda = BST::nova(); // Usa a BST implementada acima
agenda.inserir(Contato::novo("Maria", "(11) 91234-5678"));
agenda.inserir(Contato::novo("Ana", "(21) 99876-5432"));
agenda.inserir(Contato::novo("Pedro", "(31) 98765-4321"));
agenda.inserir(Contato::novo("Carlos", "(41) 97654-3210"));
agenda.inserir(Contato::novo("Juliana", "(51) 96543-2109"));
println!("=== Agenda Telefônica (ordem alfabética) ===");
for contato in agenda.em_ordem() {
println!(" {}", contato);
}
// Busca pelo nome
let busca = Contato::novo("Pedro", "");
println!("\nPedro está na agenda? {}", agenda.buscar(&busca));
let busca = Contato::novo("Roberto", "");
println!("Roberto está na agenda? {}", agenda.buscar(&busca));
}
Comparação com Outras Estruturas
| Critério | BST (média) | HashMap | Vec Ordenado | Lista Encadeada |
|---|---|---|---|---|
| Busca | O(log n) | O(1)* | O(log n) | O(n) |
| Inserção | O(log n) | O(1)* | O(n) | O(1) |
| Remoção | O(log n) | O(1)* | O(n) | O(n) |
| Dados ordenados | Sim | Não | Sim | Não |
| Mínimo/Máximo | O(log n) | O(n) | O(1) | O(n) |
| Busca por intervalo | O(log n + k) | O(n) | O(log n + k) | O(n) |
* Amortizado, sem considerar colisões.
Quando usar BST?
- Use quando precisa de dados ordenados com inserção/remoção eficientes.
- Use quando precisa de operações como mínimo, máximo e busca por intervalo.
- Não use se a ordem dos dados não importa —
HashMapé mais rápido para busca pura. - Não use se os dados chegam em ordem — a BST degenerará. Prefira AVL ou rubro-negra.
Exercícios
Exercício 1: Verificar se é BST Válida
Escreva uma função eh_bst_valida(arvore) -> bool que verifique se uma árvore binária satisfaz a propriedade BST. Dica: use limites inferior e superior durante a recursão.
Exercício 2: k-ésimo Menor Elemento
Implemente um método k_esimo_menor(k) -> Option<T> que retorne o k-ésimo menor elemento da BST sem gerar o vetor completo. Use uma travessia in-order com um contador.
Exercício 3: Ancestral Comum Mais Baixo (LCA)
Dados dois valores a e b presentes na BST, encontre o ancestral comum mais baixo (Lowest Common Ancestor). Aproveite a propriedade BST: se ambos os valores são menores que o nó atual, o LCA está à esquerda; se ambos são maiores, está à direita; caso contrário, o nó atual é o LCA.
[50]
/ \
[30] [70]
/ \ / \
[20][40][60][80]
LCA(20, 40) = 30
LCA(20, 60) = 50
LCA(60, 80) = 70
Conclusão
A Árvore de Busca Binária é uma estrutura elegante que combina a eficiência da busca binária com a flexibilidade de inserção e remoção dinâmicas. Sua implementação em Rust nos ensina a trabalhar com tipos recursivos e o sistema de ownership de maneira prática.
No entanto, a BST tem uma fraqueza fundamental: sem balanceamento, sua performance pode degradar para O(n). Por isso, na prática, quase sempre usamos variantes balanceadas como árvores AVL ou rubro-negras. A BST é, porém, essencial como fundamento teórico — entender sua lógica é pré-requisito para compreender qualquer árvore balanceada. No próximo artigo, veremos como a árvore AVL resolve o problema de degeneração com rotações automáticas.