Na Aula 12 vimos que a Abp garante busca, inserção e remoção em O(h), onde h é a altura da árvore. O problema é que h pode chegar a n - 1 se os elementos forem inseridos em ordem — tornando a Abp tão lenta quanto uma lista encadeada. Nesta aula estudamos a Árvore AVL (Adelson-Velsky e Landis, 1962), a primeira estrutura de dados que resolve esse problema: uma Abp que se reequilibra automaticamente a cada inserção e remoção, garantindo que a altura seja sempre O(log₂ n) — e, portanto, todas as operações sejam O(log₂ n) no pior caso, independentemente da ordem de inserção.

1. Por que árvore balanceada implica O(log₂ n)?

Antes de ver como a AVL se reequilibra, vale entender por que manter a árvore balanceada garante operações em O(log₂ n). A ideia central está na relação entre a altura e o número de nodos.

1.1 Altura e número de nodos

Em uma árvore binária perfeitamente balanceada, cada nível aproximadamente dobra o número de nodos em relação ao nível anterior:

nível 0:       raiz          →  2⁰ = 1 nodo
nível 1:     /       \       →  2¹ = 2 nodos
nível 2:   /  \    /  \      →  2² = 4 nodos
nível 3: / \ / \  / \ / \   →  2³ = 8 nodos
            ...
nível h:                     →  2ʰ nodos (no máximo)

Total de nodos:  n ≤ 1 + 2 + 4 + ... + 2ʰ = 2^(h+1) - 1  ≈  2^h

Invertendo a relação: se a árvore tem n nodos e está balanceada, então:

n  ≈  2ʰ
⟹  h  =  log₂ n

1.2 Por que as operações custam O(log₂ n)

As operações de busca, inserção e remoção percorrem um único caminho da raiz até uma folha (ou até onde a busca falha). Esse caminho tem no máximo h nodos:

2. O problema da degeneração

Recapitulando: ao inserir 1, 2, 3, 4, 5 em uma Abp, a árvore resultante é:

1
 \
  2
   \
    3
     \
      4
       \
        5        <- altura h = 4 = n - 1

Com 5 elementos, a altura é 4. Uma árvore perfeitamente balanceada teria altura 2 (⌊log₂ 5⌋ = 2). Para 1.000 elementos, seria a diferença entre altura 9 e altura 999 — uma diferença de duas ordens de magnitude.

3. Fator de balanceamento

A invariante da árvore AVL é: para todo nó x, as alturas das suas subárvores esquerda e direita diferem em no máximo 1. Essa diferença é chamada de fator de balanceamento (fb):

fb(x) = altura(subárvore esquerda de x) - altura(subárvore direita de x)

Para uma árvore AVL válida: fb(x) ∈ {-1, 0, +1}  para todo nó x.

fb = +1  →  subárvore esquerda um nível mais alta
fb =  0  →  subárvores com a mesma altura
fb = -1  →  subárvore direita um nível mais alta

Cada nó da AVL armazena, além do dado e dos dois ponteiros, um inteiro altura. O fator de balanceamento é derivado das alturas dos dois filhos — não é armazenado diretamente. Isso permite recalcular o fator em tempo constante após qualquer reorganização.

Um exemplo de árvore AVL válida (os números entre parênteses são os fatores de balanceamento):

           20 (fb=0)
          /          \
      10 (fb=+1)    30 (fb=0)
      /
   5 (fb=0)

Todo nó tem fb ∈ {-1, 0, +1} → árvore AVL válida.

E um exemplo de árvore inválida — o nó 20 ficou com fb = +2 após inserir 5:

           20 (fb=+2) ← INVÁLIDO!
          /
      10 (fb=+1)
      /
   5 (fb=0)

4. Rotações

Quando uma inserção ou remoção faz com que o fator de balanceamento de algum nó saia de {-1, 0, +1}, a árvore precisa ser reequilibrada. O mecanismo fundamental para isso são as rotações: operações locais que reorganizam ponteiros para reduzir a altura de um lado e aumentar do outro, restaurando o balanceamento sem alterar a propriedade de ordenação da Abp.

Rotação simples à direita — caso LL

Usada quando o nó está "pesado à esquerda" (fb = +2) e o filho esquerdo também está pesado à esquerda ou equilibrado (fb ≥ 0). O desequilíbrio está no filho esquerdo do filho esquerdo — daí o nome LL.

x "sobe" para o lugar de y. O filho direito de x (B) passa a ser o filho esquerdo de y.

    Antes (fb(y) = +2):          Depois (rotação à direita em y):

          y                               x
         / \                            /   \
        x   C          →              A     y
       / \                                 / \
      A   B                               B   C

Rotação simples à esquerda — caso RR

Simétrica ao caso LL. Usada quando o nó está "pesado à direita" (fb = -2) e o filho direito também está pesado à direita (fb ≤ 0). O desequilíbrio está no filho direito do filho direito.

y "sobe" para o lugar de x. O filho esquerdo de y (B) passa a ser o filho direito de x.

    Antes (fb(x) = -2):          Depois (rotação à esquerda em x):

        x                                  y
       / \                               /   \
      A   y              →             x     C
         / \                          / \
        B   C                        A   B

Rotação dupla esquerda-direita — caso LR

Usada quando o nó está "pesado à esquerda" (fb = +2) mas o filho esquerdo está "pesado à direita" (fb = -1). Uma rotação simples não resolve porque o desequilíbrio está no filho direito do filho esquerdo. A solução é em dois passos: primeiro rotacionar o filho esquerdo à esquerda (transformando o caso LR em LL), depois rotacionar a raiz à direita.

  Caso LR (antes):     Após rot. esq. em x:    Após rot. dir. em z:

      z (fb=+2)               z (fb=+2)                y
     /                       /                        /   \
    x (fb=-1)               y                        x     z
     \                     /
      y                   x

Rotação dupla direita-esquerda — caso RL

Simétrica ao caso LR. Usada quando o nó está "pesado à direita" (fb = -2) e o filho direito está "pesado à esquerda" (fb = +1). Dois passos: rotaciona o filho direito à direita (RL vira RR), depois rotaciona a raiz à esquerda.

Resumo dos quatro casos

5. Inserção na AVL

A inserção na AVL começa exatamente como na Abp: desce recursivamente até encontrar a posição NULL onde o novo nó deve entrar e cria o nó lá. A diferença está no caminho de volta da recursão: ao retornar para cada ancestral, duas coisas acontecem:

1. A altura do nó é atualizada com base nas alturas dos filhos.
2. O fator de balanceamento é calculado. Se saiu de {-1, 0, +1}, identifica-se qual dos quatro casos é e aplica-se a rotação adequada.

Exemplo de inserção com reequilíbrio

Inserir 1, 2, 3 em ordem (que na Abp simples geraria uma lista):

Após inserir 1:    Após inserir 2:    Após inserir 3:
    1 (fb=0)           1 (fb=-1)          1 (fb=-2)  ← INVÁLIDO
                        \                  \
                         2 (fb=0)           2 (fb=-1)
                                             \
                                              3 (fb=0)

Detecta caso RR em 1: fb(1) = -2 e fb(filho dir 2) = -1.
Aplica rotação simples à esquerda:

    2 (fb=0)
   / \
  1   3

Árvore perfeitamente balanceada após apenas 3 inserções.

Inserir 30, 10, 20 (caso LR):

Após inserir 30, 10:    Após inserir 20:
    30 (fb=+1)               30 (fb=+2)  ← INVÁLIDO
   /                        /
  10 (fb=0)               10 (fb=-1)
                              \
                               20 (fb=0)

Detecta caso LR em 30: fb(30) = +2 e fb(filho esq 10) = -1.
Passo 1 — rotação à esquerda em 10:        Passo 2 — rotação à direita em 30:
    30                                           20
   /                                           /    \
  20           →                             10      30
 /
10

Resultado final: fb(20)=0, fb(10)=0, fb(30)=0. Árvore AVL válida.

6. Remoção na AVL

A remoção na AVL começa como na Abp — os mesmos três casos (folha, um filho, dois filhos com substituição pelo sucessor em-ordem). Novamente, a diferença está no caminho de volta da recursão: após remover, atualizamos alturas e verificamos o balanceamento em cada ancestral, aplicando rotações onde necessário.

7. Por que a altura da AVL é O(log₂ n)?

A prova formal usa o argumento de Fibonacci: o número mínimo de nós em uma árvore AVL de altura h é definido pela recorrência N(h) = N(h-1) + N(h-2) + 1, com N(0) = 1 e N(-1) = 0. A pior árvore AVL possível para uma dada altura é aquela em que cada nó tem um filho com altura h-1 e outro com altura h-2 (diferença de exatamente 1 em todo nó).

Essa recorrência cresce como a sequência de Fibonacci — especificamente, N(h) ≈ φ^h / √5, onde φ ≈ 1,618 é a razão áurea. Invertendo:

n ≥ N(h) ≈ φ^h / √5
→ h ≤ log_φ(n√5)
→ h < 1.44 × log₂(n + 2)
→ h = O(log n)

Isso significa que mesmo a pior árvore AVL tem altura no máximo cerca de 44% maior que o log₂ de n. Para 1.000.000 de elementos: 1.44 × log₂(10⁶) ≈ 1.44 × 20 ≈ 28 — muito longe do pior caso da Abp simples (h = 999.999).

8. Complexidade das operações

O custo extra da AVL em relação à Abp simples é um inteiro a mais por nó (a altura) e o trabalho de atualizar alturas e checar o balanceamento no caminho de volta — tudo O(1) por nó visitado. O ganho (pior caso O(log₂ n) em vez de O(n)) compensa amplamente em qualquer aplicação com muitas buscas ou dados chegando em ordem.

Resumo

Exercícios

1. O que é o fator de balanceamento de um nó em uma árvore AVL? Quais são os valores permitidos? Por que guardamos a altura no nó em vez do fator diretamente?
2. Insira os valores 10, 20, 30 (nessa ordem) em uma árvore AVL inicialmente vazia. Mostre o estado da árvore após cada inserção e qual rotação foi aplicada (se houver).
3. Insira os valores 30, 10, 20 (nessa ordem) em uma árvore AVL. Qual caso de desbalanceamento ocorre? Aplique as rotações necessárias e mostre a árvore final.
4. Insira os valores 5, 3, 7, 1, 4, 6, 8 em uma árvore AVL. Mostre a árvore final e confirme que todo nó tem fator de balanceamento em {-1, 0, +1}.
5. Explique por que as rotações não alteram a propriedade de ordenação da Abp. Use a rotação simples à direita (caso LL) como exemplo.
6. Por que uma inserção na AVL exige no máximo uma rotação (simples ou dupla), enquanto uma remoção pode exigir mais de uma? Justifique intuitivamente.
7. A altura de uma árvore AVL com n nós é no máximo 1.44 × log₂ n. Para n = 1.000.000, qual é a altura máxima? Compare com o pior caso de uma Abp simples.

Após inserir 10:    Após inserir 20:    Após inserir 30 (desbalanceia!):
    10 (fb=0)           10 (fb=-1)          10 (fb=-2)
                          \                   \
                           20 (fb=0)           20 (fb=-1)
                                                 \
                                                  30 (fb=0)

Caso RR: fb(10) = -2, fb(filho dir 20) = -1.
Rotação simples à esquerda em 10:

    20 (fb=0)
   /  \
  10   30

fb(20)=0, fb(10)=0, fb(30)=0. Árvore AVL válida.

Após inserir 30, 10:    Após inserir 20 (desbalanceia!):
    30 (fb=+1)               30 (fb=+2)
   /                        /
  10 (fb=0)               10 (fb=-1)
                              \
                               20 (fb=0)

Caso LR: fb(30) = +2 e fb(filho esq 10) = -1.

Passo 1 — rotação à esquerda em 10:    Passo 2 — rotação à direita em 30:
    30                                       20
   /                   →                  /    \
  20                                    10      30
 /
10

Resultado: fb(20)=0, fb(10)=0, fb(30)=0. Árvore AVL válida.

Bônus: TAD AVL completo em C

O código abaixo implementa todas as operações estudadas. Está apresentado como um único bloco comentado para que você possa ver como cada conceito se traduz em código. Leia-o depois de entender as operações conceitualmente — o código faz sentido somente se você já sabe o que cada parte deve fazer.

/* ============================================================
   avl.h  —  TAD Árvore AVL
   ============================================================ */

/* O nó agora guarda um inteiro 'altura' além do dado e dos filhos. */
typedef struct str_NodoAvl NodoAvl;

struct str_NodoAvl {
    Produto  dado;
    NodoAvl *esq;
    NodoAvl *dir;
    int      altura;   /* folha = 0; NULL = -1 (por convenção) */
};

/* ============================================================
   avl.c  —  implementação
   ============================================================ */

/* Retorna a altura do nó, ou -1 se o nó for NULL.
   Usamos -1 para NULL pois folha = 0; assim a fórmula
   1 + max(h_esq, h_dir) fica correta até nos nós folha. */
int avlAltura(const NodoAvl *no) {
    if (no == NULL) return -1;
    return no->altura;
}

/* Calcula o fator de balanceamento: h(esq) - h(dir).
   fb > 0 → mais pesado à esquerda; fb < 0 → mais pesado à direita. */
int avlFb(const NodoAvl *no) {
    if (no == NULL) return 0;
    return avlAltura(no->esq) - avlAltura(no->dir);
}

/* Recalcula e armazena a altura de 'no' com base nas alturas dos filhos.
   Deve ser chamado após qualquer mudança nos filhos de 'no'. */
void avlAtualizarAltura(NodoAvl *no) {
    int ae = avlAltura(no->esq);
    int ad = avlAltura(no->dir);
    if (ae > ad)
        no->altura = 1 + ae;
    else
        no->altura = 1 + ad;
}

/* Rotação simples à direita (caso LL).
   x sobe para o lugar de y; o filho dir de x passa a ser filho esq de y.
   Atualiza as alturas de y (que desce) e depois de x (que sobe). */
NodoAvl* avlRotDir(NodoAvl *y) {
    NodoAvl *x = y->esq;
    NodoAvl *B = x->dir;

    x->dir = y;
    y->esq = B;

    avlAtualizarAltura(y);   /* y primeiro: agora está abaixo de x */
    avlAtualizarAltura(x);

    return x;   /* x é a nova raiz desta subárvore */
}

/* Rotação simples à esquerda (caso RR). Simétrica à anterior.
   y sobe para o lugar de x; o filho esq de y passa a ser filho dir de x. */
NodoAvl* avlRotEsq(NodoAvl *x) {
    NodoAvl *y = x->dir;
    NodoAvl *B = y->esq;

    y->esq = x;
    x->dir = B;

    avlAtualizarAltura(x);   /* x primeiro: agora está abaixo de y */
    avlAtualizarAltura(y);

    return y;
}

/* Verifica o fator de balanceamento e aplica a rotação correta.
   Pode ser chamada tanto pela inserção quanto pela remoção,
   pois a lógica de reequilíbrio é idêntica. */
NodoAvl* avlReequilibrar(NodoAvl *raiz) {
    avlAtualizarAltura(raiz);
    int fb = avlFb(raiz);

    /* Caso LL: pesado à esquerda, filho esq também pesado à esq ou equilibrado */
    if (fb == +2 && avlFb(raiz->esq) >= 0)
        return avlRotDir(raiz);

    /* Caso RR: pesado à direita, filho dir também pesado à dir ou equilibrado */
    if (fb == -2 && avlFb(raiz->dir) <= 0)
        return avlRotEsq(raiz);

    /* Caso LR: pesado à esquerda, mas filho esq pesado à direita.
       Transforma em LL com uma rotação à esquerda no filho, depois resolve LL. */
    if (fb == +2 && avlFb(raiz->esq) < 0) {
        raiz->esq = avlRotEsq(raiz->esq);
        return avlRotDir(raiz);
    }

    /* Caso RL: pesado à direita, mas filho dir pesado à esquerda.
       Transforma em RR com uma rotação à direita no filho, depois resolve RR. */
    if (fb == -2 && avlFb(raiz->dir) > 0) {
        raiz->dir = avlRotDir(raiz->dir);
        return avlRotEsq(raiz);
    }

    return raiz;   /* sem desbalanceamento: devolve sem alterar */
}

/* Busca idêntica à Abp: a AVL não precisa mudar a busca,
   pois a invariante garante que a altura é O(log n). */
NodoAvl* avlBuscar(NodoAvl *raiz, int cod) {
    if (raiz == NULL)              return NULL;
    if (cod == raiz->dado.cod)    return raiz;
    if (cod < raiz->dado.cod)     return avlBuscar(raiz->esq, cod);
    return avlBuscar(raiz->dir, cod);
}

/* Inserção: descida igual à Abp; na subida, reequilibra cada ancestral.
   Uso: raiz = avlInserir(raiz, produto); */
NodoAvl* avlInserir(NodoAvl *raiz, Produto valor) {
    /* base: posição encontrada — cria o nó */
    if (raiz == NULL) {
        NodoAvl *novo = (NodoAvl*) malloc(sizeof(NodoAvl));
        novo->dado   = valor;
        novo->esq    = NULL;
        novo->dir    = NULL;
        novo->altura = 0;
        return novo;
    }

    /* descida: igual à Abp */
    if (valor.cod < raiz->dado.cod)
        raiz->esq = avlInserir(raiz->esq, valor);
    else if (valor.cod > raiz->dado.cod)
        raiz->dir = avlInserir(raiz->dir, valor);
    else
        return raiz;   /* duplicado: ignora */

    /* subida: reequilibra se necessário */
    return avlReequilibrar(raiz);
}

/* Auxiliar: encontra o nó com menor cod na subárvore (sucessor em-ordem). */
NodoAvl* avlMinimo(NodoAvl *raiz) {
    while (raiz->esq != NULL) raiz = raiz->esq;
    return raiz;
}

/* Remoção: mesmos três casos da Abp; na subida, reequilibra cada ancestral.
   Uma remoção pode gerar rotações em vários níveis (diferente da inserção).
   Uso: raiz = avlRemover(raiz, cod); */
NodoAvl* avlRemover(NodoAvl *raiz, int cod) {
    if (raiz == NULL) return NULL;

    /* descida: procura o nó a remover */
    if (cod < raiz->dado.cod) {
        raiz->esq = avlRemover(raiz->esq, cod);
    } else if (cod > raiz->dado.cod) {
        raiz->dir = avlRemover(raiz->dir, cod);
    } else {
        /* nó encontrado — três casos da Abp */
        if (raiz->esq == NULL) {
            NodoAvl *filho = raiz->dir; free(raiz); return filho;
        }
        if (raiz->dir == NULL) {
            NodoAvl *filho = raiz->esq; free(raiz); return filho;
        }
        /* dois filhos: substitui pelo sucessor em-ordem (mínimo da subárvore dir) */
        NodoAvl *sucessor = avlMinimo(raiz->dir);
        raiz->dado = sucessor->dado;
        raiz->dir  = avlRemover(raiz->dir, sucessor->dado.cod);
    }

    /* subida: reequilibra — pode acontecer em vários níveis */
    return avlReequilibrar(raiz);
}

/* Destrói toda a árvore liberando cada nó (pós-ordem).
   Uso: raiz = avlDestruir(raiz); */
NodoAvl* avlDestruir(NodoAvl *raiz) {
    if (raiz == NULL) return NULL;
    raiz->esq = avlDestruir(raiz->esq);
    raiz->dir = avlDestruir(raiz->dir);
    free(raiz);
    return NULL;
}