Nesta aula vamos aprender como fazer uma inserção em uma Árvore Binária de Busca Balanceada, uma Árvore AVL.

Se você está acompanhando o curso desde o início você vai perceber que a inserção é exatamente igual a inserção em uma árvore binárias de busca sem balanceamento com algumas poucas alterações.

A primeira alteração é que agora não irei criar um novo nó dentro da função de inserção. Quando encontrarmos o ponto de inserção, vamos chamar a função novoNo apresentada nas aulas anteriores. Esta função irá criar um novo nó, preencher seus campos e retornar seu endereço.

No final da função, após o processo de inserção, precisamos agora realizar duas novas ações. Como acabamos de inserir um novo nó na árvore, precisamos checar a altura e o fator de balanceamento dos nós no caminho percorrido até a inserção.

A altura é simples. Basta recalcular a altura de cada nó entre a raiz e o novo nó inserido.

O fator de balanceamento é um pouco mais complicado e, apesar de poder ser feito dentro da função inserir, é altamente recomendado fazer uma função a parte uma vez que a mesma ação será necessária também na função de remoção. Assim, faremos uma nova função chamada balancear que será chamada para cada nó entre a raiz e o novo nó inserido.

/*
    Insere um novo nó na árvore
    raiz -> raiz da árvore
    x -> valor a ser inserido
    Retorno: endereço do novo nó ou nova raiz após o balanceamento
*/
No* inserir(No *raiz, int x){
    if(raiz == NULL) // árvore vazia
        return novoNo(x);
    else{ // inserção será à esquerda ou à direita
        if(x < raiz->valor)
            raiz->esquerdo = inserir(raiz->esquerdo, x);
        else if(x > raiz->valor)
            raiz->direito = inserir(raiz->direito, x);
        else
            printf("\nInsercao nao realizada!\nO elemento %d a existe!\n", x);
    }

    // Recalcula a altura de todos os nós entre a raiz e o novo nó inserido
    raiz->altura = maior(alturaDoNo(raiz->esquerdo), alturaDoNo(raiz->direito)) + 1;

    // verifica a necessidade de rebalancear a árvore
    raiz = balancear(raiz);

    return raiz;
}

A função balancear irá calcular o fator de balanceamento para o nó recebido e realizar a rotação adequada quando necessário. Observe que a rotação a ser realizada é encontrada por meio do fator de balanceamento. Se o fb for negativo já sabemos que a árvore está desbalanceada à direita. Então precisamos descobrir se é um caso clássico, pendendo completamente para à direita ou se é direita-esquerda. Para isso basta verificar também o fb da subárvore direita.

Com o fator de balanceamento podemos montar a seguinte tabela.

/*
    Função para realizar o balanceamento da árvore após uma inserção ou remoção
    Recebe o nó que está desbalanceado e retorna a nova raiz após o balanceamento
*/
No* balancear(No *raiz){
    short fb = fatorDeBalanceamento(raiz);

    // Rotação à esquerda
    if(fb < -1 && fatorDeBalanceamento(raiz->direito) <= 0)
        raiz = rotacaoEsquerda(raiz);

    // Rotação à direita
    else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) >= 0)
        raiz = rotacaoDireita(raiz);

    // Rotação dupla à esquerda
    else if(fb > 1 && fatorDeBalanceamento(raiz->esquerdo) < 0)
        raiz = rotacaoEsquerdaDireita(raiz);

    // Rotação dupla à direita
    else if(fb < -1 && fatorDeBalanceamento(raiz->direito) > 0)
        raiz = rotacaoDireitaEsquerda(raiz);

    return raiz;
}