Nesta aula vamos iniciar o desenvolvimento da nossa Árvore Binária de Busca Balanceada – Árvore AVL. Vamos desenvolver algumas funções necessárias para as rotações, como o cálculo da altura de um nó e o fator de balanceamento de cada nó.

A boa notícia é que todo o código já desenvolvido para a Árvore Binária de Busca pode ser reaproveitado, fazendo algumas pequenas alterações nas funções de inserção, remoção e acrescentando algumas outras funções auxiliares.

Vamos iniciar pela estrutura nó. Cada nó precisa possuir um novo campo para armazenar sua altura na árvore. É por meio desta altura que iremos calcular o fator de balanceamento. A seguir é apresentado o código atualizado para nossa Árvore AVL. Aqui no exemplo estou utilizando uma variável do tipo short apenas para economizar memória. Fique a vontade para trocar para o tipo int caso queira.

/*
       Nó para a Árvore AVL
*/
 typedef struct no{
     int valor;
     struct no *esquerdo, *direito;
     short altura;
 }No;

Também vou desenvolver uma função para criar um novo nó. Assim, ao inserir não precisamos mais criar um novo nó dentro da função de inserção, bastando chamar esta função.

/*
    Função que cria um novo nó
    x -> valor a ser inserido no nó
    Retorna: o endereço do nó criado
*/
No* novoNo(int x){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->valor = x;
        novo->esquerdo = NULL;
        novo->direito = NULL;
        novo->altura = 0;
    }
    else
        printf("\nERRO ao alocar nó em novoNo!\n");
    return novo;
}

Para descobrir a altura de um determinado nó precisamos descobrir qual subárvore tem a maior altura. Assim, irei também desenvolver uma função que recebe duas alturas e retorna a maior. Para isso foi utilizado o operador ternário. Esta função será utilizada nas rotações para recalcular a altura dos nós movimentados.

/*
    Retorna o maior dentre dois valores
    a, b -> altura de dois nós da árvore
*/
short maior(short a, short b){
    return (a > b)? a: b;
}

Também desenvolveremos uma função para retornar a altura de um determinado nó. Se o nó for nulo o retorno será -1. Esta função será utilizada para calcular o fator de balanceamento de um nó.

/*
      Retorna a altura de um nó ou -1 caso ele seja null
*/
short alturaDoNo(No *no){
    if(no == NULL)
        return -1;
    else
        return no->altura;
}

Agora vamos implementar uma função de suma importância para uma árvore balanceada, a função que calcula o fator de balanceamento de um nó. Observe que nesta função já fazemos uso da função anterior, uma vez que o fator de balanceamento de um nó é a altura da subárvore esquerda menos a altura da subárvore direita.

/*
      Calcula e retorna o fator de balanceamento de um nó
*/
short fatorDeBalanceamento(No *no){
    if(no)
        return (alturaDoNo(no->esquerdo) - alturaDoNo(no->direito));
    else
        return 0;
}

Na aula seguinte iniciaremos o desenvolvimento das rotações.