estrutura de dados 2 - 18/09/2019

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

typedef struct node {
   char chave;
   int altura;
   struct node* esq;
   struct node* dir;
} No, Arvore;

/*----------------------*/
int maior (int esq, int dir) {
   return (esq > dir ? esq : dir);
}

/*----------------------*/
int altura (Arvore* a)
{
    //se não tiver nenhum nó, altura é -1
    //caso contrário, retornar o que estiver no campo altura do nó
   return(a==NULL?-1:a->altura);
}

int atualizar_altura (Arvore *a)
{
    //ver qual dos descendentes tem altura maior
    //atribuir ao pai o maior dos filhos +1
    return(maior(altura(a->esq),altura(a->dir))+1);
}

/*----------------------*/
int balanceamento (Arvore *a)
{
    return(altura(a->dir)-altura(a->esq));
}

/*----------------------*/
Arvore* rotacao_simples_esq (Arvore* a)
{
    //criar um node temporário para armazernar
    //os ponteiros para os antigos
    node *t=a->dir;
    a->dir=t->esq;
    t->esq=a;
    a->altura=atualizar_altura(a);
    t->altura=atualizar_altura(t);
    return t;
}

/*----------------------*/
Arvore* rotacao_simples_dir (Arvore* a)
{
//espelho da rotação à esquerda
//trocando apenas os campos direita e esquerda
    node *t=a->esq;
    a->esq=t->dir;
    t->dir=a;
    a->altura=atualizar_altura(a);
    t->altura=atualizar_altura(t);
    return t;
}

/*----------------------*/
Arvore* rotacao_dupla_esq (Arvore* a)
{
    //vai utlizar as rotações simples definidas anteriormente
    a->dir=rotacao_simples_dir(a->dir);
    return rotacao_simples_esq(a);
}

/*----------------------*/
Arvore* rotacao_dupla_dir (Arvore* a)
{
    //espelho da rotação dupla à esquerda
    //apenas mudando direita por esquerda
    a->dir=rotacao_simples_esq(a->esq);
    return rotacao_simples_dir(a);
}

/*----------------------*/
Arvore* atualizar_fb_dir (Arvore *a)
{
//espelho de atualizar_fb_esq
//direita e esquerda das rotações invertidas
//-2 invertido, <= invertido
    if(balanceamento(a)==2)
    {
        if(balanceamento(a->dir)>=0)
            {
            a=rotacao_simples_esq(a);
            }
        else
            {
            a=rotacao_dupla_esq(a);
            }
    }
    return a;
}

/*----------------------*/
Arvore* atualizar_fb_esq (Arvore *a)
{
    //se o fator de balanceamento for igual a -2
    //rotacionar para rebalancear
    if(balanceamento(a)==-2)
    {
        if(balanceamento(a->esq)<=0)
            {
            a=rotacao_simples_dir(a);
            }
        else
            {
            a=rotacao_dupla_dir(a);
            }
    }
    return a;
}

/*----------------------*/
Arvore* inserir (Arvore *a, char chave)
{
    //se a árvore estiver vazia, criar um nó raiz
    //atribuir nela a chave passada
    //preecher a altura dessa raiz como 0
    //e os filhos como NULL
    if(a==NULL)
    {
        a=(No*)malloc(sizeof(No));
        a->chave=chave;
        a->altura=0;
        a->esq=a->dir=NULL;
    }
    //se já existe uma raiz
    //chamar recursivamente o inserir
    //olhando se deve colocar à esquerda (menor) ou à direita (se for maior)
    else if(chave<a->chave)
    {
        a->esq = inserir(a->esq,chave);
        a=atualizar_fb_esq(a);
    }
    else
    {
        a->dir = inserir(a->dir,chave);
        a=atualizar_fb_dir(a);
    }
    return a;
}

/*----------------------*/
Arvore* remover (Arvore *a, char chave) {
   if (a == NULL) {
      return NULL;
   }
   else {
      if (chave < a->chave) {
         a->esq = remover (a->esq, chave);
         a = atualizar_fb_dir (a);
      }
      else if (chave > a->chave) {
         a->dir = remover (a->dir, chave);
         a = atualizar_fb_esq (a);
      }
      else {
         if ((a->esq == NULL) && (a->dir == NULL)) {
            free (a);
            a = NULL;
         }
         else if (a->esq == NULL) {
            No *tmp = a;
            a = a->dir;
            free (tmp);
         }
         else if (a->dir == NULL) {
            No *tmp = a;
            a = a->esq;
            free (tmp);
         }
         else {
            No *tmp = a->esq;
            while (tmp->dir != NULL) {
               tmp = tmp->dir;
            }
            a->chave = tmp->chave;
            tmp->chave = chave;
            a->esq = remover (a->esq, chave);
            a = atualizar_fb_dir (a);
         }
      }
      return a;
   }
}

/*----------------------*/
void imprimir_in_order (Arvore* a, int nivel) {
   if (a != NULL) {
      int i;
      for (i = 0; i < nivel; i++) {
         printf("      ");
      }
      printf("Chave: %c (altura: %d, fb: %+d) no nível: %d\n", a->chave, a->altura, balanceamento(a), nivel);
      imprimir_in_order (a->esq, nivel + 1);
      imprimir_in_order (a->dir, nivel + 1);
   }
}

/*----------------------*/
int main () {

   Arvore *AVL = NULL;
    //ex1: inserir os termos passados
   AVL = inserir (AVL, 'Q');
   AVL = inserir (AVL, 'Z');
   AVL = inserir (AVL, 'B');
   AVL = inserir (AVL, 'Y');
   AVL = inserir (AVL, 'T');
   AVL = inserir (AVL, 'M');
   AVL = inserir (AVL, 'E');
   AVL = inserir (AVL, 'W');
   AVL = inserir (AVL, 'X');
   AVL = inserir (AVL, 'S');
   AVL = inserir (AVL, 'F');
   AVL = inserir (AVL, 'G');
   AVL = inserir (AVL, 'A');
   AVL = inserir (AVL, 'H');
   AVL = inserir (AVL, 'N');
   AVL = inserir (AVL, 'O');
   AVL = inserir (AVL, 'P');
   AVL = inserir (AVL, 'R');

    imprimir_in_order (AVL, 0);

   /*Complete!!!*/

   //AVL = remover (AVL, 'A');
   //AVL = remover (AVL, 'H');
   //AVL = remover (AVL, 'E');
   //AVL = remover (AVL, 'W');
   //AVL = remover (AVL, 'G');
   //AVL = remover (AVL, 'N');
   //AVL = remover (AVL, 'P');
   //AVL = remover (AVL, 'O');

   imprimir_in_order (AVL, 0);

   return 0;
}