Árvores AVL

1. O Problema da BST “Degenerada”

Como vimos, se inserirmos 1, 2, 3, 4 em uma BST, ela vira uma Linha Reta com altura \(N\). A busca degrada para \(O(N)\). Para resolver isso, G.M. Adelson-Velsky e E.M. Landis criaram, em 1962, a primeira árvore balanceada auto-ajustável.

2. Invariante da AVL

Uma BST é uma AVL se, para todo nó, a diferença de altura entre a subárvore esquerda e a direita (Fator de Balanceamento) é no máximo 1.

\[ FB(nó) = h(direita) - h(esquerda) \] \[ FB \in \{-1, 0, +1\} \]

Se, após uma inserção ou remoção, algum nó ficar com \(|FB| > 1\), precisamos consertá-lo.

3. Implementação: Calculando Altura

Diferente da BST comum, cada nó da AVL precisa armazenar sua própria altura para evitar recalcular recursivamente (o que seria \(O(N)\)).

class Node {
    int key, height;
    Node left, right;
    
    Node(int d) {
        key = d;
        height = 1; // Nó novo é folha, altura 1
    }
}

int height(Node N) {
    if (N == null) return 0;
    return N.height;
}

int getBalance(Node N) {
    if (N == null) return 0;
    return height(N.right) - height(N.left);
}

4. As Rotações

As rotações são as operações mágicas que reduzem a altura da árvore localmente mantendo a ordem da BST (\(mq < Raiz < Mq\)).

4.1. Rotação Simples à Direita (Right Rotate)

Usada quando o desbalanceamento é na Esquerda-Esquerda (O filho esquerdo está pesado na esquerda).

graph TD
    y((y)) --> x((x))
    y --> T3
    x --> T1
    x --> T2

Vira:

graph TD
    x((x)) --> T1
    x --> y((y))
    y --> T2
    y --> T3

Código Java:

Node rightRotate(Node y) {
    // Definindo variáveis
    Node x = y.left;
    Node T2 = x.right;

    // A Rotação em si (troca de ponteiros)
    x.right = y;
    y.left = T2;

    // Atualiza alturas (primeiro y, que desceu, depois x)
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;

    // Nova raiz
    return x;
}

4.2. Rotação Simples à Esquerda (Left Rotate)

Simétrica à anterior. Usada para desbalanceamento Direita-Direita.

Node leftRotate(Node x) {
    Node y = x.right;
    Node T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;

    return y;
}

4.3. Rotação Dupla

Se o filho pesado tiver o “peso” no lado interno, a rotação simples não resolve (cria um “joelho”). Precisamos de duas rotações.

Caso Esquerda-Direita: 1. Rotaciona o filho esquerdo para a esquerda (leftRotate(node.left)). 2. Rotaciona o nó atual para a direita.

Caso Direita-Esquerda: 1. Rotaciona o filho direito para a direita. 2. Rotaciona o nó atual para a esquerda.

5. Inserção Completa

Node insert(Node node, int key) {
    // 1. Inserção normal de BST
    if (node == null) return (new Node(key));

    if (key < node.key)
        node.left = insert(node.left, key);
    else if (key > node.key)
        node.right = insert(node.right, key);
    else
        return node; // Chaves duplicadas não permitidas

    // 2. Atualiza altura do ancestral
    node.height = 1 + Math.max(height(node.left), height(node.right));

    // 3. Verifica Balanceamento
    int balance = getBalance(node);

    // 4. Aplica Rotações se necessário

    // Caso Esquerda-Esquerda
    if (balance < -1 && key < node.left.key)
        return rightRotate(node);

    // Caso Direita-Direita
    if (balance > 1 && key > node.right.key)
        return leftRotate(node);

    // Caso Esquerda-Direita (Joelho)
    if (balance < -1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // Caso Direita-Esquerda (Joelho)
    if (balance > 1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

6. AVL vs Árvore Rubro-Negra

Característica AVL Rubro-Negra (Red-Black)
Balanceamento Rígido (fator \(\le 1\)). Relaxado (caminho mais longo \(\le 2 \times\) curto).
Altura da Árvore Menor (\(\approx 1.44 \log N\)). Maior (\(\approx 2 \log N\)).
Busca (Lookup) Mais rápida. Levemente mais lenta.
Inserção/Remoção Mais lenta (muitas rotações). Mais rápida.
Uso Real Bancos de dados com muita leitura. java.util.TreeMap, C++ std::map (Geral).

Conclusão

A AVL é excelente para cenários Read-Heavy (muitas buscas, poucas alterações). Se houver muitas escritas, a Árvore Rubro-Negra é preferível.

Back to top