Compreendendo as Árvores Binárias de Busca Balanceadas (AVL)
Uma Árvore AVL, ou árvore binária de busca balanceada, é uma estrutura de dados essencial que otimiza as operações de busca, inserção e remoção, garantnido que elas sempre ocorram em tempo logarítmico. A chave para essa eficiência é o mecanismo de balanceamento que a árvore mantém continuamente.
A característica definidora de uma árvore AVL é o seu "fator de balanceamento". Para qualquer nó na árvore, este fator é calculado como a diferença entre a altura de sua subárvore esquerda e a altura de sua subárvore direita. Para que uma árvore seja considerada AVL, o valor absoluto do fator de balanceamento de cada nó deve ser no máximmo 1 (ou seja, pode ser -1, 0 ou 1).
Fundamentos: A Árvore Binária de Busca (BST)
As Árvores AVL são uma evolução das Árvores Binárias de Busca (BSTs). Uma BST é definida por ter, para cada nó, todos os valores na subárvore esquerda menores que o seu próprio valor, e todos os valores na subárvore direita maiores que o seu próprio valor. Ambas as subárvores também devem ser BSTs.
Embora as BSTs sejam eficientes em cenários médios, elas podem degenerar em uma estrutura semelhante a uma lista encadeada (por exemplo, ao enserir elementos em ordem estritamente crescente ou decrescente). Nesses casos, as operações podem levar a uma complexidade de tempo linear, o que as AVL evitam.
A seguir, uma classe básica para um nó de árvore e uma implementação de uma Árvore Binária de Busca simples:
class No {
int chave;
No filhoEsquerdo;
No filhoDireito;
int altura; // Armazena a altura do nó para facilitar o cálculo do balanceamento em AVL
public No(int valor) {
this.chave = valor;
this.altura = 1; // Um nó recém-criado (folha) tem altura 1
}
}
public class ArvoreBinariaBusca {
No raiz;
public ArvoreBinariaBusca() {
this.raiz = null;
}
// Auxiliar para obter a altura de um nó (0 se nulo)
private int obterAltura(No no) {
return (no == null) ? 0 : no.altura;
}
// Auxiliar para recalcular e atualizar a altura de um nó
private void atualizarAltura(No no) {
if (no != null) {
no.altura = 1 + Math.max(obterAltura(no.filhoEsquerdo), obterAltura(no.filhoDireito));
}
}
// Insere um novo valor na BST. Retorna a raiz da subárvore modificada.
public No inserir(No noAtual, int valor) {
if (noAtual == null) {
return new No(valor);
}
if (valor < noAtual.chave) {
noAtual.filhoEsquerdo = inserir(noAtual.filhoEsquerdo, valor);
} else if (valor > noAtual.chave) { // Permite que duplicatas vão para a direita, ou pode-se ignorar
noAtual.filhoDireito = inserir(noAtual.filhoDireito, valor);
}
// Se valor == noAtual.chave, o nó já existe; não faz nada ou trata como duplicata.
atualizarAltura(noAtual); // Atualiza a altura do nó atual após a inserção recursiva
return noAtual;
}
// Exemplo de percurso em ordem (valores impressos em ordem crescente)
public void percursoEmOrdem(No no) {
if (no != null) {
percursoEmOrdem(no.filhoEsquerdo);
System.out.print(no.chave + " ");
percursoEmOrdem(no.filhoDireito);
}
}
}
Mantendo o Balanceamento em Árvores AVL
Cálculo da Altura e Fator de Balanceamento
Para garantir que a propriedade AVL seja mantida, cada nó precisa ter sua altura atualizada e seu fator de balanceamento verificado. As alturas são armazenadas em cada nó para acesso eficiente.
// Estes métodos seriam parte da classe ArvoreAVL
class ArvoreAVL {
No raiz; // A raiz da árvore AVL
public ArvoreAVL() {
this.raiz = null;
}
// Retorna a altura de um nó. Se o nó for nulo, a altura é 0.
private int obterAltura(No no) {
return (no == null) ? 0 : no.altura;
}
// Recalcula e atualiza a altura de um nó com base nas alturas de seus filhos.
private void atualizarAltura(No no) {
if (no != null) {
no.altura = 1 + Math.max(obterAltura(no.filhoEsquerdo), obterAltura(no.filhoDireito));
}
}
// Calcula o fator de balanceamento de um nó: altura(esquerda) - altura(direita).
// Um valor positivo indica uma subárvore esquerda mais alta; negativo, direita mais alta.
private int obterFatorBalanceamento(No no) {
if (no == null) {
return 0;
}
return obterAltura(no.filhoEsquerdo) - obterAltura(no.filhoDireito);
}
// ... (restante da classe ArvoreAVL)
}
Rotações: O Mecanismo de Rebalanceamento
Quando uma operação (como inserção ou remoção) causa um desequilíbrio (fator de balanceamento > 1 ou < -1), a árvore deve ser rebalanceada através de uma ou mais "rotações". Existem quatro casos de desequilíbrio que correspondem a diferentes tipos de rotações.
1. Rotação Simples à Direita (Caso LL - Left-Left)
Esta rotação é aplicada quando o desequilíbrio ocorre na subárvore esquerda do filho esquerdo do nó desbalanceado.
// Realiza uma rotação simples à direita no nó 'y'
private No rotacionarDireita(No y) {
No x = y.filhoEsquerdo;
No T2 = x.filhoDireito;
// Ajusta os ponteiros para realizar a rotação
x.filhoDireito = y;
y.filhoEsquerdo = T2;
// Atualiza as alturas dos nós 'y' e 'x'
atualizarAltura(y);
atualizarAltura(x);
return x; // 'x' torna-se a nova raiz da subárvore
}
2. Rotação Simples à Esquerda (Caso RR - Right-Right)
Esta rotação é aplicada quando o desequilíbrio ocorre na subárvore direita do filho direito do nó desbalanceado.
// Realiza uma rotação simples à esquerda no nó 'x'
private No rotacionarEsquerda(No x) {
No y = x.filhoDireito;
No T2 = y.filhoEsquerdo;
// Ajusta os ponteiros para realizar a rotação
y.filhoEsquerdo = x;
x.filhoDireito = T2;
// Atualiza as alturas dos nós 'x' e 'y'
atualizarAltura(x);
atualizarAltura(y);
return y; // 'y' torna-se a nova raiz da subárvore
}
3. Rotação Dupla Esquerda-Direita (Caso LR - Left-Right)
Este cenário ocorre quando o desequilíbrio se encontra na subárvore direita do filho esquerdo. É corrigido com uma rotação à esquerda no filho esquerdo, seguida por uma rotação à direita no nó original.
// Rotação LR: Primeiro rotaciona à esquerda no filho esquerdo, depois à direita no nó atual
private No rotacaoEsquerdaDireita(No no) {
no.filhoEsquerdo = rotacionarEsquerda(no.filhoEsquerdo);
return rotacionarDireita(no);
}
4. Rotação Dupla Direita-Esquerda (Caso RL - Right-Left)
Este cenário ocorre quando o desequilíbrio se encontra na subárvore esquerda do filho direito. É corrigido com uma rotação à direita no filho direito, seguida por uma rotação à esquerda no nó original.
// Rotação RL: Primeiro rotaciona à direita no filho direito, depois à esquerda no nó atual
private No rotacaoDireitaEsquerda(No no) {
no.filhoDireito = rotacionarDireita(no.filhoDireito);
return rotacionarEsquerda(no);
}
Inserção de Elementos em uma Árvore AVL
O processo de inserção em uma árvore AVL começa como uma inserção padrão de BST. No entanto, à medida que a chamada recursiva retorna, a altura de cada nó é atualizada e seu fator de balanceamento é verificado. Se um desequilíbrio for detectado, as rotações apropriadas são aplicadas para restaurar a propriedade AVL.
public class ArvoreAVL {
No raiz;
public ArvoreAVL() {
this.raiz = null;
}
// Métodos auxiliares (obterAltura, atualizarAltura, obterFatorBalanceamento, rotacionarDireita, rotacionarEsquerda)
// são omitidos aqui por brevidade, mas devem ser implementados conforme mostrado acima.
private int obterAltura(No no) { /* ... */ return (no == null) ? 0 : no.altura; }
private void atualizarAltura(No no) { /* ... */ if (no != null) { no.altura = 1 + Math.max(obterAltura(no.filhoEsquerdo), obterAltura(no.filhoDireito)); }}
private int obterFatorBalanceamento(No no) { /* ... */ if (no == null) return 0; return obterAltura(no.filhoEsquerdo) - obterAltura(no.filhoDireito); }
private No rotacionarDireita(No y) { /* ... */
No x = y.filhoEsquerdo;
No T2 = x.filhoDireito;
x.filhoDireito = y;
y.filhoEsquerdo = T2;
atualizarAltura(y);
atualizarAltura(x);
return x;
}
private No rotacionarEsquerda(No x) { /* ... */
No y = x.filhoDireito;
No T2 = y.filhoEsquerdo;
y.filhoEsquerdo = x;
x.filhoDireito = T2;
atualizarAltura(x);
atualizarAltura(y);
return y;
}
private No rotacaoEsquerdaDireita(No no) { /* ... */
no.filhoEsquerdo = rotacionarEsquerda(no.filhoEsquerdo);
return rotacionarDireita(no);
}
private No rotacaoDireitaEsquerda(No no) { /* ... */
no.filhoDireito = rotacionarDireita(no.filhoDireito);
return rotacionarEsquerda(no);
}
// Método recursivo para inserir um nó na árvore AVL
public No inserirNo(No noAtual, int valor) {
// 1. Executa a inserção padrão de uma Árvore Binária de Busca
if (noAtual == null) {
return new No(valor);
}
if (valor < noAtual.chave) {
noAtual.filhoEsquerdo = inserirNo(noAtual.filhoEsquerdo, valor);
} else if (valor > noAtual.chave) {
noAtual.filhoDireito = inserirNo(noAtual.filhoDireito, valor);
} else {
return noAtual; // Chaves duplicadas geralmente não são permitidas ou tratadas de forma específica
}
// 2. Atualiza a altura do nó pai
atualizarAltura(noAtual);
// 3. Obtém o fator de balanceamento deste nó para verificar o desequilíbrio
int fatorBalanceamento = obterFatorBalanceamento(noAtual);
// 4. Se o nó estiver desbalanceado, aplica a rotação apropriada
// Caso LL (Left-Left)
if (fatorBalanceamento > 1 && valor < noAtual.filhoEsquerdo.chave) {
return rotacionarDireita(noAtual);
}
// Caso RR (Right-Right)
if (fatorBalanceamento < -1 && valor > noAtual.filhoDireito.chave) {
return rotacionarEsquerda(noAtual);
}
// Caso LR (Left-Right)
if (fatorBalanceamento > 1 && valor > noAtual.filhoEsquerdo.chave) {
noAtual.filhoEsquerdo = rotacionarEsquerda(noAtual.filhoEsquerdo); // Rotação Esquerda no filho esquerdo
return rotacionarDireita(noAtual); // Rotação Direita no nó atual
}
// Caso RL (Right-Left)
if (fatorBalanceamento < -1 && valor < noAtual.filhoDireito.chave) {
noAtual.filhoDireito = rotacionarDireita(noAtual.filhoDireito); // Rotação Direita no filho direito
return rotacionarEsquerda(noAtual); // Rotação Esquerda no nó atual
}
return noAtual; // Retorna o nó (potencialmente rebalanceado)
}
// Método público para adicionar um valor à árvore AVL
public void adicionar(int valor) {
this.raiz = inserirNo(this.raiz, valor);
}
// Método para percorrer a árvore em ordem e imprimir os nós com suas alturas e fatores de balanceamento
public void percursoEmOrdem(No no) {
if (no != null) {
percursoEmOrdem(no.filhoEsquerdo);
System.out.print(no.chave + "(h:" + no.altura + " bf:" + obterFatorBalanceamento(no) + ") ");
percursoEmOrdem(no.filhoDireito);
}
}
// Verifica se a árvore inteira está balanceada (útil para testes)
public boolean verificarBalanceamento(No no) {
if (no == null) {
return true;
}
int bf = obterFatorBalanceamento(no);
if (Math.abs(bf) > 1) {
return false; // Nó desbalanceado encontrado
}
// Verifica recursivamente as subárvores
return verificarBalanceamento(no.filhoEsquerdo) && verificarBalanceamento(no.filhoDireito);
}
}
public class ExemploAVL {
public static void main(String[] args) {
ArvoreAVL arvore = new ArvoreAVL();
int[] valoresParaInserir = {10, 20, 30, 40, 50, 25};
System.out.println("--- Inserindo elementos na Arvore AVL ---");
for (int val : valoresParaInserir) {
arvore.adicionar(val);
System.out.println("Após inserir " + val + ":");
arvore.percursoEmOrdem(arvore.raiz);
System.out.println("\nRaiz atual: " + arvore.raiz.chave +
", Altura da raiz: " + arvore.obterAltura(arvore.raiz) +
", Balanceada: " + arvore.verificarBalanceamento(arvore.raiz));
System.out.println("---------------------------------");
}
System.out.println("\n--- Percurso em ordem da Arvore AVL final ---");
arvore.percursoEmOrdem(arvore.raiz);
System.out.println("\nAltura total da Arvore AVL: " + arvore.obterAltura(arvore.raiz));
System.out.println("A Arvore AVL final está balanceada: " + arvore.verificarBalanceamento(arvore.raiz));
System.out.println("\n--- Exemplo de uma BST simples (não AVL) para comparação ---");
ArvoreBinariaBusca arvoreNaoAVL = new ArvoreBinariaBusca();
arvoreNaoAVL.raiz = arvoreNaoAVL.inserir(arvoreNaoAVL.raiz, 10);
arvoreNaoAVL.raiz = arvoreNaoAVL.inserir(arvoreNaoAVL.raiz, 20);
arvoreNaoAVL.raiz = arvoreNaoAVL.inserir(arvoreNaoAVL.raiz, 30);
arvoreNaoAVL.raiz = arvoreNaoAVL.inserir(arvoreNaoAVL.raiz, 40);
arvoreNaoAVL.raiz = arvoreNaoAVL.inserir(arvoreNaoAVL.raiz, 50);
System.out.println("Percurso em ordem da BST simples:");
arvoreNaoAVL.percursoEmOrdem(arvoreNaoAVL.raiz);
System.out.println("\nAltura da BST simples: " + arvoreNaoAVL.obterAltura(arvoreNaoAVL.raiz));
// Note que esta BST não possui mecanismos de balanceamento, resultando em uma altura maior.
}
}