Arvore_RedBlack

#include <stdio.h>
#include <stdlib.h>
#include <bool.h>
#define vermelho 0
#define preto 1

typedef long TipoChave;

typedef struct Regist {
    TipoChave Chave;
} Registro;

struct No {
    Registro Reg;
    short int cor;
    struct No *pEsq, *pDir, *pPai, *pTio;
};

/**
 * ----------------------Regras para manipular uma árvore rubro-negra
 *
 * Caso 1- Nó inserido é a raiz
 * Solução: Cor recebe preto
 *
 * Caso 2- Tio do nó inserido é vermelho
 * Solução: Inverte a cor do pai, do tio e do avô
 *
 * Caso 3a- Tio do nó inserido é preto e o nó inserido e seu tio são os filhos da direita de seus respectivos pais
 * Solução: Rotação Simples para Direita no pai do nó inserido
 *
 * Caso 3b- Tio do nó inserido é preto e o nó inserido e seu tio são os filhos da esquerda de seus respectivos pais
 * Solução: Rotação Simples para Esquerda no pai do nó inserido
 *
 * Caso 4a- Tio do nó inserido é preto e o nó inserido é filho da direita e seu tio é filho da esquerda
 * Solução: Rotação Simples para Esquerda no avô do nó inserido e inverte a cor do pai e do avô
 *
 * Caso 4b- Tio do nó inserido é preto e o nó inserido é filho da esquerda e seu tio é filho da direita
 * Solução: Rotação Simples para Direita no avô do nó inserido e inverte a cor do pai e do avô
 *
 */

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

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

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

void Corrige(struct No **p);

bool EhArvoreRB(struct No *p);

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

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

void RotacaoSimplesEsquerda(struct No **ppRaiz);

void RotacaoSimplesDireita(struct No **ppRaiz);

int BalancaEsquerda(struct No **ppRaiz);

int BalancaDireita(struct No **ppRaiz);

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

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

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

    Leia: printf("Digite: ");
    scanf("%li", &dado.Chave);
    Insere(dado,&arvore,NULL);
    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 Insere(Registro x, struct No **p, struct No *Pai)
{
    if ((*p) == NULL)
    {
        (*p) = (struct No*)malloc(sizeof(struct No));
        (*p)->Reg = x;
        (*p)->pEsq = NULL;
        (*p)->pDir = NULL;
        (*p)->pPai = Pai;
        (*p)->pTio=NULL;
        if ((*p)->pPai != NULL && (*p)->pPai->pPai != NULL)
        {
            (*p)->cor=vermelho;
            if ((*p)->pPai->pPai->pDir == (*p)->pPai)
            {//Se o nodo que esta sendo inserido e o filho do pai da direita, o tio sera o da esquerda
                (*p)->pTio=(*p)->pPai->pPai->pEsq;
            }
            else
            {
                (*p)->pTio=(*p)->pPai->pPai->pDir;
            }
        }
        else
        {//Corrigindo Caso 1
            (*p)->cor=preto;
        }
        return;
    }
    if (x.Chave < (*p)->Reg.Chave)
    {
        Insere(x, &(*p)->pEsq, *p);
        return;
    }
    if (x.Chave > (*p)->Reg.Chave)
        Insere(x, &(*p)->pDir, *p);
    else
        printf("Erro : Registro ja existe na arvore\n");
}

void Corrige(struct No **p)
{

}

bool EhArvoreRB(struct No *p)
{
    if (p == NULL)
        return false;   //Nao precisa corrigir nada
    if (p->pPai != NULL && p.cor == preto && p->pPai.cor == vermelho)
        return true;    //Precisa corrigir
    return EhArvoreRB(p->pEsq) || EhArvoreRB(p->pDir);
}

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

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