A Árvore AVL (nomeada em homenagem aos inventores Adelson-Velsky e Landis, 1962) é uma árvore binária de busca auto-balanceada. A diferença fundamental em relação a uma BST simples é que a AVL garante que, para todo nó, a diferença de altura entre as subárvores esquerda e direita (chamada fator de balanceamento) nunca exceda 1 em valor absoluto. Isso garante operações em O(log n) mesmo no pior caso.
Enquanto uma BST comum pode degenerar em uma lista encadeada (O(n) por operação) ao receber inserções ordenadas, a AVL realiza rotações para manter o equilíbrio estrutural. Essas rotações são operações locais que reorganizam no máximo três nós, mantendo a propriedade de BST.
Como Funciona
O fator de balanceamento de um nó é definido como altura(esquerda) - altura(direita). Quando esse fator se torna -2 ou +2 após uma inserção ou remoção, a árvore realiza uma das quatro rotações possíveis.
Fator de balanceamento (FB):
FB = altura(esquerda) - altura(direita)
Válido: -1, 0, +1
Desbalanceado: -2 ou +2
=== Rotação Simples à Direita (LL - Left-Left) ===
Ocorre quando FB = +2 e o filho esquerdo tem FB >= 0
30 (FB=+2) 20
/ / \
20 (FB=+1) → 10 30
/
10
=== Rotação Simples à Esquerda (RR - Right-Right) ===
Ocorre quando FB = -2 e o filho direito tem FB <= 0
10 (FB=-2) 20
\ / \
20 (FB=-1) → 10 30
\
30
=== Rotação Dupla Esquerda-Direita (LR - Left-Right) ===
Ocorre quando FB = +2 e o filho esquerdo tem FB = -1
30 (FB=+2) 30 25
/ / / \
20 (FB=-1) → 25 → 20 30
\ /
25 20
Primeiro rotação à esquerda em 20, depois rotação à direita em 30.
=== Rotação Dupla Direita-Esquerda (RL - Right-Left) ===
Ocorre quando FB = -2 e o filho direito tem FB = +1
10 (FB=-2) 10 15
\ \ / \
20 (FB=+1) → 15 → 10 20
/ \
15 20
Primeiro rotação à direita em 20, depois rotação à esquerda em 10.
Exemplo completo de inserções com rebalanceamento:
Inserir: 30, 20, 10, 25, 28
Passo 1: 30 Passo 2: 30 Passo 3: 30 (FB=+2)
/ /
20 20
/
10
Rotação LL → 20
/ \
10 30
Passo 4: Inserir 25 Passo 5: Inserir 28
20 20
/ \ / \
10 30 10 30
/ /
25 25 (FB=-1)
\
OK (balanceado) 28
30 tem FB=+2, filho esq 25 tem FB=-1
→ Rotação LR
20
/ \
10 28
/ \
25 30
Complexidade
| Operação | Tempo | Espaço |
|---|---|---|
| Busca | O(log n) | O(log n) |
| Inserção | O(log n) | O(log n) |
| Remoção | O(log n) | O(log n) |
| Travessia | O(n) | O(n) |
| Rotação | O(1) | O(1) |
- Garantia O(log n): a altura de uma AVL com n nós é sempre no máximo ~1.44 * log2(n), garantindo desempenho logarítmico mesmo no pior caso.
- Espaço O(log n): refere-se ao espaço da pilha de recursão durante operações. O espaço total da árvore é O(n).
- Overhead por nó: cada nó armazena a altura (um inteiro extra), consumindo memória adicional em comparação com uma BST simples.
Implementação em Rust
use std::cmp::max;
use std::fmt::Display;
/// Nó da árvore AVL com campo de altura para cálculo do fator de balanceamento.
#[derive(Debug)]
struct No<T: Ord + Display> {
valor: T,
altura: i32,
esquerda: Option<Box<No<T>>>,
direita: Option<Box<No<T>>>,
}
impl<T: Ord + Display> No<T> {
fn novo(valor: T) -> Self {
No {
valor,
altura: 1,
esquerda: None,
direita: None,
}
}
}
/// Árvore AVL auto-balanceada.
struct Avl<T: Ord + Display> {
raiz: Option<Box<No<T>>>,
}
/// Retorna a altura de um nó (0 se None).
fn altura<T: Ord + Display>(no: &Option<Box<No<T>>>) -> i32 {
no.as_ref().map_or(0, |n| n.altura)
}
/// Calcula o fator de balanceamento de um nó.
fn fator_balanceamento<T: Ord + Display>(no: &Box<No<T>>) -> i32 {
altura(&no.esquerda) - altura(&no.direita)
}
/// Atualiza a altura de um nó com base nos filhos.
fn atualizar_altura<T: Ord + Display>(no: &mut Box<No<T>>) {
no.altura = 1 + max(altura(&no.esquerda), altura(&no.direita));
}
/// Rotação simples à direita (LL).
fn rotacao_direita<T: Ord + Display>(mut raiz: Box<No<T>>) -> Box<No<T>> {
let mut nova_raiz = raiz.esquerda.take().expect("Filho esquerdo necessário");
raiz.esquerda = nova_raiz.direita.take();
atualizar_altura(&mut raiz);
nova_raiz.direita = Some(raiz);
atualizar_altura(&mut nova_raiz);
nova_raiz
}
/// Rotação simples à esquerda (RR).
fn rotacao_esquerda<T: Ord + Display>(mut raiz: Box<No<T>>) -> Box<No<T>> {
let mut nova_raiz = raiz.direita.take().expect("Filho direito necessário");
raiz.direita = nova_raiz.esquerda.take();
atualizar_altura(&mut raiz);
nova_raiz.esquerda = Some(raiz);
atualizar_altura(&mut nova_raiz);
nova_raiz
}
/// Rebalanceia um nó se necessário.
fn balancear<T: Ord + Display>(mut no: Box<No<T>>) -> Box<No<T>> {
atualizar_altura(&mut no);
let fb = fator_balanceamento(&no);
// Caso LL: desbalanceado à esquerda, filho esquerdo pendendo à esquerda
if fb > 1 && fator_balanceamento(no.esquerda.as_ref().unwrap()) >= 0 {
return rotacao_direita(no);
}
// Caso RR: desbalanceado à direita, filho direito pendendo à direita
if fb < -1 && fator_balanceamento(no.direita.as_ref().unwrap()) <= 0 {
return rotacao_esquerda(no);
}
// Caso LR: desbalanceado à esquerda, filho esquerdo pendendo à direita
if fb > 1 && fator_balanceamento(no.esquerda.as_ref().unwrap()) < 0 {
let esq = no.esquerda.take().unwrap();
no.esquerda = Some(rotacao_esquerda(esq));
return rotacao_direita(no);
}
// Caso RL: desbalanceado à direita, filho direito pendendo à esquerda
if fb < -1 && fator_balanceamento(no.direita.as_ref().unwrap()) > 0 {
let dir = no.direita.take().unwrap();
no.direita = Some(rotacao_direita(dir));
return rotacao_esquerda(no);
}
no // Já está balanceado
}
impl<T: Ord + Display> Avl<T> {
/// Cria uma árvore AVL vazia.
fn nova() -> Self {
Avl { raiz: None }
}
/// Insere um valor na árvore, mantendo o balanceamento.
fn inserir(&mut self, valor: T) {
self.raiz = Self::inserir_rec(self.raiz.take(), valor);
}
fn inserir_rec(no: Option<Box<No<T>>>, valor: T) -> Option<Box<No<T>>> {
let mut no = match no {
None => return Some(Box::new(No::novo(valor))),
Some(n) => n,
};
if valor < no.valor {
no.esquerda = Self::inserir_rec(no.esquerda.take(), valor);
} else if valor > no.valor {
no.direita = Self::inserir_rec(no.direita.take(), valor);
} else {
return Some(no); // Valor duplicado, ignora
}
Some(balancear(no))
}
/// Busca um valor na árvore.
fn buscar(&self, valor: &T) -> bool {
let mut atual = &self.raiz;
while let Some(no) = atual {
if *valor == no.valor {
return true;
} else if *valor < no.valor {
atual = &no.esquerda;
} else {
atual = &no.direita;
}
}
false
}
/// Remove um valor da árvore, mantendo o balanceamento.
fn remover(&mut self, valor: &T) {
self.raiz = Self::remover_rec(self.raiz.take(), valor);
}
fn remover_rec(no: Option<Box<No<T>>>, valor: &T) -> Option<Box<No<T>>> {
let mut no = match no {
None => return None,
Some(n) => n,
};
if *valor < no.valor {
no.esquerda = Self::remover_rec(no.esquerda.take(), valor);
} else if *valor > no.valor {
no.direita = Self::remover_rec(no.direita.take(), valor);
} else {
// Encontrou o nó para remover
match (no.esquerda.take(), no.direita.take()) {
(None, None) => return None,
(Some(esq), None) => return Some(esq),
(None, Some(dir)) => return Some(dir),
(esq, Some(mut dir)) => {
// Encontra o menor da subárvore direita
let (menor, nova_dir) = Self::extrair_min(dir);
no = menor;
no.esquerda = esq;
no.direita = nova_dir;
}
}
}
Some(balancear(no))
}
/// Extrai o nó com menor valor de uma subárvore.
fn extrair_min(mut no: Box<No<T>>) -> (Box<No<T>>, Option<Box<No<T>>>) {
if no.esquerda.is_none() {
let dir = no.direita.take();
no.altura = 1;
(no, dir)
} else {
let (min, nova_esq) = Self::extrair_min(no.esquerda.take().unwrap());
no.esquerda = nova_esq;
let no_balanceado = balancear(no);
(min, Some(no_balanceado))
}
}
/// Travessia in-order (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<'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 a altura da árvore.
fn altura(&self) -> i32 {
altura(&self.raiz)
}
}
fn main() {
let mut arvore = Avl::nova();
// Inserção em ordem crescente — BST degeneraria, AVL se mantém balanceada
for v in 1..=15 {
arvore.inserir(v);
}
println!("Em ordem: {:?}", arvore.em_ordem());
println!("Altura da árvore: {}", arvore.altura());
println!(" (BST sem balanceamento teria altura 15!)");
println!(" (Altura AVL ideal para 15 nós: ~4)");
// Busca
println!("\nBuscar 7: {}", arvore.buscar(&7));
println!("Buscar 16: {}", arvore.buscar(&16));
// Remoção
arvore.remover(&8);
println!("\nApós remover 8: {:?}", arvore.em_ordem());
println!("Altura: {}", arvore.altura());
}
Exemplo de Execução
Em ordem: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Altura da árvore: 4
(BST sem balanceamento teria altura 15!)
(Altura AVL ideal para 15 nós: ~4)
Buscar 7: true
Buscar 16: false
Após remover 8: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]
Altura: 4
Trace da inserção de 1, 2, 3 (seria o pior caso para BST):
Inserir 1: 1 (h=1, FB=0)
Inserir 2: 1 (h=2, FB=-1)
\
2
Inserir 3: 1 (h=3, FB=-2) → Rotação RR (esquerda)
\
2 2
\ → / \
3 1 3 (h=2, balanceada!)
Variações e Otimizações
1. AVL com Contagem de Nós por Subárvore
Adicionar um campo de contagem permite encontrar o k-ésimo menor elemento em O(log n).
use std::cmp::max;
struct No {
valor: i64,
altura: i32,
tamanho: usize, // número de nós na subárvore
esquerda: Option<Box<No>>,
direita: Option<Box<No>>,
}
fn tamanho(no: &Option<Box<No>>) -> usize {
no.as_ref().map_or(0, |n| n.tamanho)
}
fn alt(no: &Option<Box<No>>) -> i32 {
no.as_ref().map_or(0, |n| n.altura)
}
fn atualizar(no: &mut Box<No>) {
no.altura = 1 + max(alt(&no.esquerda), alt(&no.direita));
no.tamanho = 1 + tamanho(&no.esquerda) + tamanho(&no.direita);
}
/// Encontra o k-ésimo menor elemento (1-indexado).
fn k_esimo(no: &Option<Box<No>>, k: usize) -> Option<i64> {
let n = no.as_ref()?;
let esq = tamanho(&n.esquerda);
if k <= esq {
k_esimo(&n.esquerda, k)
} else if k == esq + 1 {
Some(n.valor)
} else {
k_esimo(&n.direita, k - esq - 1)
}
}
fn main() {
// Demonstração do conceito com nó manual
let arvore = Some(Box::new(No {
valor: 5,
altura: 3,
tamanho: 5,
esquerda: Some(Box::new(No {
valor: 3,
altura: 2,
tamanho: 2,
esquerda: Some(Box::new(No {
valor: 1,
altura: 1,
tamanho: 1,
esquerda: None,
direita: None,
})),
direita: None,
})),
direita: Some(Box::new(No {
valor: 8,
altura: 2,
tamanho: 2,
esquerda: None,
direita: Some(Box::new(No {
valor: 10,
altura: 1,
tamanho: 1,
esquerda: None,
direita: None,
})),
})),
}));
for k in 1..=5 {
println!("{}º menor: {:?}", k, k_esimo(&arvore, k));
}
}
2. Impressão Visual da Árvore
use std::cmp::max;
struct No {
valor: i32,
altura: i32,
esquerda: Option<Box<No>>,
direita: Option<Box<No>>,
}
/// Imprime a árvore de forma visual com indentação.
fn imprimir_arvore(no: &Option<Box<No>>, prefixo: &str, eh_esquerdo: bool) {
if let Some(n) = no {
let conector = if eh_esquerdo { "├── " } else { "└── " };
let extensao = if eh_esquerdo { "│ " } else { " " };
println!("{}{}{} (h={}, fb={})",
prefixo, conector, n.valor, n.altura,
alt(&n.esquerda) - alt(&n.direita));
let novo_prefixo = format!("{}{}", prefixo, extensao);
if n.esquerda.is_some() || n.direita.is_some() {
imprimir_arvore(&n.esquerda, &novo_prefixo, true);
imprimir_arvore(&n.direita, &novo_prefixo, false);
}
} else {
println!("{}{}(vazio)", prefixo, if eh_esquerdo { "├── " } else { "└── " });
}
}
fn alt(no: &Option<Box<No>>) -> i32 {
no.as_ref().map_or(0, |n| n.altura)
}
fn main() {
let arvore = Some(Box::new(No {
valor: 20,
altura: 3,
esquerda: Some(Box::new(No {
valor: 10,
altura: 2,
esquerda: Some(Box::new(No { valor: 5, altura: 1, esquerda: None, direita: None })),
direita: Some(Box::new(No { valor: 15, altura: 1, esquerda: None, direita: None })),
})),
direita: Some(Box::new(No {
valor: 30,
altura: 2,
esquerda: Some(Box::new(No { valor: 25, altura: 1, esquerda: None, direita: None })),
direita: None,
})),
}));
println!("Árvore AVL:");
if let Some(ref raiz) = arvore {
println!("{} (h={}, fb={})", raiz.valor, raiz.altura,
alt(&raiz.esquerda) - alt(&raiz.direita));
imprimir_arvore(&raiz.esquerda, "", true);
imprimir_arvore(&raiz.direita, "", false);
}
}
Aplicações Práticas
- Bancos de dados em memória: AVL Trees são usadas em sistemas que exigem garantia de O(log n) para todas as operações, como caches ordenados e índices em memória.
- Sistemas de tempo real: onde o pior caso importa mais que o caso médio, a AVL é preferida por ter altura estritamente limitada.
- Editores de texto: representação de linhas do texto em uma árvore balanceada permite inserção, remoção e navegação eficientes.
- Agendamento de tarefas: organizar tarefas por prioridade com inserção e remoção frequentes.
- Jogos: árvores de decisão e detecção de colisão em engines gráficas.
Comparação com Alternativas
| Característica | AVL | BST Simples | Red-Black Tree | B-Tree |
|---|---|---|---|---|
| Busca (pior) | O(log n) | O(n) | O(log n) | O(log n) |
| Altura máxima | ~1.44 log n | n | ~2 log n | log n |
| Rotações (inserção) | Até 2 | 0 | Até 2 | 0 |
| Rotações (remoção) | Até O(log n) | 0 | Até 3 | 0 |
| Balanceamento | Mais rígido | Nenhum | Menos rígido | Por grau |
| Busca mais rápida? | Sim | Depende | Não | Para disco |
| Inserção/remoção | Mais lenta | Mais rápida | Mais rápida | Para disco |
A AVL é mais rígida que a Red-Black Tree: buscas são mais rápidas na AVL (altura menor), mas inserções e remoções são mais lentas (mais rotações). Use AVL quando buscas são mais frequentes que modificações.
Exercícios Práticos
Inserção com log de rotações: Modifique a implementação para imprimir qual tipo de rotação (LL, RR, LR, RL) foi executada durante cada inserção. Insira os valores 10, 20, 30, 15, 25, 12 e observe as rotações.
Verificador de AVL: Implemente uma função que verifica se uma árvore binária é uma AVL válida (todas as propriedades de BST + fator de balanceamento entre -1 e +1 para todo nó).
Merge de duas AVLs: Dadas duas árvores AVL onde todos os valores da primeira são menores que todos os valores da segunda, implemente uma função que as combine em uma única AVL balanceada em O(m + n).
Comparação empírica BST vs AVL: Insira 10.000 números em ordem crescente tanto em uma BST simples quanto em uma AVL. Compare a altura resultante e o tempo de busca para 1.000 consultas aleatórias usando
std::time::Instant.
Veja Também
- Árvore Binária de Busca em Rust — BST sem balanceamento
- Box — Alocação no Heap — como
Box<No>gerencia memória - Option — Valores Opcionais — representação de filhos ausentes
- Tipos Numéricos — tipos usados para altura e fator de balanceamento