Árvores AVL

#include <stdio.h>
#include <stdlib.h>
 
// Estrutura do nó da árvore AVL
typedef struct No {
    int chave;
    struct No* esquerda;
    struct No* direita;
    int altura;
} No;
 
// Função para obter a altura de um nó
int obterAltura(No* no) {
    if (no == NULL)
        return 0;
    return no->altura;
}
 
// Função para calcular o máximo entre dois valores
int maximo(int a, int b) {
    return (a > b) ? a : b;
}
 
// Função para criar um novo nó
No* criarNo(int chave) {
    No* no = (No*)malloc(sizeof(No));
    no->chave = chave;
    no->esquerda = NULL;
    no->direita = NULL;
    no->altura = 1; // Novo nó é inicialmente inserido na folha
    return no;
}
 
// Função para calcular o fator de balanceamento de um nó
int obterFatorBalanceamento(No* no) {
    if (no == NULL)
        return 0;
    return obterAltura(no->esquerda) - obterAltura(no->direita);
}
 
// Rotação à direita
No* rotacaoDireita(No* y) {
    No* x = y->esquerda;
    No* T2 = x->direita;
 
    // Realizar rotação
    x->direita = y;
    y->esquerda = T2;
 
    // Atualizar alturas
    y->altura = maximo(obterAltura(y->esquerda), obterAltura(y->direita)) + 1;
    x->altura = maximo(obterAltura(x->esquerda), obterAltura(x->direita)) + 1;
 
    // Retornar nova raiz
    return x;
}
 
// Rotação à esquerda
No* rotacaoEsquerda(No* x) {
    No* y = x->direita;
    No* T2 = y->esquerda;
 
    // Realizar rotação
    y->esquerda = x;
    x->direita = T2;
 
    // Atualizar alturas
    x->altura = maximo(obterAltura(x->esquerda), obterAltura(x->direita)) + 1;
    y->altura = maximo(obterAltura(y->esquerda), obterAltura(y->direita)) + 1;
 
    // Retornar nova raiz
    return y;
}
 
// Função para inserir um nó na árvore AVL
No* inserir(No* no, int chave) {
    // 1. Realizar inserção normal de BST
    if (no == NULL)
        return criarNo(chave);
 
    if (chave < no->chave)
        no->esquerda = inserir(no->esquerda, chave);
    else if (chave > no->chave)
        no->direita = inserir(no->direita, chave);
    else // Chaves iguais não são permitidas
        return no;
 
    // 2. Atualizar altura do nó ancestral
    no->altura = 1 + maximo(obterAltura(no->esquerda), obterAltura(no->direita));
 
    // 3. Obter o fator de balanceamento deste nó ancestral
    int balanceamento = obterFatorBalanceamento(no);
 
    // Se este nó ficou desbalanceado, então temos 4 casos:
 
    // Caso Esquerda Esquerda
    if (balanceamento > 1 && chave < no->esquerda->chave)
        return rotacaoDireita(no);
 
    // Caso Direita Direita
    if (balanceamento < -1 && chave > no->direita->chave)
        return rotacaoEsquerda(no);
 
    // Caso Esquerda Direita
    if (balanceamento > 1 && chave > no->esquerda->chave) {
        no->esquerda = rotacaoEsquerda(no->esquerda);
        return rotacaoDireita(no);
    }
 
    // Caso Direita Esquerda
    if (balanceamento < -1 && chave < no->direita->chave) {
        no->direita = rotacaoDireita(no->direita);
        return rotacaoEsquerda(no);
    }
 
    // Retornar o nó (inalterado)
    return no;
}
 
// Função para encontrar o nó com valor mínimo
No* encontrarMinimo(No* no) {
    No* atual = no;
    while (atual->esquerda != NULL)
        atual = atual->esquerda;
    return atual;
}
 
// Função para remover um nó da árvore AVL
No* remover(No* raiz, int chave) {
    // 1. Realizar remoção normal de BST
    if (raiz == NULL)
        return raiz;
 
    if (chave < raiz->chave)
        raiz->esquerda = remover(raiz->esquerda, chave);
    else if (chave > raiz->chave)
        raiz->direita = remover(raiz->direita, chave);
    else {
        // Este é o nó a ser removido
        if (raiz->esquerda == NULL) {
            // Nó sem filho esquerdo ou folha
            No* temp = raiz->direita;
            free(raiz);
            return temp;
        }
        else if (raiz->direita == NULL) {
            // Nó sem filho direito
            No* temp = raiz->esquerda;
            free(raiz);
            return temp;
        }
        else {
            // Nó com dois filhos: obter o sucessor inorder
            No* temp = encontrarMinimo(raiz->direita);
 
            // Copiar a chave do sucessor inorder para este nó
            raiz->chave = temp->chave;
 
            // Remover o sucessor inorder
            raiz->direita = remover(raiz->direita, temp->chave);
        }
    }
 
    // Se a árvore tinha apenas um nó, então retornar
    if (raiz == NULL)
        return raiz;
 
    // 2. Atualizar altura do nó atual
    raiz->altura = 1 + maximo(obterAltura(raiz->esquerda), obterAltura(raiz->direita));
 
    // 3. Obter o fator de balanceamento deste nó
    int balanceamento = obterFatorBalanceamento(raiz);
 
    // Se este nó ficou desbalanceado, então temos 4 casos:
 
    // Caso Esquerda Esquerda
    if (balanceamento > 1 && obterFatorBalanceamento(raiz->esquerda) >= 0)
        return rotacaoDireita(raiz);
 
    // Caso Esquerda Direita
    if (balanceamento > 1 && obterFatorBalanceamento(raiz->esquerda) < 0) {
        raiz->esquerda = rotacaoEsquerda(raiz->esquerda);
        return rotacaoDireita(raiz);
    }
 
    // Caso Direita Direita
    if (balanceamento < -1 && obterFatorBalanceamento(raiz->direita) <= 0)
        return rotacaoEsquerda(raiz);
 
    // Caso Direita Esquerda
    if (balanceamento < -1 && obterFatorBalanceamento(raiz->direita) > 0) {
        raiz->direita = rotacaoDireita(raiz->direita);
        return rotacaoEsquerda(raiz);
    }
 
    return raiz;
}
 
// Função para imprimir a árvore em ordem
void imprimirEmOrdem(No* raiz) {
    if (raiz != NULL) {
        imprimirEmOrdem(raiz->esquerda);
        printf("%d ", raiz->chave);
        imprimirEmOrdem(raiz->direita);
    }
}
 
// Função para buscar um valor na árvore
No* buscar(No* raiz, int chave) {
    if (raiz == NULL || raiz->chave == chave)
        return raiz;
 
    if (chave < raiz->chave)
        return buscar(raiz->esquerda, chave);
 
    return buscar(raiz->direita, chave);
}
 
// Função para imprimir informações detalhadas de um nó
void imprimirDetalhesNo(No* no) {
    if (no != NULL) {
        printf("Nó: %d, Altura: %d, Fator de Balanceamento: %d\n", 
               no->chave, no->altura, obterFatorBalanceamento(no));
    }
}
 
// Função para liberar toda a árvore
void liberarArvore(No* raiz) {
    if (raiz != NULL) {
        liberarArvore(raiz->esquerda);
        liberarArvore(raiz->direita);
        free(raiz);
    }
}
 
// Função para imprimir a árvore de forma visual (pré-ordem com indentação)
void imprimirArvoreVisual(No* raiz, int nivel) {
    if (raiz != NULL) {
        for (int i = 0; i < nivel; i++) {
            printf("  ");
        }
        printf("%d (h:%d, fb:%d)\n", raiz->chave, raiz->altura, obterFatorBalanceamento(raiz));
        
        if (raiz->esquerda != NULL || raiz->direita != NULL) {
            imprimirArvoreVisual(raiz->esquerda, nivel + 1);
            imprimirArvoreVisual(raiz->direita, nivel + 1);
        }
    }
}

// Função principal
int main() {
    No* raiz = NULL;
 
    printf("=== Demonstração da Árvore AVL ===\n\n");
 
    // Inserindo elementos
    printf("Inserindo elementos: 10, 20, 30, 40, 50, 25\n");
    raiz = inserir(raiz, 10);
    raiz = inserir(raiz, 20);
    raiz = inserir(raiz, 30);
    raiz = inserir(raiz, 40);
    raiz = inserir(raiz, 50);
    raiz = inserir(raiz, 25);
 
    printf("Árvore AVL em ordem: ");
    imprimirEmOrdem(raiz);
    printf("\n\n");
 
    // Visualização da estrutura da árvore
    printf("Estrutura da árvore (h=altura, fb=fator de balanceamento):\n");
    imprimirArvoreVisual(raiz, 0);
    printf("\n");
 
    // Mostrando detalhes da raiz
    printf("Detalhes da raiz:\n");
    imprimirDetalhesNo(raiz);
    printf("\n");
 
    // Buscando um elemento
    printf("Buscando o elemento 30: ");
    No* resultado = buscar(raiz, 30);
    if (resultado != NULL)
        printf("Encontrado!\n");
    else
        printf("Não encontrado!\n");
 
    // Removendo um elemento
    printf("\nRemoção do elemento 10:\n");
    raiz = remover(raiz, 10);
    printf("Árvore AVL em ordem após remoção: ");
    imprimirEmOrdem(raiz);
    printf("\n\n");
 
    printf("Estrutura da árvore após remoção:\n");
    imprimirArvoreVisual(raiz, 0);
    printf("\n");
 
    printf("Detalhes da nova raiz:\n");
    imprimirDetalhesNo(raiz);
    
    // Teste adicional: removendo mais elementos
    printf("\n=== Teste adicional de remoção ===\n");
    printf("Removendo elemento 30:\n");
    raiz = remover(raiz, 30);
    printf("Árvore após remoção do 30: ");
    imprimirEmOrdem(raiz);
    printf("\n");
    
    printf("Estrutura final:\n");
    imprimirArvoreVisual(raiz, 0);
    
    // Liberar memória
    liberarArvore(raiz);
    printf("\nMemória liberada com sucesso!\n");
 
    return 0;
}