Tree

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


//Criação da estrutura de um nó da arvore
struct No{
    int num; //Número armazenado
    int fb;  //Fator de balanceamento
    struct No* L; //Filho à esquerda
    struct No* R; //Filho à direita
};
typedef struct No No;


/* 
    UTILIZANDO PONTEIRO DUPLO   
    
    **pRaiz == ARVORE
      pRaiz->num == Resulta em ERRO pois a ARVORE em si não possui um número, apenas os nós

    Para acessar os atributos é preciso referenciar o NÓ e não a ARVORE
    *pRaiz = Nó
    (*pRaiz)->num == Correto para acessar um atributo de um nó
    
*/

/* Define o primeiro NÓ da ARVORE como nulo */
void criarArvore(No **pRaiz){
    *pRaiz = NULL; 
}

/*Mostra os números recursivamente*/
void showRED(No **pRaiz){
    if((*pRaiz) != NULL){
        printf("%d - ",(*pRaiz)->num); /*R*/
        showRED(&(*pRaiz)->L); /*E*/
        showRED(&(*pRaiz)->R); /*D*/
    }
}
void showERD(No **pRaiz){
    if((*pRaiz) != NULL){
        showERD(&(*pRaiz)->L);
        printf("%d(%d) - ",(*pRaiz)->num,(*pRaiz)->fb);
        showERD(&(*pRaiz)->R);
    }
}
void showEDR(No **pRaiz){
    if((*pRaiz) != NULL){
        showEDR(&(*pRaiz)->L);
        showEDR(&(*pRaiz)->R);
        printf("%d - ",(*pRaiz)->num);
    }
}

/*Busca o nó que possui o número 'n' salvo*/
No* buscar(No **pRaiz,int n){
    //Se o nó tem o número retorna ele
    if((*pRaiz)->num == n) return (*pRaiz);
    //Se o número desse nó é maior que 'n', procura 'n' a esquerda
    if((*pRaiz)->num > n) return buscar(&(*pRaiz)->L,n);
    //Caso contrário procura 'n' a direita
    else return buscar(&(*pRaiz)->R,n);
}

/*Retorna o pai do nó que possui o número 'n' salvo*/
No* buscarPai(No **pRaiz,int n){
    No* pai = NULL;
    
    //Se o nó atual possir o número retorna ele (caso o número procurado seja a raiz principal da arvore)
    if((*pRaiz)->num == n) return (*pRaiz);
    
    //Verifica se existe filho à direita
    if((*pRaiz)->R){
        //Verifica se o filho a direita possui o número, se sim retorna este nó
        if((*pRaiz)->R->num == n) return (*pRaiz);
        //Senão passa para o filho à direita
        else pai = buscarPai(&(*pRaiz)->R,n);
    }
    
    //Verifica se existe filho à esquerda e o pai ainda não foi encontrado
    if((*pRaiz)->L && !pai){
        //Verifica se o filho a esquerda possui o número, se sim retorna este nó
        if((*pRaiz)->L->num == n) return (*pRaiz);
        //Senão passa para o filho à esquerda
        else pai = buscarPai(&(*pRaiz)->L,n);
    }
    
    return pai;
}

/*Insere novo valor na àrvore*/
void inserir(No **pRaiz,int n){
    //Caso o nó não exista aloca espaço, insere o número e define filhos como NULL
    if(*pRaiz == NULL){
        *pRaiz = (No*) malloc(sizeof(No));
        (*pRaiz)->R = NULL;
        (*pRaiz)->L = NULL;
        (*pRaiz)->num = n;
    }else{
        //Caso o número seja maior que o número do nó insere à direita
        if(n > (*pRaiz)->num)
            inserir(&(*pRaiz)->R,n);
        //Senão insere à esquerda
        if(n < (*pRaiz)->num)
            inserir(&(*pRaiz)->L,n);
    }
}

/*Retonar o menor valor da árvore*/
No* min(No **pRaiz){
    //Anda até o ultimo nó à esquerda e o retorna
    if((*pRaiz)->L) min(&(*pRaiz)->L);
    
    return (*pRaiz);
}

/*Retonar o maior valor da árvore*/
No* max(No **pRaiz){
     //Anda até o ultimo nó à direita e o retorna
    if((*pRaiz)->R) max(&(*pRaiz)->R);
    
    return (*pRaiz);
}


/*Remove um número da àrvore (esta função não funciona caso o nó a ser removido tenha NETOS)

    REMOVENTO UM NÓ
    
    Casos:
    1) Nó não tem filhos: Apenas remove o nó defininindo NULL para sua conexão com o pai
        20      20
          \       \
           21     (X)
    
    2) Nó tem 1 filho: Faz com que o pai do nó aponte para o filho do nó e apaga o nó
        20          20          20
          \           \           \
           21          \  21       \  (X)
             \          \           \
              22         22         22
              
    3) 2 filhos: Substitui o nó pelo seu neto à esquerda do deu filho a direita, caso não tenha neto, substitui
        pelo filho a direita.
        
             x22x          (23)           (23)    
           /     \        /    \         /    \
        19       24     19     24      19     24
                /  \          /  \           /  \
             (23)  25      x22x   25        X   25
*/
No* remover(No **pRaiz,int n){
    
    //Caso não encontre número, exibe mensagem de erro
    if (*pRaiz == NULL) {
		printf("\n%d não existe nesta àrvore!\n",n);
		return *pRaiz;
	}
	
	//Procura e remove nó com o número a ser excluído
	if (n < (*pRaiz)->num){
	    (*pRaiz)->L = remover(&(*pRaiz)->L, n);  
	} 
	else if(n > (*pRaiz)->num){ 
	    (*pRaiz)->R = remover(&(*pRaiz)->R, n);
	}
    //Quando encontra
	else {
	    //Apenas 1 filho à direita
		if ((*pRaiz)->L == NULL) { 
			No *temp = (*pRaiz)->R;
			free(*pRaiz);
			return temp;
		}
		//Apenas 1 filho à esquerda
		else if ((*pRaiz)->R == NULL) { 
			No *temp = (*pRaiz)->L;
			free(*pRaiz);
			return temp;
		}
		
		//2 filhos
		No *temp = min(&(*pRaiz)->R); //Obtem nó com o menor número
		(*pRaiz)->num = temp->num; //Troca valores com o menor número
		(*pRaiz)->R = remover(&(*pRaiz)->R, temp->num); //Chama a remoção para a ultimo nó
	}
	
	return *pRaiz;
}

/*Retorna a altura de um nó*/
int altura(No **pRaiz) { 
    //Se não existe a altura é -1
    if ((*pRaiz) == NULL) return -1; 
    else { 
        //Obtem as alturas da esquerda e direita 
        int hl = altura(&(*pRaiz)->L);
        int hr = altura(&(*pRaiz)->R);
        //Retorna a hr+1 se a altura direita for maior, caso contrário retorna hl+1
        if (hl < hr)
          return hr + 1;  
        else
          return hl + 1;  
    } 
}

/*Calcula o fator de balanceamento da alvore*/
void getFb(No **pRaiz) {
    /*(fb) = hr - hl*/
	if (*pRaiz != NULL) {
		(*pRaiz)->fb = altura(&(*pRaiz)->R) - altura(&(*pRaiz)->L);
	    getFb(&(*pRaiz)->L); //Calcula fb da esquerda
        getFb(&(*pRaiz)->R); //Calcula fb da direita
	}
}


/*Rotação à direita*/
No* rotR(No** pRaiz){
    No* q,*temp;
    q = (*pRaiz)->L;
    temp = q->R;
    q->R = (*pRaiz);
    (*pRaiz)->L = temp;
    *pRaiz = q;
    return *pRaiz;
}

/*Rotação à esquerda*/
No* rotL(No** pRaiz){
    No* q = NULL;
    No* temp = NULL;
    q = (*pRaiz)->R;
    temp = q->L;
    q->L = *pRaiz;
    (*pRaiz)->R = temp;
    *pRaiz =  q;
    return *pRaiz;
}

/*Rotação esquerda-direita*/
No* rotLR(No** pRaiz){
    (*pRaiz)->L = rotL(&(*pRaiz)->L);
    return rotR(&(*pRaiz));
}

/*Rotação direita-esquerda*/
No* rotRL(No** pRaiz){
    (*pRaiz)->R = rotR(&(*pRaiz)->R);
    return rotL(&(*pRaiz));
}

/*Balanceia a àrvore (se fb < -1 ou > 1 está desbalanceada)*/
void balancear(No **pRaiz){
   do{
        getFb(&(*pRaiz));
        if((*pRaiz)->fb < -1){//Caso o nó esteja pesado para a esquerda (-)
            
            //Se o sinal do filho também for negativo rotação simples à direita
            if((*pRaiz)->L->fb <= 0)  
                *pRaiz = rotR(pRaiz);
            //Caso contrário rotação esquerda-direita
            else 
                *pRaiz = rotLR(pRaiz);
        
            
        }else if((*pRaiz)->fb > 1){//Caso nó esteja pesado para a direita (+)
            
             //Se o sinal do filho também for positivo rotação simples à esquerda
            if((*pRaiz)->R->fb >= 0) 
                *pRaiz = rotL(pRaiz);
            //Caso contrário rotação direita-esquerda
            else
                *pRaiz = rotRL(pRaiz);
            
        }
   }while((*pRaiz)->fb < -1 || (*pRaiz)->fb > 1); //Fazer isso enquando a raiz não estiver balanceada
}    

#define size 6 //número de nós
int main(void) {
    No *pRaiz;
    criarArvore(&pRaiz);
    
    //Insere nós
    int x[size] = {8,4,6,10,2,5};
    for(int i = 0; i < size; i++){
        inserir(&pRaiz,x[i]);      
    }
   
    //Mostra estado inicial
    printf("Antes:");
    showERD(&pRaiz);
    printf("\n");
    
    //Remove número 6
    remover(&pRaiz,6);
    //Balanceia a àrvore
    balancear(&pRaiz);
    //Mostra estado final da àrvore 
    printf("\n");
    printf("Depois:");
    showERD(&pRaiz);
    return 0;
}