Árvores pt III: Teoria, Introdução, Binárias e AVL.

Continuando a abordagem da estrutura de dados “Árvore” (já abordadas neste e neste post), vamos explorar desta vez as árvores AVL.

Ás árvores AVL, são árvores binarias, mas com um diferencial: Elas são balanceadas!

Mas o que vem a ser árvores balanceadas? São árvores que tendem a ter a mesma altura à direita e à esquerda! Formalmente, considerasse que uma árvore é balanceada quando, para cada nó, a altura da sub-árvore da esquerda não difere da altura da sub-árvore direita em mais de uma unidade.

Abaixo, um exemplos de árvores balanceadas e não balanceadas:

Quais as vantagens de uma árvore balanceada? Bem, quando a árvore está balanceada, podemos dar menos saltos para atingir o item procurado. No último exemplo da figura acima, para encontrar o item “B”, precisaríamos de 4 saltos, enquanto no penúltimo exemplo apenas 1 salto seria necessário.

Então pare e pense: As árvores de pesquisa são construídas de modo a tornar mais eficiente a tarefa de procura dos elementos, visando que o elemento deve ser procurado à esquerda (caso seja menor que o item atual), ou procurado à direita (caso seja maior do que o item atual), mas nunca em ambos os lados, nada melhor do que a árvore estar balanceada.

Mas por que AVL? Isto é porque os matemáticos russos Adelson-Velskii e Landis que fizeram a proposta deste modelo.

Várias são as estratégias de balanceamento, podemos balancear ao inserir um elemento, ao excluir um elemento, disparar um comando manualmente para balanceá-la etc.

Para determinar a necessidade do balanceamento, teremos de calcular o Fator de Balanceamento. Para uma árvore balanceada, o módulo deste fator não pode ser maior do que 1. Lembrando que cada vértice tem de ter seu Fator de Balanceamento calculado. Dizemos que:

• Se o Fator de Balanceamento for igual a –1: Sub-árvore da esquerda é mais alta.
• Se o Fator de Balanceamento for igual a 0: Os dois lados tem a mesma altura.
• Se o Fator de Balanceamento for igual a 1: Sub-árvore da direita é mais alta.
• O Fator de Balanceamento de uma folha é sempre 0!

… E como dito anteriormente, dentro destes limites, ainda não é necessário balancear a árvore.

Para calcular o Fator de Balanceamento (FB) de um vértice temos:

FB(vértice v) = altura(sub-árvore direita v) - altura(sub-árvore esquerda v)

Observe a árvore (balanceada) abaixo com os fatores calculados:

Se o fator extrapolar o intervalo (-1, 1) , significa que a árvore está desbalanceada! Então temos de dar início ao processo de balanceamento em árvores AVL.

Vamos pensar em um processo para a inserção.

• Inserimos um novo elemento na árvore.
• A inserção deste novo elemento pode ou não violar a propriedade de balanceamento.
• Se a inserção não violar a propriedade de balanceamento, podemos continuar inserindo novos elementos.
• Se a inserção violar temos de dar início nas Rotações da Árvore.

A Rotação da Árvore é um algoritmo que visa ajustar o balanceamento, trocando elementos de posição em “girando os elementos pelos seus lugares”. Pode ser usado para qualquer caso de balanceamento AVL. Temos quatro tipos de rotação: Rotação simples à esquerda, rotação simples à direita, Rotação dupla à esquerda, Rotação dupla à direita.

Rotação Simples

Observe a seguinte evolução da árvore, ao inserirmos o elemento “3” no exemplo a seguir:

Percebam que o elemento “2”, que inicialmente estava com FB (Fator de Balanceamento) igual a 0 no primeiro estágio, ganhou um FB de 1 por conta do elemento “3” inserido à direita. Calculando o FB do elemento “8”, temos que somar, em módulo, o FB de suas sub-árvores.

Aqui vai um macete, quando tivermos o sinal negativo a rotação (ao menos a primeira) deve ser à direita (pois ó sinal negativo indica maior peso/altura para a esquerda). Se o sinal for positivo, então a rotação deve ser efetuada para a esquerda.

Outro macete, quando os sinais dos FBs (pai e filho) são iguais (elemento “8” tem FB = –2 e o elemento “4” tem o FB = –1, ambos são negativos), a rotação é simples. Caso sejam diferente a rotação deverá ser dupla (seguindo o macete do sinal).

Então, o elemento “4”, que está à esquerda do elemento “8” sobe para a direita, só que isso faria com que ele tivesse três filhos (6, 8, 10), então passamos um filho, nesse caso o maior (da direita) para a sub-árvore do elemento “8”.

Rotação Dupla

Observe a evolução dos exemplos a seguir quando inserimos o elemento “5” na primeira árvore da imagem abaixo:

Percebam que o vértice “8” ficou com FB = –2, porém o sinal do seu filho esquerdo é positivo, sendo assim, o sinal é inverso, resultando em rotação dupla. Porém tenha calma.

Um terceiro macete: a rotação começa de baixo para cima! Nesse exemplo, o vértice desbalanceado é o “8”, como a rotação é dupla, vamos rotacionar primeiro o seu filho desbalanceado para a esquerda (jogando o elemento “4” para baixo).

Para concluir, bastaria rotacionar, na posição oporta (direita) o vértice “8”.

Para compreender: a rotação define qual lado o elemento com FB alterado deve prosseguir.

Observe a generalização dos processos abaixo:

Para tal, teremos dois vértices especiais:

• P – Vértice ancestral mais próximo do elemento inserido, cujo o FB fica fora do intervalo (-1, 1);
• Q – Filho de P na sub-árvore onde ocorreu a inserção.

Os triângulos representam as sub-árvores, eventualmente presentes na árvore.

Rotação simples à esquerda

Neste caso o vértice Q sobe para a posição anteriormente ocupada pelo vértice P. A sub-árvore com o elemento 2 (estava à esquerda de Q, portanto constituída de elementos menores), passa para a direita de P, cedendo assim o lugar à esquerda de Q, para que P possa ser seu filho.

Rotação simples à direita

Neste caso o vértice Q sobe para a posição anteriormente ocupada pelo vértice P. A sub-árvore com o elemento 2 (estava à direita de Q, portanto é constituída de elementos maiores), passa para a esquerda de P, cedendo assim o lugar à direita de Q, para que P possa ser seu filho.

Rotação dupla à esquerda

A rotação dupla à esquerda é constituída por duas rotações simples:

1. a primeira, à direita, em torno do nodo Q,
2. e a segunda, à esquerda, em torno do nodo P.

Rotação dupla à direita

A rotação dupla à direita é constituída por duas rotações simples:

1. a primeira, à esquerda, em torno do nodo Q,
2. e a segunda, à direita, em torno do nodo P.

Então fica mais esse macete: quando há rotação dupla, a rotação principal é a ultima que será executada, pois começamos “de baixo para cima”.

Revisão

• Se o FB do vértice P for positivo, a rotação deve ser feita para a esquerda, se for negativo, para direita.
• Se o FB do vértice P e o FB do vértice Q tiverem o mesmo sinal, a rotação deve ser simples, se tiverem sinais contrários, a rotação deve ser dupla.

Pseudo-código

    1. Insira o novo vértice normalmente ;

    2. Iniciando com o vértice pai do elemento recém-inserido, teste se a propriedade AVL
        é violada, ou seja, teste se o FB deste é maior do que abs(1).
        Temos aqui 2 possibilidades:

        2.1. A condição AVL foi violada

            2.1.1. Execute as operações de rotação conforme for o caso (Tipo 1 ou Tipo 2)

            2.1.2. Volte ao passo 1

        2.2. A condição AVL não foi violada.

            2.2.1. Se o vértice recém-testado não tem pai, ou seja, é a raiz da árvore,
            volte para inserir novo elemento (Passo 1)

E agora o código em C (documentado)

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
 
struct Item
{
    int numero;
    Item *esquerda;
    Item *direita;
};
 
 
Item** Procurar(Item **itemAtual, int valor)
{
    if(*itemAtual == NULL)
    {
        return NULL;
    }
    else if((*itemAtual)->numero == valor)
    {
        return itemAtual;
    }
    else if(valor < (*itemAtual)->numero)
    {
        return Procurar(&(*itemAtual)->esquerda, valor);
    }
    else
    {
        return Procurar(&(*itemAtual)->direita, valor);
    }
}
 
bool Remover(Item **itemAtual, int valor)
{
    Item **itemProcurado = Procurar(itemAtual, valor);
 
    if(itemProcurado == NULL)

    {
        printf("\nItem não encontrado!\n");
        return false;
    }
 
    Item *temp = *itemProcurado;
 
    if((*itemProcurado)->direita == NULL)
    {
        // -> Não tem filho a direita.
        (*itemProcurado) = (*itemProcurado)->esquerda;
    }
    else if((*itemProcurado)->esquerda == NULL)
    {
        // -> Não tem filho a esquerda.
        (*itemProcurado) = (*itemProcurado)->direita;
    }
    else
    {
        // -> Tem os dois filhos.
        Item *anterior = NULL;
       
        temp = (*itemProcurado)->esquerda;
 
        while (temp->direita != NULL)
        {
            anterior = temp;
            temp = temp->direita;
        }
 
        (*itemProcurado)->numero = temp->numero;
 
        if(anterior == NULL)
        {
            (*itemProcurado)->esquerda = temp->esquerda;
        }
        else
        {
            (*itemProcurado)->direita = temp->esquerda;
        }
    }
 
    free(temp);
    return true;
}
 
 
void ListarPreOrdem(Item *itemAtual)
{
    if (itemAtual != NULL)
    {
        printf("%i; ", itemAtual->numero);
        ListarPreOrdem(itemAtual->esquerda);
        ListarPreOrdem(itemAtual->direita);
    }
}
 
void ListarInOrdem(Item *itemAtual)
{
    if (itemAtual != NULL)
    {
        ListarInOrdem(itemAtual->esquerda);
        printf("%i; ", itemAtual->numero);
        ListarInOrdem(itemAtual->direita);
    }
}
 
void ListarPosOrdem(Item *itemAtual)
{
    if (itemAtual != NULL)
    {
        ListarPosOrdem(itemAtual->esquerda);
        ListarPosOrdem(itemAtual->direita);
        printf("%i; ", itemAtual->numero);
    }
}
 
 
void Listar(Item *itemAtual)
{
    printf( "Listando... \n\n");
    ListarPreOrdem(itemAtual);
    printf("\n\n");
}
 
 
int CalcularAltura(Item *itemAtual)
{
    int esquerda;
    int direita;
 
    if (itemAtual == NULL)
    {
        return 0;
    }
    else
    {
        esquerda = CalcularAltura(itemAtual->esquerda);
        direita = CalcularAltura(itemAtual->direita);
 
        if (esquerda > direita)
        {
            return esquerda + 1;
        }
        else
        {
           return direita + 1;
        }
    }
}
 
int CalcularFatorDeBalanceamento(Item *itemAtual)
{
    if (itemAtual == NULL)
    {
      return 0;
    }
    else
    {
        int fator = CalcularAltura(itemAtual->direita) - CalcularAltura(itemAtual->esquerda);
        return fator;
    }
}
 
 
void RotacionarParaEsquerda(Item **itemAtual)
{
    Item *temp;
   
    printf ("Rotacao para esquerda de %i\n", (*itemAtual)->numero);

    temp = *itemAtual;
    *itemAtual = (*itemAtual)->direita;
    temp->direita = (*itemAtual)->esquerda;
    (*itemAtual)->esquerda = temp;
}
 
void RotacionarParaDireita(Item **itemAtual)
{
    Item *temp;
 
    printf ("Rotacao para direita de %i\n", (*itemAtual)->numero);
 
    temp = *itemAtual;
    *itemAtual = (*itemAtual)->esquerda;
    temp->esquerda = (*itemAtual)->direita;
    (*itemAtual)->direita = temp;
}
 
 
bool InserirAVL(Item **itemAtual, int valor)
{
    // -> Se o nó for nulo então o item alocado é colocado nele.
    if(*itemAtual == NULL)
    {
        // -> Aloca memória para o novo item
        Item *novo = (Item *)malloc(sizeof(Item));
 
        // -> Checa se foi alocado memória corretamente.
        if (novo != NULL)
        {    
            // -> Define e inicializa os valores.
            novo->numero = valor;
            novo->esquerda = NULL;
            novo->direita = NULL;
        }
        else   
        {
            return false;
        }
 
        *itemAtual = novo;
    }
    else // -> Decisão: Esquerda ou Direita?
    {
        // -> valor menor que o atual vai para a esquerda.
        if(valor < (*itemAtual)->numero)
        {
            InserirAVL(&(*itemAtual)->esquerda, valor);

            // -> Após inserir, temos de verificar se há necessidade de balanceamento.
            // -> Como inserimos na esquerda, vamos balancear apenas a direita, pois a esquerda pode pesar.
            int fatorDeBalanceamentoItemAtual = CalcularFatorDeBalanceamento(*itemAtual);

            if(abs(fatorDeBalanceamentoItemAtual) > 1)
            {
                int fatorDeBalanceamentoItemEsquerda = CalcularFatorDeBalanceamento((*itemAtual)->esquerda);

                // -> Define se vai ocorrer rotação dupla
                if(fatorDeBalanceamentoItemAtual * fatorDeBalanceamentoItemEsquerda < 0)
                {
                    printf("rotacao dupla (%i, %i)\n", fatorDeBalanceamentoItemAtual, fatorDeBalanceamentoItemEsquerda);
                   
                    RotacionarParaEsquerda(&(*itemAtual)->esquerda);
                    RotacionarParaDireita(itemAtual);
                }
                else
                {
                    printf("rotacao simples (%i, %i)\n", fatorDeBalanceamentoItemAtual, fatorDeBalanceamentoItemEsquerda);
                   
                    RotacionarParaDireita(itemAtual);
                }
            }
           
        }
        else // -> valor maior que o atual vai para a direita.
        {
            InserirAVL(&(*itemAtual)->direita, valor);
 
            // -> Após inserir, temos de verificar se há necessidade de balanceamento.
            // -> Como inserimos na direita, vamos balancear apenas a esquerda, pois a direita pode pesar.
            int fatorDeBalanceamentoItemAtual = CalcularFatorDeBalanceamento(*itemAtual);

            if(abs(fatorDeBalanceamentoItemAtual) > 1)
            {
                int fatorDeBalanceamentoItemDireita = CalcularFatorDeBalanceamento((*itemAtual)->direita);

                // -> Define se vai ocorrer rotação dupla
                if(fatorDeBalanceamentoItemAtual * fatorDeBalanceamentoItemDireita < 0)
                {
                    printf("rotacao dupla (%i, %i)\n", fatorDeBalanceamentoItemAtual, fatorDeBalanceamentoItemDireita);
                    RotacionarParaDireita(&(*itemAtual)->direita);

                    RotacionarParaEsquerda(itemAtual);
                }
                else
                {
                    printf("rotacao simples (%i, %i)\n", fatorDeBalanceamentoItemAtual, fatorDeBalanceamentoItemDireita);

                    RotacionarParaEsquerda(itemAtual);
                }
            }
        }
    }
    return true;
} 
 
 
void Menu()

{
    printf( "Digite a sua escolha: \n"
        "    1 para inserir um elemento na arvore \n"
        "    2 para remover um elemento da arvore \n"
        "    3 para finalizar \n"
        "? ");
}
 
void main()
{   
    Item *raiz = NULL;

    int opcao;
    int numero;
 
    Menu();
    scanf("%i", &opcao);
 
    while (opcao != 3)
    {
        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);
                InserirAVL(&raiz, numero);
                Listar(raiz);
                break;

            case 2:
                printf( " Digite o numero a ser removido: ");
                scanf( "\n%i", &numero);
                Remover(&raiz, numero);
                Listar(raiz);
                break;
 
            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }
 
        scanf("%i", &opcao);   
    }
    printf("Fim do programa.\n");
}

Resultado do código, listando em pré-ordem:

Bem, após todos estes ensinamentos, dicas e macetes, me resta deixar algumas tarefas:

1. Implementar o balanceamento na exclusão.
2. Retirar o balanceamento automático (quando um elemento é inserido e/ou excluido) e implementar o balanceamento via comando.
3. Após concluído os exercícios anteriores, implementá-los em uma árvore de alunos, se baseando no RA do aluno como indice para a árvore.
4. Após concluído os exercícios anteriores, implementá-los em uma árvore de alunos, se baseando no Nome do aluno como indice para a árvore.

Espero que tenham, gostado boa sorte!!!