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. A solução geral é manter a árvore balanceada: garantir que a altura permaneça O(log₂ n) independentemente da ordem de inserção. Existem diversas estratégias para isso; nesta aula estudamos duas:

• Árvore AVL (Adelson-Velsky e Landis, 1962): mantém um invariante estrito de balanceamento por nó e o restaura a cada operação via rotações. Garante O(log₂ n) no pior caso.
• Splay Tree (Sleator e Tarjan, 1985): não mantém invariante explícito — em vez disso, move o nó acessado até a raiz. Garante O(log₂ n) amortizado, com bom desempenho prático quando há localidade de acesso.

1. Por que balancear? A relação entre altura e complexidade

Em uma árvore binária perfeitamente balanceada, cada nível 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 h:                     →  2ʰ nodos (no máximo)

Total:  n ≈ 2ʰ  →  h = log₂ n

As operações de busca, inserção e remoção percorrem um único caminho da raiz até uma folha — no máximo h passos. Se a árvore estiver balanceada, esse custo é O(log₂ n). O que a AVL garante é que a árvore permaneça balanceada após cada inserção e remoção.

2. O problema da degeneração

Ao inserir 1, 2, 3, 4, 5 em ordem em uma Abp simples, a árvore resultante é uma lista:

1
 \
  2
   \
    3
     \
      4
       \
        5       ← altura h = 4 = n − 1

1. Fator de balanceamento (FB)

O fator de balanceamento de um nó mede o desequilíbrio entre seus dois filhos:

FB(x) = altura(subárvore esq de x) − altura(subárvore dir de x)

AVL válida: FB(x) ∈ {−1, 0, +1}  para todo nó x.

FB = +1  →  esquerda um nível mais alta
FB =  0  →  subárvores com mesma altura
FB = −1  →  direita um nível mais alta

Cada nó armazena um inteiro altura. O FB é derivado das alturas dos dois filhos em tempo O(1) — não é guardado diretamente, porque após uma rotação seria necessário percorrer subárvores para atualizá-lo, perdendo a eficiência.

Convenção: um nó NULL tem altura −1; uma folha tem altura 0. Assim a fórmula 1 + max(h_esq, h_dir) funciona corretamente até os nós folha.

2. O algoritmo de reequilíbrio

Toda vez que você insere ou remove um nó, a sequência de passos para manter a AVL válida é:

1. Execute a operação normalmente (como na Abp simples).
2. Suba da posição alterada até a raiz, visitando cada ancestral.
3. Em cada nó visitado: recalcule a altura e compute o FB.
4. Se FB ∈ {−1, 0, +1} → o nó está OK; continue subindo.
5. Se |FB| = 2 → aplique a rotação correta (veja tabela abaixo) e continue subindo.

Filho problemático: o filho esquerdo quando FB = +2; o filho direito quando FB = −2.

  +2 → problema à esquerda
       filho ≥ 0 (tb pesado à esq)  →  LL  →  rotação direita
       filho  < 0 (pesado à dir)    →  LR  →  dupla (esq no filho, depois dir no nó)

  -2 → problema à direita
       filho ≤ 0 (tb pesado à dir)  →  RR  →  rotação esquerda
       filho  > 0 (pesado à esq)   →  RL  →  dupla (dir no filho, depois esq no nó)

3. Rotações simples

Nas rotações simples usamos a notação x, y para os nós e ▲A, ▲B, ▲C para as subárvores (o triângulo ▲ indica que é uma subárvore inteira, não um nó único). As subárvores podem ter qualquer tamanho (inclusive serem vazias).

3.1 Caso LL — rotação simples à direita

Ocorre quando FB(y) = +2 e FB(x) ≥ 0 (nó pesado à esquerda, filho esquerdo também pesado à esquerda ou equilibrado). O desequilíbrio está no filho esquerdo do filho esquerdo.

Diagrama geral:

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

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

  x sobe para o lugar de y.
  O filho dir de x (▲B) passa a ser o filho esq de y.
  Atualizar altura de y primeiro (agora está abaixo), depois de x.

Exemplo concreto — inserir 30, 20, 10:

  Após inserir 30, 20:      Após inserir 10 (desbalanceia!):

      30 (FB=+1)                  30 (FB=+2) ← INVÁLIDO   y = 30
     /                           /                         x = 20
    20 (FB=0)                   20 (FB=+1)
                               /
                              10 (FB=0)

  FB(y=30) = +2 e FB(x=20) = +1 (≥ 0) → caso LL → rotação à direita em 30.

      Antes:                          Depois:

            30 (y)                          20 (x)
           /   \                          /       \
         20(x)  ▲∅          →           10        30 (y)
        /   \                           ▲∅       /   \
       10    ▲∅                                 ▲∅   ▲∅
       ▲∅

  Resultado: FB(20)=0, FB(10)=0, FB(30)=0. AVL válida.

3.2 Caso RR — rotação simples à esquerda

Simétrico ao LL. Ocorre quando FB(x) = −2 e FB(y) ≤ 0 (nó pesado à direita, filho direito também pesado à direita ou equilibrado). O desequilíbrio está no filho direito do filho direito.

Diagrama geral:

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

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

  y sobe para o lugar de x.
  O filho esq de y (▲B) passa a ser o filho dir de x.
  Atualizar altura de x primeiro (agora está abaixo), depois de y.

Exemplo concreto — inserir 10, 20, 30:

  Após inserir 10, 20:      Após inserir 30 (desbalanceia!):

      10 (FB=-1)                  10 (FB=-2) ← INVÁLIDO   x = 10
        \                           \                       y = 20
         20 (FB=0)                   20 (FB=-1)
                                       \
                                        30 (FB=0)

  FB(x=10) = -2 e FB(y=20) = -1 (≤ 0) → caso RR → rotação à esquerda em 10.

      Antes:                          Depois:

          10 (x)                              20 (y)
         /    \                             /       \
        ▲∅    20(y)          →           10(x)      30
             /   \                      /   \       ▲∅
            ▲∅    30                   ▲∅   ▲∅
                  ▲∅

  Resultado: FB(20)=0, FB(10)=0, FB(30)=0. AVL válida.

4. Rotações duplas

Nas rotações duplas, o desequilíbrio está no filho interno — o filho direito do filho esquerdo (caso LR), ou o filho esquerdo do filho direito (caso RL). Uma rotação simples não resolve porque ela empurraria o nó problemático ainda mais para dentro. A solução é primeiro "endireitar" o caminho com uma rotação, transformando o caso duplo em simples, e depois aplicar a rotação simples.

Para os casos duplos usamos a notação x, y, z para os três nós envolvidos e ▲A, ▲B, ▲C, ▲D para as quatro subárvores possíveis.

4.1 Caso LR — rotação dupla esquerda-direita

Ocorre quando FB(z) = +2 e FB(x) = −1 (nó pesado à esquerda, mas filho esquerdo pesado à direita). O desequilíbrio está no filho direito do filho esquerdo — por isso LR.

Diagrama geral:

      Antes (FB(z)=+2, FB(x)=-1):

              z
             / \
            x   ▲D
           / \
          ▲A   y
              / \
             ▲B  ▲C

  Passo 1 — rotação à esquerda em x:

              z
             / \
            y   ▲D
           / \
          x   ▲C
         / \
        ▲A  ▲B

  Passo 2 — rotação à direita em z:

              y
            /   \
           x     z
          / \   / \
         ▲A  ▲B ▲C  ▲D

  y sobe para a raiz; x fica à esquerda com ▲A e ▲B; z fica à direita com ▲C e ▲D.

Exemplo concreto — inserir 30, 10, 20:

  Após inserir 30, 10:       Após inserir 20 (desbalanceia!):

      30 (FB=+1)                  30 (FB=+2) ← INVÁLIDO   z = 30
     /                           /                         x = 10
    10 (FB=0)                   10 (FB=-1)                 y = 20
                                  \
                                   20 (FB=0)

  FB(z=30) = +2 e FB(x=10) = -1 (< 0) → caso LR → dupla (esq em 10, dir em 30).

  Passo 1 — rotação à esquerda em 10:

              30 (z)
             /      \
            20 (y)   ▲∅
           /    \
         10(x)   ▲∅
        /    \
       ▲∅    ▲∅

  Passo 2 — rotação à direita em 30:

              20 (y)
            /        \
          10 (x)      30 (z)
         /    \      /    \
        ▲∅    ▲∅    ▲∅    ▲∅

  Resultado: FB(20)=0, FB(10)=0, FB(30)=0. AVL válida.

Exemplo com subárvores não-vazias — inserir 50, 20, 80, 10, 35, 70, 90, 30, 40 e depois 38:

  Antes de inserir 38 (árvore já montada):

                    50 (FB=0)
                  /          \
              20 (FB=0)       80 (FB=0)
             /      \        /       \
           10(FB=0) 35(FB=0) 70(FB=0) 90(FB=0)
                   /    \
                 30(FB=0) 40(FB=0)

  Após inserir 38 — vai para direita de 35, esquerda de 40:

                    50 (FB=+1)
                  /          \
              20 (FB=-1)      80 (FB=0)
             /      \
           10       35 (FB=-1)        ← 35 ficou com FB=-1, ainda OK
                   /    \
                 30      40 (FB=+1)  ← 40 ficou com FB=+1, ainda OK
                         /
                        38

  Subindo: FB(35)=-1 OK, FB(20)=-1 OK → chegou na raiz sem desequilíbrio.
  (Neste caso a inserção de 38 não causou reequilíbrio — mas veja que
   o caminho é conferido em todos os ancestrais mesmo assim.)

4.2 Caso RL — rotação dupla direita-esquerda

Simétrico ao LR. Ocorre quando FB(z) = −2 e FB(x) = +1 (nó pesado à direita, mas filho direito pesado à esquerda). O desequilíbrio está no filho esquerdo do filho direito — por isso RL.

Diagrama geral:

      Antes (FB(z)=-2, FB(x)=+1):

          z
         / \
        ▲A   x
            / \
           y   ▲D
          / \
         ▲B  ▲C

  Passo 1 — rotação à direita em x:

          z
         / \
        ▲A   y
            / \
           ▲B   x
               / \
              ▲C  ▲D

  Passo 2 — rotação à esquerda em z:

              y
            /   \
           z     x
          / \   / \
         ▲A  ▲B ▲C  ▲D

  y sobe para a raiz; z fica à esquerda com ▲A e ▲B; x fica à direita com ▲C e ▲D.

Exemplo concreto — inserir 10, 30, 20:

  Após inserir 10, 30:       Após inserir 20 (desbalanceia!):

      10 (FB=-1)                  10 (FB=-2) ← INVÁLIDO   z = 10
        \                           \                       x = 30
         30 (FB=0)                   30 (FB=+1)             y = 20
                                    /
                                   20 (FB=0)

  FB(z=10) = -2 e FB(x=30) = +1 (> 0) → caso RL → dupla (dir em 30, esq em 10).

  Passo 1 — rotação à direita em 30:

          10 (z)
         /      \
        ▲∅      20 (y)
               /    \
             ▲∅      30 (x)
                    /    \
                   ▲∅    ▲∅

  Passo 2 — rotação à esquerda em 10:

              20 (y)
            /        \
          10 (z)      30 (x)
         /    \      /    \
        ▲∅    ▲∅    ▲∅    ▲∅

  Resultado: FB(20)=0, FB(10)=0, FB(30)=0. AVL válida.

Exemplo com subárvores não-vazias — inserir 10, 40, 20, 50, 30 e depois 25:

  Antes de inserir 25:

          20 (FB=0)
         /          \
        10 (FB=0)   40 (FB=0)
                   /        \
                 30 (FB=0)  50 (FB=0)

  Após inserir 25 — vai para esquerda de 30:

          20 (FB=-1)
         /          \
        10           40 (FB=+1)     ← 40 ficou FB=+1, ainda OK
                    /        \
                  30 (FB=+1)  50   ← 30 ficou FB=+1, ainda OK
                 /
                25

  Subindo do 25: FB(30)=+1 OK, FB(40)=+1 OK, FB(20)=-1 OK → sem reequilíbrio.

  ----- Agora, inserindo mais um: 15 -----

  Após inserir 15 — vai para direita de 10:

          20 (FB=-2) ← INVÁLIDO   z = 20
         /          \
        10 (FB=-1)   40            x = 40 ← filho dir, FB = +1 (> 0) → caso RL!
       /    \       /   \
      ▲∅    15    30    50
            ▲∅   /
                25

  Espera: z=20, filho problemático é o filho DIREITO (FB(z)=-2).
  FB(x=40) = +1 → caso RL: dupla (dir no filho dir=40, esq no nó=20).

  Mas aqui ▲A = subárvore de 10 (inclui 15), ▲D = subárvore de 50.
  y = 30 (filho esq de x=40); ▲B = subárvore de 25; ▲C = ∅ (dir de 30).

  Passo 1 — rotação à direita em 40:

          20 (z)
         /      \
        10(▲A)   30 (y)
                /    \
              25(▲B)   40 (x)
                      /    \
                     ▲∅(▲C)  50(▲D)

  Passo 2 — rotação à esquerda em 20:

              30 (y)
            /        \
          20 (z)      40 (x)
         /    \      /    \
        10    25    ▲∅    50
       /  \   ▲∅
      ▲∅   15

  Resultado: todos os FBs em {-1, 0, +1}. AVL válida.

5. Resumo visual dos quatro casos

      y
     / \
    x   ▲C
   / \
  ▲A  ▲B

    x
   / \
  ▲A   y
      / \
     ▲B  ▲C

    x
   / \
  ▲A   y
      / \
     ▲B  ▲C

      y
     / \
    x   ▲C
   / \
  ▲A  ▲B

      z
     / \
    x   ▲D
   / \
  ▲A   y
      / \
     ▲B  ▲C

      y
    /   \
   x     z
  / \   / \
 ▲A ▲B ▲C ▲D

    z
   / \
  ▲A   x
      / \
     y   ▲D
    / \
   ▲B  ▲C

      y
    /   \
   z     x
  / \   / \
 ▲A ▲B ▲C ▲D

6. Inserção na AVL — exemplo completo

Inserindo 5, 10, 15, 3, 8 em uma AVL inicialmente vazia (cada passo mostra a árvore e o reequilíbrio, se houver):

  Inserir 5:          Inserir 10:         Inserir 15:
    5 (FB=0)            5 (FB=-1)           5 (FB=-2) ← INVÁLIDO
                          \                   \
                           10 (FB=0)           10 (FB=-1)
                                                 \
                                                  15 (FB=0)

  FB(5)=-2, FB(filho dir 10)=-1 → caso RR → rotação esquerda em 5:

              10 (FB=0)
             /  \
            5    15

  ────────────────────────────────────────

  Inserir 3:          Inserir 8:
      10 (FB=+1)          10 (FB=+2) ← INVÁLIDO
     /  \                /   \
    5    15             5(FB=-1) 15
   /                   / \
  3 (FB=0)            3   8 (FB=0)

  FB(10)=+2, FB(filho esq 5)=-1 (< 0) → caso LR → dupla (esq em 5, dir em 10):
  z=10, x=5, y=8. ▲A={3}, ▲B=∅, ▲C=∅, ▲D={15}.

  Passo 1 — rotação esquerda em 5:
          10
         /  \
        8    15
       /
      5
     /
    3

  Passo 2 — rotação direita em 10:

          8 (FB=0)
         / \
        5   10
       /     \
      3       15

  Verificação: FB(8)=0, FB(5)=+1, FB(10)=-1, FB(3)=0, FB(15)=0. AVL válida.

7. Remoção na AVL

A remoção começa exatamente como na Abp: localiza o nó, trata os três casos (folha, um filho, dois filhos com substituição pelo sucessor em-ordem) e libera a memória. Na subida, cada ancestral tem sua altura atualizada e seu FB verificado — aplicando rotação onde necessário.

8. 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 AVL de altura h obedece a recorrência:

N(h) = N(h-1) + N(h-2) + 1,   com N(0)=1 e N(-1)=0.

(A pior AVL de altura h tem um filho com altura h−1 e outro com h−2 — diferença exata de 1 em todo nó.) Essa recorrência cresce como Fibonacci: N(h) ≈ φ^h / √5, onde φ ≈ 1,618. Invertendo:

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

Mesmo a pior AVL tem altura no máximo 44% maior que log₂ n. Para 1.000.000 de elementos: 1,44 × log₂(10⁶) ≈ 28 — contra 999.999 de uma Abp degenerada.

9. Complexidade das operações

O custo extra da AVL: um inteiro altura por nó e trabalho O(1) por nó visitado para atualizar a altura e verificar o FB.

10. Implementação completa — TAD AVL em C

/* ============================================================
   Estrutura do nó: igual ao NodoArv da Abp, mas com 'altura'.
   ============================================================ */
typedef struct str_NodoAvl NodoAvl;

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

/* Retorna -1 para NULL (convenção: folha=0, NULL=-1).
   Necessário para que 1 + max(h_esq, h_dir) funcione corretamente. */
int avlAltura(const NodoAvl *no) {
    if (no == NULL) return -1;
    return no->altura;
}

/* FB = h(esq) - h(dir). Positivo = pesado à esq; negativo = pesado à dir. */
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.
   Chamado sempre que um filho muda (inserção, remoção ou rotação). */
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; B (filho dir de x) passa para filho esq de y.
   Atualiza y primeiro (ficou abaixo), depois x. */
NodoAvl* avlRotDir(NodoAvl *y) {
    NodoAvl *x = y->esq;
    NodoAvl *B = x->dir;
    x->dir = y;
    y->esq = B;
    avlAtualizarAltura(y);
    avlAtualizarAltura(x);
    return x;
}

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

/* Verifica o FB e aplica a rotação correta.
   Usada tanto na inserção quanto na remoção. */
NodoAvl* avlReequilibrar(NodoAvl *raiz) {
    avlAtualizarAltura(raiz);
    int fb = avlFb(raiz);

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

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

    /* LR: pesado à esq, filho esq pesado à dir → transforma LR em LL */
    if (fb == +2 && avlFb(raiz->esq) < 0) {
        raiz->esq = avlRotEsq(raiz->esq);
        return avlRotDir(raiz);
    }

    /* RL: pesado à dir, filho dir pesado à esq → transforma RL em RR */
    if (fb == -2 && avlFb(raiz->dir) > 0) {
        raiz->dir = avlRotDir(raiz->dir);
        return avlRotEsq(raiz);
    }

    return raiz;   /* sem desequilíbrio */
}

/* Busca: idêntica à Abp — a altura garantida torna-a 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.
   No máximo uma rotação por inserção.
   Uso: raiz = avlInserir(raiz, produto); */
NodoAvl* avlInserir(NodoAvl *raiz, Produto valor) {
    if (raiz == NULL) {
        NodoAvl *novo = (NodoAvl*) malloc(sizeof(NodoAvl));
        novo->dado   = valor;
        novo->esq    = NULL;
        novo->dir    = NULL;
        novo->altura = 0;
        return novo;
    }
    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 */
    return avlReequilibrar(raiz);
}

/* Auxiliar: menor nó da 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.
   Podem ser necessárias múltiplas rotações (uma por nível desequilibrado).
   Uso: raiz = avlRemover(raiz, cod); */
NodoAvl* avlRemover(NodoAvl *raiz, int cod) {
    if (raiz == NULL) return NULL;

    if (cod < raiz->dado.cod) {
        raiz->esq = avlRemover(raiz->esq, cod);
    } else if (cod > raiz->dado.cod) {
        raiz->dir = avlRemover(raiz->dir, cod);
    } else {
        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 */
        NodoAvl *sucessor = avlMinimo(raiz->dir);
        raiz->dado = sucessor->dado;
        raiz->dir  = avlRemover(raiz->dir, sucessor->dado.cod);
    }
    return avlReequilibrar(raiz);
}

/* Destroi toda a árvore em 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;
}

1. Splay Tree — Árvore Auto-ajustável

A Splay Tree (Sleator e Tarjan, 1985) é uma Abp que, a cada acesso (busca, inserção ou remoção), move o nó acessado até a raiz por meio de um processo chamado splay. Não existe invariante de balanceamento explícito — nenhum campo extra por nó — mas a estrutura se auto-organiza de forma que elementos frequentemente acessados ficam perto da raiz e, por isso, baratos de acessar novamente.

2. A operação splay

O splay de um nó x repete os passos abaixo até x chegar à raiz. Em cada passo, analisa-se x, seu pai p e, se existir, seu avô g:

Em todos os casos, após o passo, x subiu dois níveis (ou um nível no caso Zig). Repete-se até x ser a raiz.

3. Diagramas dos três casos

──── ZIG (x filho esq de p = raiz) ─────────────────────────────────

      p (raiz)                   x
     / \           →            / \
    x   ▲C                    ▲A   p
   / \                             / \
  ▲A  ▲B                          ▲B  ▲C

  Rotação simples à direita em p. x torna-se a nova raiz.

──── ZIG-ZIG (x e p ambos filhos esquerdos) ─────────────────────────

         g                    p                    x
        / \                  / \                  / \
       p   ▲D    →          x   g      →        ▲A   p
      / \                  / \ / \                  / \
     x   ▲C               ▲A ▲B ▲C ▲D             ▲B   g
    / \                                                 / \
   ▲A  ▲B                                             ▲C  ▲D

  Passo 1: rot. dir. em g (sobe p). Passo 2: rot. dir. em p (sobe x).
  x sobe dois níveis; ▲B passa para filho esq de p; ▲C passa para filho esq de g.

──── ZIG-ZAG (x filho dir de p; p filho esq de g) ──────────────────

         g                    g                    x
        / \                  / \                  / \
       p   ▲D    →          x   ▲D    →          p   g
      / \                  / \                  / \ / \
     ▲A   x               p   ▲C              ▲A ▲B ▲C ▲D
         / \             / \
        ▲B  ▲C          ▲A  ▲B

  Passo 1: rot. esq. em p (x sobe). Passo 2: rot. dir. em g (x sobe de novo).
  Resultado igual à rotação dupla LR da AVL — mas o objetivo é levar x à raiz,
  não apenas equilibrar localmente.

4. Exemplo: splay(20) na árvore {10, 30, 5, 20, 35}

  Árvore inicial (inserção em ordem: 10, 30, 5, 20, 35):

          10
         /  \
        5    30
            /  \
           20   35

  splay(20): x=20, p=30, g=10.
  x é filho esq de p; p é filho dir de g → lados opostos → ZIG-ZAG.

  Passo 1 — rot. dir. em p=30:

          10
         /  \
        5    20
               \
                30
                  \
                   35

  Passo 2 — rot. esq. em g=10:

          20
         /  \
        10   30
       /       \
      5         35

  20 é a nova raiz. A árvore continua sendo uma Abp válida.

5. Inserção e remoção

Inserção: insere como numa Abp simples, depois aplica splay no novo nó.

Remoção de x:

1. Aplica splay(x) → x vai para a raiz.
2. Separa a árvore em duas: L (subárvore esquerda de x) e R (subárvore direita de x).
3. Remove x (libera o nó).
4. Aplica splay no maior elemento de L → esse elemento vai para a raiz de L e ficará sem filho direito.
5. Conecta R como filho direito da nova raiz de L. A árvore resultante é a nova raiz.

6. Complexidade amortizada

O splay não garante O(log n) por operação individual — uma busca num elemento profundo pode custar O(n). A garantia é amortizada: qualquer sequência de m operações em uma árvore de n elementos custa O((m + n) log n) no total, ou seja, O(log n) por operação em média.

7. Implementação completa — TAD Splay em C

/* =============================================================
   Nó da Splay Tree — mesmo struct da Abp, sem campo extra.
   ============================================================= */
typedef struct str_NodoSplay NodoSplay;

struct str_NodoSplay {
    int        cod;
    NodoSplay *esq;
    NodoSplay *dir;
};

/* Rotação simples à direita — x sobe, y desce.
   Retorna o novo nó raiz da subárvore. */
NodoSplay* splayRotDir(NodoSplay *y) {
    NodoSplay *x = y->esq;
    y->esq = x->dir;
    x->dir = y;
    return x;
}

/* Rotação simples à esquerda — y sobe, x desce. */
NodoSplay* splayRotEsq(NodoSplay *x) {
    NodoSplay *y = x->dir;
    x->dir = y->esq;
    y->esq = x;
    return y;
}

/* splay(raiz, cod): leva o nó com chave 'cod' até a raiz.
   Se 'cod' não existe, leva o último nó visitado (predecessor ou
   sucessor) — comportamento padrão para inserção e remoção.
   Retorna a nova raiz da árvore. */
NodoSplay* splay(NodoSplay *raiz, int cod) {
    if (raiz == NULL || raiz->cod == cod)
        return raiz;

    if (cod < raiz->cod) {
        if (raiz->esq == NULL) return raiz;          /* não existe */

        if (cod < raiz->esq->cod) {                       /* Zig-zig esq */
            raiz->esq->esq = splay(raiz->esq->esq, cod);
            raiz = splayRotDir(raiz);
        } else if (cod > raiz->esq->cod) {              /* Zig-zag esq-dir */
            raiz->esq->dir = splay(raiz->esq->dir, cod);
            if (raiz->esq->dir != NULL)
                raiz->esq = splayRotEsq(raiz->esq);
        }
        return (raiz->esq == NULL) ? raiz : splayRotDir(raiz);  /* Zig */

    } else {
        if (raiz->dir == NULL) return raiz;          /* não existe */

        if (cod > raiz->dir->cod) {                       /* Zig-zig dir */
            raiz->dir->dir = splay(raiz->dir->dir, cod);
            raiz = splayRotEsq(raiz);
        } else if (cod < raiz->dir->cod) {              /* Zig-zag dir-esq */
            raiz->dir->esq = splay(raiz->dir->esq, cod);
            if (raiz->dir->esq != NULL)
                raiz->dir = splayRotDir(raiz->dir);
        }
        return (raiz->dir == NULL) ? raiz : splayRotEsq(raiz);  /* Zig */
    }
}

/* Busca: faz splay do nó buscado (ou do mais próximo).
   Retorna 1 se encontrado, 0 caso contrário.
   Uso: raiz = splayBuscar(raiz, cod, &encontrado); */
NodoSplay* splayBuscar(NodoSplay *raiz, int cod, int *encontrado) {
    raiz = splay(raiz, cod);
    *encontrado = (raiz != NULL && raiz->cod == cod);
    return raiz;
}

/* Inserção: splay da chave → se já existe, ignora.
   Caso contrário cria nó e o coloca na raiz reorganizando a árvore.
   Uso: raiz = splayInserir(raiz, cod); */
NodoSplay* splayInserir(NodoSplay *raiz, int cod) {
    if (raiz == NULL) {
        NodoSplay *novo = (NodoSplay*) malloc(sizeof(NodoSplay));
        novo->cod = cod; novo->esq = NULL; novo->dir = NULL;
        return novo;
    }
    raiz = splay(raiz, cod);
    if (raiz->cod == cod) return raiz;   /* duplicado */

    NodoSplay *novo = (NodoSplay*) malloc(sizeof(NodoSplay));
    novo->cod = cod;
    if (cod < raiz->cod) {
        novo->dir = raiz;
        novo->esq = raiz->esq;
        raiz->esq = NULL;
    } else {
        novo->esq = raiz;
        novo->dir = raiz->dir;
        raiz->dir = NULL;
    }
    return novo;
}

/* Auxiliar: maior nó da subárvore. */
NodoSplay* splayMaximo(NodoSplay *raiz) {
    while (raiz->dir != NULL) raiz = raiz->dir;
    return raiz;
}

/* Remoção: splay da chave → separa L e R → une via maior de L.
   Uso: raiz = splayRemover(raiz, cod); */
NodoSplay* splayRemover(NodoSplay *raiz, int cod) {
    if (raiz == NULL) return NULL;
    raiz = splay(raiz, cod);
    if (raiz->cod != cod) return raiz;   /* não encontrado */

    NodoSplay *esq = raiz->esq;
    NodoSplay *dir = raiz->dir;
    free(raiz);

    if (esq == NULL) return dir;
    /* Splay do maior de L → raiz de L ficará sem filho dir */
    esq = splay(esq, splayMaximo(esq)->cod);
    esq->dir = dir;
    return esq;
}

/* Destroi toda a árvore em pós-ordem.
   Uso: raiz = splayDestruir(raiz); */
NodoSplay* splayDestruir(NodoSplay *raiz) {
    if (raiz == NULL) return NULL;
    raiz->esq = splayDestruir(raiz->esq);
    raiz->dir = splayDestruir(raiz->dir);
    free(raiz);
    return NULL;
}

Resumo

Exercícios

1. Insira os valores 10, 20, 30 em uma AVL vazia. Mostre a árvore após cada inserção, identifique o caso de desequilíbrio e aplique a rotação correta.
2. Insira os valores 30, 10, 20 em uma AVL vazia. Mostre a árvore após cada inserção, identifique o caso e aplique as rotações necessárias.
3. Insira os valores 10, 30, 20 em uma AVL vazia. Qual caso de desequilíbrio ocorre? Como é diferente do exercício anterior?
4. Insira os valores 5, 10, 15, 20, 25 em uma AVL vazia. Mostre cada reequilíbrio (pode haver mais de um).
5. Explique por que uma inserção exige no máximo uma rotação (simples ou dupla), mas uma remoção pode exigir rotações em vários níveis.
6. Dada uma AVL com os valores 20, 10, 30, 5, 15, 25, 35: remova o nó 35 e depois o nó 30. Mostre o estado da árvore após cada remoção e aplique os reequilíbrios necessários.
7. Por que guardamos a altura em cada nó em vez do fator de balanceamento diretamente?
8. A altura de uma 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 10:  10(FB=0)
Após 20:  10(FB=-1) → 20(FB=0)
Após 30:  10(FB=-2) ← INVÁLIDO
            \
             20(FB=-1)
               \
                30

FB(x=10)=-2, FB(y=20)=-1 → caso RR → rotação esquerda em 10.
     20
    /  \
   10   30
FB(20)=0, FB(10)=0, FB(30)=0. AVL válida.

Após 30:  30(FB=0)
Após 10:  30(FB=+1)
           /
          10(FB=0)
Após 20:  30(FB=+2) ← INVÁLIDO   z=30, x=10, y=20
           /
          10(FB=-1)
            \
             20

FB(z=30)=+2, FB(x=10)=-1 → caso LR → dupla (esq em 10, dir em 30).

Passo 1 — rot. esq. em 10:   30
                             /
                            20
                           /
                          10

Passo 2 — rot. dir. em 30:   20
                             /  \
                            10   30
Resultado válido.