Árvores AVL: Rotações, Inserção, Exclusão com C++ Exemplo

⚡ Resumo Inteligente

As árvores AVL são árvores de busca binária auto-balanceadas onde a diferença de altura entre as subárvores esquerda e direita de cada nó permanece dentro de -1, 0 ou +1, garantindo um desempenho de busca de O(log n).

🌲 Definição: Uma árvore de busca binária na qual o fator de balanceamento de cada nó está no intervalo {-1, 0, +1}, nomeada em homenagem aos seus inventores, Adelson-Velsky e Landis.
⚖️ Fator de equilíbrio: Calculado como altura(esquerda) − altura(direita); valores fora de {-1, 0, +1} acionam uma rotação para restaurar o equilíbrio.
🔄 Rotações: Quatro casos — LL, RR, LR e RL — realinham os nós após inserções ou exclusões desbalanceadas para manter a árvore logarítmica em altura.
➕ Inserção: Inserção BST padrão seguida de um deslocamento ascendente que recalcula os fatores de equilíbrio e realiza, no máximo, uma rotação simples ou dupla.
➖ Eliminação: Semelhante à exclusão de BST, mas pode desencadear múltiplas rotações em cascata na árvore, pois a altura da subárvore pode diminuir a cada ancestral.
🚀 Aplicações: Bancos de dados, índices em memória, metadados do sistema de arquivos e estruturas de busca de IA usam árvores AVL para pesquisas ordenadas rápidas.

Saiba Mais

O que são árvores AVL?

Árvores AVL São árvores de busca binária nas quais a diferença de altura entre as subárvores esquerda e direita de cada nó é -1, 0 ou +1. São árvores de busca binária auto-balanceadas que mantêm um tempo de busca logarítmico, nomeadas em homenagem aos seus inventores, Adelson-Velsky e Landis (AVL).

Como funciona a árvore AVL?

Para entender por que as árvores AVL existem, observe o que dá errado com uma árvore simples. Árvore de pesquisa bináriaConsidere estas chaves inseridas na ordem indicada:

Visualização da árvore AVL

A árvore cresce linearmente quando as chaves chegam em ordem crescente, degenerando a busca em O(n). Isso anula o propósito de uma BST — somente uma árvore balanceada mantém a busca logarítmica. Agora observe as mesmas chaves inseridas em uma ordem diferente.

As mesmas chaves, mas com ordem de inserção diferente, resultam em uma forma mais rasa, de modo que cada busca é executada em O(log n). As árvores AVL impõem essa forma monitorando a altura a cada inserção e corrigindo o desequilíbrio sem quebrar a ordenação da BST.

Fator de equilíbrio em árvores AVL

O fator de equilíbrio (FE) tracks mede a altura de cada nó para que a árvore possa se autoequilibrar dinamicamente.

Propriedades do fator de equilíbrio

Árvore AVL do fator de equilíbrio

O fator de balanceamento é a diferença entre a altura da subárvore esquerda e a altura da subárvore direita.
Balance factor(node) = height(node->left) − height(node->right)
Os únicos valores permitidos são −1, 0 e +1.
Um valor de −1 significa que a subárvore direita contém um nível extra — o nó é pesado à direita.
Um valor de +1 significa que a subárvore esquerda contém um nível extra — o nó é pesado à esquerda.
Um valor de 0 significa que ambos os lados têm a mesma altura — o nó está perfeitamente equilibrado.

Rotações AVL

As rotações são executadas sempre que uma inserção ou exclusão viola a regra do fator de balanceamento. Os quatro casos são LL, RR, LR e RL.

Esquerda – Rotação Esquerda

Esta rotação é realizada quando um novo nó é inserido no filho esquerdo da subárvore esquerda.

Árvore AVL Esquerda – Rotação Esquerda

É realizada uma única rotação à direita. Este caso ocorre quando um nó tem BF +2 e seu filho esquerdo tem BF +1.

Direita – Rotação Direita

Esta rotação é realizada quando um novo nó é inserido no filho direito da subárvore direita.

É realizada uma única rotação para a esquerda. Este caso ocorre quando um nó tem BF −2 e seu filho direito tem BF −1.

Direita – Rotação Esquerda

Esta rotação é realizada quando um novo nó é inserido no filho esquerdo da subárvore direita.

É acionado quando BF(nó) = −2 e BF(filho-direito) = +1. Rotaciona o filho-direito para a direita e, em seguida, rotaciona o nó para a esquerda.

Esquerda – Rotação Direita

Esta rotação é realizada quando um novo nó é inserido no filho direito da subárvore esquerda.

É acionado quando BF(nó) = +2 e BF(filho-esquerdo) = −1. Rotaciona o filho-esquerdo para a esquerda e, em seguida, rotaciona o nó para a direita.

Inserção em árvores AVL

A inserção é quase idêntica a uma inserção simples em uma árvore binária de busca (BST). Após cada inserção, a árvore percorre seu caminho para cima e se reequilibra. A inserção tem complexidade de tempo O(log n) no pior caso.

Implementação de inserção de árvore AVL

Passo 1: Insira o nó usando o algoritmo BST padrão. No exemplo acima, insira 160.

Passo 2: Atualize o fator de balanceamento de cada ancestral ao longo do caminho de inserção.

Passo 3: Se algum ancestral violar o intervalo do fator de balanceamento, execute a rotação correspondente. No exemplo, o fator de balanceamento do nó 350 está violado, portanto, uma rotação LL restaura o equilíbrio.

If BF(node) = +2 e BF(left-child) = +1, realize rotação LL.
If BF(node) = −2 e BF(right-child) = −1, realize rotação RR.
If BF(node) = −2 e BF(right-child) = +1, execute a rotação RL.
If BF(node) = +2 e BF(left-child) = −1, realize rotação LR.

Exclusão em árvores AVL

A exclusão segue a mesma lógica de uma BST simples e é reequilibrada posteriormente.

Passo 1: Encontre o elemento na árvore.

Passo 2: Exclua o nó usando o método padrão de exclusão de BST (Árvore Binária de Busca).

Passo 3: Dois casos são possíveis.

Caso 1: Excluindo da subárvore direita.

1A. If BF(node) = +2 e BF(left-child) = +1, realize rotação LL.
1B. If BF(node) = +2 e BF(left-child) = −1, realize rotação LR.
1C. If BF(node) = +2 e BF(left-child) = 0, realize rotação LL.

Caso 2: Excluindo da subárvore esquerda.

2A. If BF(node) = −2 e BF(right-child) = −1, realize rotação RR.
2B. If BF(node) = −2 e BF(right-child) = +1, execute a rotação RL.
2C. If BF(node) = −2 e BF(right-child) = 0, realize rotação RR.

C++ Exemplo de árvores AVL

Abaixo está uma C++ Programa que implementa árvores AVL:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;
};

class AVL {
public:
    struct node *root;

    AVL() {
        this->root = NULL;
    }

    int calheight(struct node *p) {
        if (p->left && p->right) {
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else
                return p->left->height + 1;
        }
        else if (p->left && p->right == NULL) {
            return p->left->height + 1;
        }
        else if (p->left == NULL && p->right) {
            return p->right->height + 1;
        }
        return 0;
    }

    int bf(struct node *n) {
        if (n->left && n->right)
            return n->left->height - n->right->height;
        else if (n->left && n->right == NULL)
            return n->left->height;
        else if (n->left == NULL && n->right)
            return -n->right->height;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *tp2 = p->right->left;
        p->right = tp2->left;
        tp->left = tp2->right;
        tp2->left = p;
        tp2->right = tp;
        return tp2;
    }

    struct node *lrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        struct node *tp2 = p->left->right;
        p->left = tp2->right;
        tp->right = tp2->left;
        tp2->right = p;
        tp2->left = tp;
        return tp2;
    }

    struct node *insert(struct node *r, int data) {
        if (r == NULL) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        if (data < r->data)
            r->left = insert(r->left, data);
        else
            r->right = insert(r->right, data);

        r->height = calheight(r);

        if (bf(r) == 2 && bf(r->left) == 1)       r = llrotation(r);
        else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r);
        else if (bf(r) == -2 && bf(r->right) == 1)  r = rlrotation(r);
        else if (bf(r) == 2 && bf(r->left) == -1)   r = lrrotation(r);

        return r;
    }

    void levelorder_newline() {
        if (this->root == NULL) {
            cout << "\nEmpty tree\n";
            return;
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v) {
        queue<struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            if (cur == NULL && q.size() != 0) {
                cout << "\n";
                q.push(NULL);
                continue;
            }
            if (cur != NULL) {
                cout << " " << cur->data;
                if (cur->left != NULL)  q.push(cur->left);
                if (cur->right != NULL) q.push(cur->right);
            }
        }
    }

    struct node *deleteNode(struct node *p, int data) {
        if (p->left == NULL && p->right == NULL) {
            if (p == this->root) this->root = NULL;
            delete p;
            return NULL;
        }
        struct node *q;
        if (p->data < data)      p->right = deleteNode(p->right, data);
        else if (p->data > data) p->left  = deleteNode(p->left, data);
        else {
            if (p->left != NULL) {
                q = inpre(p->left);
                p->data = q->data;
                p->left = deleteNode(p->left, q->data);
            } else {
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right, q->data);
            }
        }

        if (bf(p) == 2 && bf(p->left) == 1)         p = llrotation(p);
        else if (bf(p) == 2 && bf(p->left) == -1)    p = lrrotation(p);
        else if (bf(p) == 2 && bf(p->left) == 0)     p = llrotation(p);
        else if (bf(p) == -2 && bf(p->right) == -1)  p = rrrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 1)   p = rlrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 0)   p = rrrotation(p);

        return p;
    }

    struct node *inpre(struct node *p) {
        while (p->right != NULL) p = p->right;
        return p;
    }

    struct node *insuc(struct node *p) {
        while (p->left != NULL) p = p->left;
        return p;
    }

    ~AVL() {}
};

int main() {
    AVL b;
    int c, x;
    do {
        cout << "\n1.Display levelorder on newline";
        cout << "\n2.Insert";
        cout << "\n3.Delete\n";
        cout << "\n0.Exit\n";
        cout << "\nChoice: ";
        cin >> c;
        switch (c) {
        case 1: b.levelorder_newline(); break;
        case 2:
            cout << "\nEnter no. "; cin >> x;
            b.root = b.insert(b.root, x);
            break;
        case 3:
            cout << "\nWhat to delete? "; cin >> x;
            b.root = b.deleteNode(b.root, x);
            break;
        case 0: break;
        }
    } while (c != 0);
}

Exemplo de execução do código acima:

Copie o código acima e salve-o em um arquivo chamado avl.cpp.
Compile o código:

g++ avl.cpp -o run

Execute o código.

./run

Vantagens das árvores AVL

A altura da árvore AVL está sempre equilibrada e nunca cresce além do tronco N.
A busca é mais rápida do que em uma árvore de busca binária simples porque a árvore não pode degenerar.
O autoequilíbrio é automático — nenhuma etapa de reconstrução é necessária.
O desempenho determinístico é adequado para sistemas em tempo real e índices em memória.

Perguntas Frequentes

Uma árvore AVL é uma árvore binária de busca auto-balanceada onde o fator de balanceamento de cada nó permanece em {-1, 0, +1}. Rotações restauram essa invariante a cada inserção ou exclusão, mantendo o equilíbrio.ping pesquisar, inserir e excluir em O(log n).

O fator de balanceamento de um nó é igual à altura da subárvore esquerda menos a altura da subárvore direita. Os valores devem estar no intervalo {-1, 0, +1}. Um fator de balanceamento de +2 ou -2 indica que uma inserção ou exclusão desbalanceou o nó e que uma rotação é necessária.

As quatro rotações são LL, RR, LR e RL. LL usa uma única rotação para a direita, RR usa uma única rotação para a esquerda, e LR e RL são rotações duplas que combinam uma rotação no filho com uma rotação oposta no nó.

A inserção segue a regra padrão da Árvore Binária de Busca (BST), e então a árvore percorre o caminho inverso, atualizando as alturas. Se algum ancestral violar a regra de balanceamento, uma rotação simples ou dupla restaura o equilíbrio. No máximo, uma rotação por inserção é necessária.

As árvores AVL são estritamente balanceadas com um fator de balanceamento de no máximo um, proporcionando buscas mais rápidas. As árvores rubro-negras permitem um balanceamento menos rigoroso, o que torna as operações de inserção e exclusão mais baratas, mas as buscas um pouco mais lentas. Bancos de dados preferem árvores rubro-negras para cargas de trabalho com grande volume de escrita.

As árvores AVL são a base de índices de banco de dados em memória, metadados de sistemas de arquivos, filas de prioridade, pesquisas em listas telefônicas, corretores ortográficos e qualquer carga de trabalho que precise de pesquisa determinística O(log n) mais percurso em ordem para consultas de intervalo.

Sim. Os sistemas de IA usam árvores AVL para tabelas de símbolos, armazenamento de recursos ordenados, balanceamento de árvores kd e buscas por vizinhos mais próximos em dados estruturados. Elas também são a base de índices de recuperação classificados em fluxos de busca inteligentes.

Sim. O GitHub Copilot e assistentes de IA semelhantes criam rotinas de inserção, exclusão e rotação em C++, Java, ou Pythone gerar testes unitários que verifiquem a invariância do fator de balanceamento em cada operação.