Arvore_de_Pesquisa_AVL

#include <stdio.h>
#include <stdlib.h>

typedef long TipoChave;

typedef struct Regist {
    TipoChave Chave;
} Registro;

struct No {
    Registro Reg;
    struct No *pEsq, *pDir;
};

//-----------------------Funções

void Pesquisa(Registro *x, struct No *p);

void Inicializa(struct No *Dicionario);

void Insere(Registro x, struct No **p);

void Antecessor(struct No *q, struct No **r);

void Retira(Registro x, struct No **p);

int FB (struct No *pRaiz);

int Altura(struct No *pRaiz);

void RotacaoSimplesEsquerda(struct No **ppRaiz);

void RotacaoSimplesDireita(struct No **ppRaiz);

int BalancaEsquerda(struct No **ppRaiz);

int BalancaDireita(struct No **ppRaiz);

int Balanceamento(struct No **ppRaiz);

int Inserir(struct No **ppRaiz, Registro x);

int EhArvoreAVL(struct No *pRaiz);

//-----------------------Main

int main()
{
    struct No *arvore, *resgate=malloc(sizeof(struct No));
    Inicializa(arvore);
    int confere;
    Registro dado;

    Leia: printf("Digite: ");
    scanf("%li", &dado.Chave);
    Insere(dado,&arvore);
    printf("Feito!\n");
    printf("Inserir outro número? ");
    scanf("%d", &confere);
    if (confere == 1)
        goto Leia;

    Pesquise: printf("Digite: ");
    scanf("%li", &resgate->Reg.Chave);
    Pesquisa(&resgate->Reg,arvore);
    printf("Feito!\n");
    printf("Pesquisar por outro? ");
    scanf("%d", &confere);
    if (confere == 1)
        goto Pesquise;

    Remova: printf("Digite: ");
    scanf("%li", &resgate->Reg.Chave);
    Retira(resgate->Reg,&arvore);
    printf("Feito!\n");
    printf("Remover outro? ");
    scanf("%d", &confere);
    if (confere == 1)
        goto Remova;

    return 0;
}

//-----------------------Métodos

void Pesquisa(Registro *x, struct No *p)
{
    if (p == NULL)
    {
        printf("Erro : Registro nao esta presente na arvore\n");
        return;
    }
    if (x->Chave < p->Reg.Chave)
    {
        Pesquisa(x, p->pEsq);
        return;
    }
    if (x->Chave > p->Reg.Chave)
        Pesquisa(x, p->pDir);
    else
        *x = p->Reg;
}

void Inicializa(struct No *Dicionario)
{
    Dicionario = NULL;
}

void Insere(Registro x, struct No **p)
{
    if ((*p) == NULL)
    {
        (*p) = (struct No*)malloc(sizeof(struct No));
        (*p)->Reg = x;
        (*p)->pEsq = NULL;
        (*p)->pDir = NULL;
        return;
    }
    if (x.Chave < (*p)->Reg.Chave)
    {
        Insere(x, &(*p)->pEsq);
        return;
    }
    if (x.Chave > (*p)->Reg.Chave)
        Insere(x, &(*p)->pDir);
    else
        printf("Erro : Registro ja existe na arvore\n");
}


void Retira(Registro x, struct No **p)
{
    if ((*p) == NULL)
    {
        printf("Erro : Registro nao esta na arvore\n");
        return;
    }
    if (x.Chave < (*p)->Reg.Chave)
    {
        Retira(x, &(*p)->pEsq);
        return;
    }
    if (x.Chave > (*p)->Reg.Chave)
    {
        Retira(x, &(*p)->pDir);
        return;
    }
    if ((*p)->pDir == NULL)
    {
        struct No *Aux;
        Aux = (*p);
        (*p) = (*p)->pEsq;
        free(Aux);
        return;
    }
    if ((*p)->pEsq != NULL)
    {
        Antecessor((*p), &(*p)->pEsq);
        return;
    }
    // ((*p)->pEsq == NULL)
    struct No *Aux;
    Aux = (*p);
    (*p) = (*p)->pDir;
    free(Aux);
}

void Antecessor(struct No *q, struct No **r)
{
    struct No *aux;
    if ((*r)->pDir != NULL)
    {
        Antecessor(q, &(*r)->pDir);
        return;
    }
    q->Reg = (*r)->Reg;
    aux = (*r);
    (*r) = (*r)->pEsq;
    free(aux);
}

int FB (struct No *pRaiz)
{
    if (pRaiz == NULL)
        return 0;

    return Altura(pRaiz->pEsq) - Altura(pRaiz->pDir);
}

int Altura(struct No *pRaiz)
{
    int iEsq,iDir;
    if (pRaiz == NULL)
        return 0;
    iEsq = Altura(pRaiz->pEsq);
    iDir = Altura(pRaiz->pDir);
    if ( iEsq > iDir )
        return iEsq + 1;
    else
        return iDir + 1;
}

void RotacaoSimplesEsquerda(struct No **ppRaiz)
{
    struct No *pAux;
    pAux = (*ppRaiz)->pDir;
    (*ppRaiz)->pDir = pAux->pEsq;
    pAux->pEsq = (*ppRaiz);
    (*ppRaiz) = pAux;
}

void RotacaoSimplesDireita(struct No **ppRaiz)
{
    struct No *pAux;
    pAux = (*ppRaiz)->pEsq;
    (*ppRaiz)->pEsq = pAux->pDir;
    pAux->pDir = (*ppRaiz);
    (*ppRaiz) = pAux;
}

int BalancaEsquerda(struct No **ppRaiz)
{
    int fbe = FB ((*ppRaiz)->pEsq);
    if (fbe > 0)
    {
        RotacaoSimplesDireita(ppRaiz);
        return 1;
    }
    else if (fbe < 0)
    { //Rotação Dupla Direita
        RotacaoSimplesEsquerda(&((*ppRaiz)->pEsq));
        RotacaoSimplesDireita(ppRaiz); // &(*ppRaiz)
        return 1;
    }
    return 0;
}

int BalancaDireita(struct No **ppRaiz)
{
    int fbd = FB((*ppRaiz)->pDir);
    if (fbd < 0)
    {
        RotacaoSimplesEsquerda(ppRaiz);
        return 1;
    }
    else if (fbd > 0 )
    { // Rotação Dupla Esquerda
        RotacaoSimplesDireita(&((*ppRaiz)->pDir));
        RotacaoSimplesEsquerda(ppRaiz); // &(*ppRaiz)
        return 1;
    }
    return 0;
}

int Balanceamento(struct No **ppRaiz)
{
    int fb = FB(*ppRaiz);
    if ( fb > 1)
        return BalancaEsquerda(ppRaiz);
    else if (fb < -1 )
        return BalancaDireita(ppRaiz);
    else
        return 0;
}

int Inserir(struct No **ppRaiz, Registro x)
{
    if (*ppRaiz == NULL)
    {
        *ppRaiz = (struct No*)malloc(sizeof(struct No));
        (*ppRaiz)->Reg = x;
        (*ppRaiz)->pEsq = NULL;
        (*ppRaiz)->pDir = NULL;
        return 1;
    }
    if ((*ppRaiz)->Reg.Chave > x.Chave)
    {
        if (Inserir(&(*ppRaiz)->pEsq,x))
        {
            if (Balanceamento(ppRaiz))
                return 0;
            else
                return 1;
        }
    }
    if ((*ppRaiz)->Reg.Chave < x.Chave)
    {
        if (Inserir(&(*ppRaiz)->pDir,x))
        {
            if (Balanceamento(ppRaiz))
                return 0;
            else
                return 1;
        }
        else
            return 0;
    }
    else
        return 0; // valor ja presente
}

int EhArvoreAVL(struct No *pRaiz)
{
    int fb;
    if (pRaiz == NULL)
        return 1;
    if (!EhArvoreAVL(pRaiz->pEsq))
        return 0;
    if (!EhArvoreAVL(pRaiz->pDir))
        return 0;
    fb = FB (pRaiz);
    if ((fb > 1) || (fb < -1))
        return 0;
    else
        return 1;
}