Árvore AVL | Rust Brasil

Introdução

A Árvore AVL (nomeada em homenagem a seus inventores Adelson-Velsky e Landis, 1962) é a primeira árvore de busca binária autobalanceada da história. Ela resolve o problema fundamental das BSTs comuns: a possibilidade de degeneração em uma lista encadeada quando os dados são inseridos em ordem.

A AVL garante que, para todo nó, a diferença de altura entre as subárvores esquerda e direita (chamada de fator de balanceamento) seja no máximo 1 em valor absoluto. Quando uma inserção ou remoção viola essa propriedade, rotações são aplicadas para restaurar o equilíbrio. Isso garante que a altura da árvore é sempre O(log n), tornando todas as operações eficientes.

Conceito e Teoria

Fator de Balanceamento

O fator de balanceamento de um nó é definido como:

FB(nó) = altura(subárvore esquerda) - altura(subárvore direita)

Uma árvore AVL exige que para todo nó: FB ∈ {-1, 0, 1}

    Árvore AVL válida:          Árvore NÃO AVL:
         [30] FB=1                   [30] FB=2  ← Violação!
        /    \                      /
      [20]   [40] FB=0           [20] FB=1
      /                          /
    [10] FB=0                  [10] FB=0

As Quatro Rotações

Quando o fator de balanceamento fica fora de {-1, 0, 1}, aplicamos rotações:

Rotação Simples à Direita (LL — Left-Left)

Desbalanceamento causado por inserção na subárvore esquerda do filho esquerdo:

    Antes (FB=2):           Depois (FB=0):
        [30]                    [20]
        /                      /    \
      [20]          →       [10]   [30]
      /
    [10]

    Rotação à direita no nó [30]

Rotação Simples à Esquerda (RR — Right-Right)

Desbalanceamento causado por inserção na subárvore direita do filho direito:

    Antes (FB=-2):          Depois (FB=0):
    [10]                        [20]
       \                       /    \
      [20]          →       [10]   [30]
         \
        [30]

    Rotação à esquerda no nó [10]

Rotação Dupla Esquerda-Direita (LR — Left-Right)

Desbalanceamento causado por inserção na subárvore direita do filho esquerdo:

    Antes (FB=2):           Passo 1:             Passo 2:
        [30]                  [30]                  [25]
        /                     /                    /    \
      [20]          →      [25]          →      [20]   [30]
         \                 /
        [25]             [20]

    1. Rotação à esquerda em [20]
    2. Rotação à direita em [30]

Rotação Dupla Direita-Esquerda (RL — Right-Left)

Desbalanceamento causado por inserção na subárvore esquerda do filho direito:

    Antes (FB=-2):          Passo 1:             Passo 2:
    [10]                    [10]                    [15]
       \                       \                   /    \
      [20]          →        [15]        →      [10]   [20]
      /                         \
    [15]                       [20]

    1. Rotação à direita em [20]
    2. Rotação à esquerda em [10]

Exemplo Completo de Inserções Sucessivas

Inserir: 50, 30, 70, 20, 40, 10

    Após 50, 30, 70:        Após 20:              Após 40:
        [50]                   [50]                   [50]
       /    \                 /    \                  /    \
     [30]  [70]            [30]   [70]             [30]   [70]
                           /                       /  \
                         [20]                    [20] [40]
     FB(todos) OK         FB(todos) OK            FB(todos) OK

    Após inserir 10:
        [50] FB=2 ← Desbalanceado!
       /    \
     [30]   [70]
     /  \
   [20] [40]
   /
 [10]

    Rotação à direita em [50]:
           [30]
          /    \
       [20]   [50]
       /      /   \
     [10]   [40]  [70]

     FB(todos) ∈ {-1, 0, 1}  ✓

Complexidade

Operação	Melhor Caso	Caso Médio	Pior Caso
Busca	O(1)	O(log n)	O(log n)
Inserção	O(log n)	O(log n)	O(log n)
Remoção	O(log n)	O(log n)	O(log n)
Rotação	O(1)	O(1)	O(1)
Espaço	—	O(n)	O(n)

Garantia fundamental: A altura de uma árvore AVL com n nós é sempre no máximo 1.44 * log2(n), garantindo O(log n) para todas as operações.

Implementação em Rust

use std::cmp::Ordering;
use std::fmt::Display;

/// Nó da árvore AVL com campo de altura para balanceamento eficiente
#[derive(Debug, Clone)]
struct No<T: Ord + Display + Clone> {
    valor: T,
    altura: i32,
    esquerda: ArvoreAVL<T>,
    direita: ArvoreAVL<T>,
}

/// Tipo da árvore AVL
type ArvoreAVL<T> = Option<Box<No<T>>>;

/// Retorna a altura de um nó (ou -1 se nulo)
fn altura<T: Ord + Display + Clone>(no: &ArvoreAVL<T>) -> i32 {
    match no {
        Some(n) => n.altura,
        None => -1,
    }
}

/// Calcula o fator de balanceamento de um nó
fn fator_balanceamento<T: Ord + Display + Clone>(no: &ArvoreAVL<T>) -> i32 {
    match no {
        Some(n) => altura(&n.esquerda) - altura(&n.direita),
        None => 0,
    }
}

/// Atualiza a altura de um nó com base nos filhos
fn atualizar_altura<T: Ord + Display + Clone>(no: &mut Box<No<T>>) {
    no.altura = 1 + altura(&no.esquerda).max(altura(&no.direita));
}

/// Rotação simples à direita (caso LL)
fn rotacao_direita<T: Ord + Display + Clone>(mut raiz: Box<No<T>>) -> Box<No<T>> {
    let mut novo_raiz = raiz.esquerda.take().expect("Filho esquerdo esperado");
    raiz.esquerda = novo_raiz.direita.take();
    atualizar_altura(&mut raiz);
    novo_raiz.direita = Some(raiz);
    atualizar_altura(&mut novo_raiz);
    novo_raiz
}

/// Rotação simples à esquerda (caso RR)
fn rotacao_esquerda<T: Ord + Display + Clone>(mut raiz: Box<No<T>>) -> Box<No<T>> {
    let mut novo_raiz = raiz.direita.take().expect("Filho direito esperado");
    raiz.direita = novo_raiz.esquerda.take();
    atualizar_altura(&mut raiz);
    novo_raiz.esquerda = Some(raiz);
    atualizar_altura(&mut novo_raiz);
    novo_raiz
}

/// Aplica o balanceamento necessário após inserção/remoção
fn balancear<T: Ord + Display + Clone>(mut no: Box<No<T>>) -> Box<No<T>> {
    atualizar_altura(&mut no);
    let fb = fator_balanceamento(&Some(no.clone()));

    // Caso LL: desbalanceado à esquerda, filho esquerdo pende à esquerda
    if fb > 1 && fator_balanceamento(&no.esquerda) >= 0 {
        return rotacao_direita(no);
    }

    // Caso LR: desbalanceado à esquerda, filho esquerdo pende à direita
    if fb > 1 && fator_balanceamento(&no.esquerda) < 0 {
        no.esquerda = Some(rotacao_esquerda(no.esquerda.take().unwrap()));
        return rotacao_direita(no);
    }

    // Caso RR: desbalanceado à direita, filho direito pende à direita
    if fb < -1 && fator_balanceamento(&no.direita) <= 0 {
        return rotacao_esquerda(no);
    }

    // Caso RL: desbalanceado à direita, filho direito pende à esquerda
    if fb < -1 && fator_balanceamento(&no.direita) > 0 {
        no.direita = Some(rotacao_direita(no.direita.take().unwrap()));
        return rotacao_esquerda(no);
    }

    no // Já está balanceado
}

/// Insere um valor na árvore AVL
fn inserir<T: Ord + Display + Clone>(raiz: ArvoreAVL<T>, valor: T) -> ArvoreAVL<T> {
    match raiz {
        None => Some(Box::new(No {
            valor,
            altura: 0,
            esquerda: None,
            direita: None,
        })),
        Some(mut no) => {
            match valor.cmp(&no.valor) {
                Ordering::Less => {
                    no.esquerda = inserir(no.esquerda.take(), valor);
                }
                Ordering::Greater => {
                    no.direita = inserir(no.direita.take(), valor);
                }
                Ordering::Equal => return Some(no), // Duplicado ignorado
            }
            Some(balancear(no))
        }
    }
}

/// Encontra e remove o menor valor de uma subárvore
fn extrair_minimo<T: Ord + Display + Clone>(
    mut no: Box<No<T>>,
) -> (T, ArvoreAVL<T>) {
    match no.esquerda.take() {
        None => {
            let valor_minimo = no.valor.clone();
            (valor_minimo, no.direita.take())
        }
        Some(esq) => {
            let (valor_minimo, nova_esq) = extrair_minimo(esq);
            no.esquerda = nova_esq;
            (valor_minimo, Some(balancear(no)))
        }
    }
}

/// Remove um valor da árvore AVL
fn remover<T: Ord + Display + Clone>(raiz: ArvoreAVL<T>, valor: &T) -> ArvoreAVL<T> {
    match raiz {
        None => None,
        Some(mut no) => {
            match valor.cmp(&no.valor) {
                Ordering::Less => {
                    no.esquerda = remover(no.esquerda.take(), valor);
                    Some(balancear(no))
                }
                Ordering::Greater => {
                    no.direita = remover(no.direita.take(), valor);
                    Some(balancear(no))
                }
                Ordering::Equal => {
                    // Nó encontrado — tratar os três casos de remoção
                    match (no.esquerda.take(), no.direita.take()) {
                        (None, None) => None,
                        (Some(esq), None) => Some(esq),
                        (None, Some(dir)) => Some(dir),
                        (Some(esq), Some(dir)) => {
                            let (sucessor, nova_dir) = extrair_minimo(dir);
                            no.valor = sucessor;
                            no.esquerda = Some(esq);
                            no.direita = nova_dir;
                            Some(balancear(no))
                        }
                    }
                }
            }
        }
    }
}

/// Busca um valor na árvore AVL
fn buscar<T: Ord + Display + Clone>(raiz: &ArvoreAVL<T>, valor: &T) -> bool {
    match raiz {
        None => false,
        Some(no) => match valor.cmp(&no.valor) {
            Ordering::Less => buscar(&no.esquerda, valor),
            Ordering::Greater => buscar(&no.direita, valor),
            Ordering::Equal => true,
        },
    }
}

/// Travessia em ordem (retorna valores ordenados)
fn em_ordem<T: Ord + Display + Clone>(raiz: &ArvoreAVL<T>, resultado: &mut Vec<T>) {
    if let Some(no) = raiz {
        em_ordem(&no.esquerda, resultado);
        resultado.push(no.valor.clone());
        em_ordem(&no.direita, resultado);
    }
}

fn main() {
    let mut arvore: ArvoreAVL<i32> = None;

    // Inserção de valores que causariam degeneração em BST
    let valores = vec![10, 20, 30, 40, 50, 60, 70];
    println!("Inserindo em ordem crescente: {:?}", valores);

    for v in &valores {
        arvore = inserir(arvore, *v);
        println!(
            "  Inseriu {}: altura = {}",
            v,
            altura(&arvore)
        );
    }

    // A árvore se mantém balanceada mesmo com inserção ordenada
    println!("\nAltura final: {} (BST teria altura {})",
        altura(&arvore),
        valores.len() as i32 - 1
    );

    // Travessia em ordem
    let mut ordenados = Vec::new();
    em_ordem(&arvore, &mut ordenados);
    println!("Em ordem: {:?}", ordenados);

    // Busca
    println!("\nBuscar 30: {}", buscar(&arvore, &30));
    println!("Buscar 35: {}", buscar(&arvore, &35));

    // Remoção
    arvore = remover(arvore, &40);
    println!("\nApós remover 40:");
    let mut apos = Vec::new();
    em_ordem(&arvore, &mut apos);
    println!("Em ordem: {:?}", apos);
    println!("Altura: {}", altura(&arvore));
}

Métodos Principais

Função/Método	Descrição
`inserir(raiz, valor)`	Insere um valor e rebalanceia a árvore
`remover(raiz, valor)`	Remove um valor e rebalanceia a árvore
`buscar(raiz, valor)`	Busca binária aproveitando a propriedade BST
`rotacao_direita(no)`	Rotação simples para corrigir desbalanceamento LL
`rotacao_esquerda(no)`	Rotação simples para corrigir desbalanceamento RR
`balancear(no)`	Detecta o tipo de desbalanceamento e aplica rotação
`altura(no)`	Retorna a altura armazenada no nó (O(1))
`fator_balanceamento()`	Calcula a diferença de alturas dos filhos
`em_ordem(raiz)`	Travessia que produz os elementos em ordem crescente

Exemplo Prático: Índice de Banco de Dados

Bancos de dados frequentemente usam árvores balanceadas para indexar registros, permitindo buscas, inserções e remoções eficientes mesmo com milhões de registros.

/// Simula um índice de banco de dados usando árvore AVL
#[derive(Debug, Clone, PartialEq, Eq)]
struct RegistroIndice {
    chave: i64,          // Valor indexado (ex: ID do usuário)
    posicao_disco: u64,  // Posição do registro no disco
}

impl PartialOrd for RegistroIndice {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for RegistroIndice {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.chave.cmp(&other.chave)
    }
}

impl std::fmt::Display for RegistroIndice {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[chave={}, pos={}]", self.chave, self.posicao_disco)
    }
}

fn main() {
    let mut indice: ArvoreAVL<RegistroIndice> = None;

    // Simulação: inserindo registros no índice
    let registros = vec![
        (1001, 0), (1005, 512), (1002, 1024),
        (1008, 1536), (1003, 2048), (1007, 2560),
    ];

    for (chave, pos) in registros {
        let registro = RegistroIndice {
            chave,
            posicao_disco: pos,
        };
        indice = inserir(indice, registro);
    }

    // A altura do índice é mantida baixa graças ao balanceamento
    println!("Índice com {} registros, altura: {}",
        6, altura(&indice));

    // Busca eficiente: O(log n) mesmo no pior caso
    let busca_chave = RegistroIndice { chave: 1005, posicao_disco: 0 };
    println!("Chave 1005 existe no índice: {}", buscar(&indice, &busca_chave));
}

Comparação com Outras Estruturas

Critério	AVL	BST Simples	Rubro-Negra	HashMap
Busca (pior caso)	O(log n)	O(n)	O(log n)	O(n)*
Inserção (pior caso)	O(log n)	O(n)	O(log n)	O(n)*
Balanceamento	Estrito (±1)	Nenhum	Relaxado	N/A
Rotações por inserção	Até 2	0	Até 2	N/A
Rotações por remoção	Até O(log n)	0	Até 3	N/A
Altura máxima	1.44 log n	n-1	2 log n	N/A
Dados ordenados	Sim	Sim	Sim	Não

* Pior caso com muitas colisões.

Quando usar Árvore AVL?

Use quando buscas são muito mais frequentes que inserções/remoções (o balanceamento mais estrito favorece buscas).
Use quando precisa de garantia estrita de O(log n) para todas as operações.
Não use quando inserções e remoções são muito frequentes — rubro-negra faz menos rotações.
Não use quando não precisa de ordenação — HashMap é mais simples e rápido para busca pura.

Exercícios

Exercício 1: Visualização de Rotações

Trace manualmente as rotações ao inserir os valores [15, 10, 20, 5, 12, 11] em uma árvore AVL. Identifique qual rotação (LL, RR, LR ou RL) ocorre em cada passo e desenhe a árvore resultante.

Exercício 2: Implementar Busca por Intervalo

Adicione uma função buscar_intervalo(raiz, min, max) -> Vec<T> que retorne todos os valores da árvore AVL no intervalo [min, max] de forma eficiente (sem visitar nós desnecessários). A complexidade deve ser O(log n + k), onde k é o número de resultados.

Exercício 3: Contar Rotações

Modifique a implementação para contar quantas rotações são realizadas durante uma sequência de inserções. Compare o número de rotações ao inserir n elementos em ordem crescente versus inserir n elementos aleatórios. O que você observa?

Conclusão

A árvore AVL é uma das estruturas mais elegantes da ciência da computação. Com um conceito simples — manter o fator de balanceamento entre -1 e 1 — ela garante desempenho O(log n) para todas as operações, eliminando o problema de degeneração das BSTs simples.

Em Rust, a implementação exige atenção com ownership e borrowing ao manipular os ponteiros Box durante as rotações, mas o resultado é um código seguro sem necessidade de gerenciamento manual de memória. A AVL é particularmente indicada para cenários onde buscas predominam sobre modificações, como índices de bancos de dados em memória e dicionários. Quando a frequência de modificações é alta, considere a árvore rubro-negra, que veremos no próximo artigo.