Dando continuidade ao estudo das árvores balanceadas, nesta aula vamos aprender como remover um nó em uma árvore binária de busca balanceada – Árvore AVL.

Esta função é bastante similar à função de inserção em três aspectos.

Primeiro, o processo de remoção é exatamente igual à remoção em uma árvore binária não balanceada. Removemos nós folhas e nós com um filho. Os nós com dois filhos são trocados de posição com um de seus descendentes. Assim, ele se torna um nó folha ou com no máximo um filho.

Em segundo, o processo de remoção pode alterar a altura de uma árvore. Então, após cada remoção, precisamos calcular novamente a altura de cada nó do caminho da raiz até o nó que foi removido. Isso é feito ao final da função, após o processo de remoção.

Por fim, uma remoção também pode desbalancear a árvore. Assim, após recalcular a altura do nó, chamamos a função balancear desenvolvida na aula anterior para calcular o fator de balanceamento e verificar a necessidade de alguma rotação.

/*
    Função para remover um nó da Árvore binária balanceada
    Pode ser necessário rebalancear a árvore e a raiz pode ser alterada
    por isso precisamos retornar a raiz
*/
No* remover(No *raiz, int chave) {
    if(raiz == NULL){
        printf("Valor nao encontrado!\n");
        return NULL;
    } else { // procura o nó a remover
        if(raiz->valor == chave) {
            // remove nós folhas (nós sem filhos)
            if(raiz->esquerdo == NULL && raiz->direito == NULL) {
                free(raiz);
                printf("Elemento folha removido: %d !\n", chave);
                return NULL;
            }
            else{
                // remover nós que possuem 2 filhos
                if(raiz->esquerdo != NULL && raiz->direito != NULL){
                    No *aux = raiz->esquerdo;
                    while(aux->direito != NULL)
                        aux = aux->direito;
                    raiz->valor = aux->valor;
                    aux->valor = chave;
                    printf("Elemento trocado: %d !\n", chave);
                    raiz->esquerdo = remover(raiz->esquerdo, chave);
                    return raiz;
                }
                else{
                    // remover nós que possuem apenas 1 filho
                    No *aux;
                    if(raiz->esquerdo != NULL)
                        aux = raiz->esquerdo;
                    else
                        aux = raiz->direito;
                    free(raiz);
                    printf("Elemento com 1 filho removido: %d !\n", chave);
                    return aux;
                }
            }
        } else {
            if(chave < raiz->valor)
                raiz->esquerdo = remover(raiz->esquerdo, chave);
            else
                raiz->direito = remover(raiz->direito, chave);
        }

        // 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;
    }
}