---
title: "Árvore Binária de Busca (BST) em Rust"
url: "https://rustlang.com.br/algoritmos/binary-search-tree/"
markdown_url: "https://rustlang.com.br/algoritmos/binary-search-tree.MD"
description: "Implemente uma Árvore Binária de Busca em Rust com inserção, busca, remoção e travessia in-order. Diagramas visuais e análise Big-O."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Árvore Binária de Busca (BST) em Rust

Implemente uma Árvore Binária de Busca em Rust com inserção, busca, remoção e travessia in-order. Diagramas visuais e análise Big-O.


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`.

```text
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:

```text
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.

```rust
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

```text
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:

```text
Á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.

```rust
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.

```rust
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

```rust
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 `BTreeMap` e `BTreeSet` na 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](/algoritmos/avl-tree/) | [Tabela Hash](/algoritmos/hash-table/) | 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

1. **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.

2. **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.

3. **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.

4. **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](/algoritmos/avl-tree/) — BST auto-balanceada com rotações
- [Tabela Hash do Zero em Rust](/algoritmos/hash-table/) — alternativa O(1) quando não é necessário ordenação
- [Box — Alocação no Heap](/stdlib/box-t/) — como Rust gerencia dados no heap
- [Option — Valores Opcionais](/stdlib/option/) — representação de presença/ausência
- [Vec — Vetores Dinâmicos](/stdlib/vec/) — estrutura usada nas travessias
- [Eq e Ord — Comparação e Ordenação](/stdlib/eq-ord/) — traits necessárias para comparação de elementos