Rotação - avl

[Murilo Marchiori]

Olá, amigos, bom dia. Gostaria da ajuda dos senhores para encontrar um erro na minha função de rotação, ou na chamada da mesma, não sei... Vou postar o código inteiro caso os senhores precisem de alguma informação extra, embora ache dificil... O erro está na chamada das funções de rotação, dentro da função de inserção, ou dentro das próprias funções de rotação (esq e dir). Essas duas funções estão no final do código, e a chamada para elas está comentada dentro da função de inserção. O problema é que, com o decorrer das inserções, chega uma hora em que entro em um laço infinito... Se alguém puder ajudar, agradeço. Segue o código:

#include <iostream>
#include <cstdlib>
using namespace std;

struct tNo
{
    int num;
    tNo *esq;
    tNo *dir;
};

struct tArvore
{
    tNo *raiz;
};

int menu();
int insercao(tArvore &ar,int inf);
int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf);
int remove(tArvore &ar, int inf);
void preOrdem(tNo *aux);
void emOrdem(tNo *aux);
void posOrdem(tNo *aux);
int altura(tNo *aux);
void rot_dir(tNo *aux, tNo *ant, tArvore &ar);
void rot_esq(tNo *aux, tNo *ant, tArvore &ar);

int main()
{
    int op=0, info=0, recebe=0;
    tArvore arvore;
    
    arvore.raiz = NULL;
    
    do
    {
        op = menu();
    
        if(op == 1)
        {
            cout << "\n\nDigite o valor a ser inserido: ";
            cin >> info;
            
            recebe = insercao(arvore, info);
            
            if(recebe == 0)
                cout << "\n\nImpossÃ*vel realizar a operacao";
            
            preOrdem(arvore.raiz);
        }
        
        else
            if(op == 2)
            {
                cout << "\n\nDigite o numero a ser removido: ";
                cin >> info;
                recebe = remove(arvore, info);
                
                if(recebe == 0)
                    cout << "\n\nImpossÃ*vel realizar a operacao";
                    
                preOrdem(arvore.raiz);
            }    
    
    } while(op != 3);
}

int menu()
{
    int op=0;
    
    //system("clear"); // so para poder ver os testes 
    cout << "\n\nMenu: ";
    
    cout << "\n\n1- Insercao";
    cout << "\n2- Remocao";
    cout << "\n3- Sair";
    
    cout << "\n\nDigite sua opcao: ";
    cin >> op;
    
    while(op < 0 || op > 3)
    {
        cout << "\n\nOpcao invalida. Digite novamente: ";
        cin >> op;
    }
    
    return op;
}

int insercao(tArvore &ar,int inf) 
{
    tNo *novo_no = new tNo;
    
    if(novo_no == NULL)
        return 0;
            
    novo_no->num = inf;
    novo_no->esq = NULL;
    novo_no->dir = NULL;
    
    if(ar.raiz == NULL)
    {
        ar.raiz = novo_no;
        return 1;
    }
    else
    {
        int altura_raiz = 0, altura_ant = 0, flag=0;
        tNo *aux, *alt, *ant, *back_ant;
        
        aux = alt = ar.raiz;
        ant=NULL;
        back_ant=NULL;
        
        while(flag==0)
        {
            if(inf < aux->num)
            {
                if(aux->esq != NULL)
                {
                    back_ant = ant;
                    ant = aux;
                    aux = aux->esq;
                }
                else
                {
                    aux->esq = novo_no;
                    flag=1;
                }
            }
            else
            {
                if(aux->dir != NULL)
                {
                    back_ant = ant;
                    ant = aux;
                    aux = aux->dir;
                }
                else
                {
                    aux->dir = novo_no;
                    flag=1;
                }
            }
        }
        
        //calcular alturas e fazer o balanceamento.
        
        //NÃO FUNCIONA
        
        if(ant != NULL) // coloquei este if...
        {
                        
            altura_raiz = altura(alt->dir) - altura(alt->esq);
            altura_ant = altura(ant->dir) - altura(ant->esq);
            
            
            if(altura_raiz > 0 && altura_ant > 0)
                rot_esq(alt, ant, ar);
            else
                if(altura_raiz < 0 && altura_ant < 0)
                    rot_dir(alt, ant, ar);
                else
                    if(altura_raiz < 0 && altura_ant > 0)
                    {
                        rot_esq(ant, back_ant, ar);
                        rot_dir(alt, ant, ar);
                    }
                    else
                        if(altura_raiz > 0 && altura_ant < 0) //coloquei este if
                        {
                            rot_dir(ant, back_ant, ar);
                            rot_esq(alt, ant, ar);
                        }
        }    
        
        return 1;
    }
}

int busca(tArvore &ar, tNo *&aux, tNo *&aux_ant, int inf)
{    
    while(aux)
    {        
        if(aux->num == inf)
            return 1;
        
        else
        {
            if(inf < aux->num)
            {
                aux_ant = aux;
                aux = aux->esq;
            }
            else
            {
                aux_ant = aux;
                aux = aux->dir;
            }    
        }
    }
    
    return 0;
}

int remove(tArvore &ar, int inf)
{
    tNo *aux_ant, *aux;
    int cont=0;
    
    aux_ant = NULL;
    aux = ar.raiz;
    
    if(busca(ar, aux, aux_ant, inf) == 1)
    {
        if(aux->dir == NULL && aux->esq == NULL) //caso1 - sem filhos
        {
            if(aux_ant != NULL)
            {                
                if(aux_ant->dir == aux)
                {
                    aux_ant->dir = NULL;
                    delete aux;
                }
                else
                {
                    aux_ant->esq = NULL;
                    delete aux;
                }
            }
            else
            {                    
                ar.raiz = NULL;
                delete aux;                
            }            
        }
        else
            if(aux->dir != NULL && aux->esq != NULL) //caso3 - dois filhos
            {
               tNo *maior, *anterior;
                   
               anterior = NULL;
               maior = aux->esq;
               
               while(maior->dir != NULL)
               {
                   anterior = maior;
                   maior = maior->dir;
                   cont=1;
               }
               
               if(aux_ant != NULL)
               {                        
                   aux->num = maior->num;
                   
                   if(cont == 0)
                        aux->esq = maior->esq;
                   else
                          anterior->dir = NULL;
                   delete maior;        
               }
               else
               {
                   aux->num = maior->num;
                   aux->esq = maior->esq;
                   
                   delete maior;                   
               }                
            }
            else
                if(aux->dir == NULL) //caso2 - somente o filho da esquerda
                {
                       if(aux_ant != NULL)
                       {
                        
                        if(aux_ant->dir == aux)
                        {
                            aux_ant->dir = aux->esq;
                            delete aux;
                        }
                        else
                        {
                            aux_ant->esq = aux->esq;
                            delete aux;
                        }
                    }
                    else
                    {
                        ar.raiz = aux->esq;
                        delete aux;
                    }                    
                }
                else //caso2 - somente o filho da direita
                {
                    if(aux_ant != NULL)
                    {
                        
                        if(aux_ant->dir == aux)
                        {
                            aux_ant->dir = aux->dir;
                            delete aux;
                        }
                        else
                        {
                            aux_ant->esq = aux->dir;
                            delete aux;
                        } 
                    }
                    else
                    {
                        ar.raiz = aux->dir;
                        delete aux;
                    }
                }
                
        return 1;                        
    }
    else
    {
        cout << "\n\nNo não encontrado.";
        return 0;
    }
 }

void preOrdem(tNo *aux)
{
    if(aux != NULL)
    {
        cout << aux->num << " ";
    
        if(aux->esq != NULL)
            preOrdem(aux->esq);
            
        if(aux->dir != NULL)
            preOrdem(aux->dir);
    }
    else
        cout << "\n\nA arvore esta vazia";
}

void emOrdem(tNo *aux)
{
    if(aux != NULL)
    {        
        if(aux->esq != NULL)
            emOrdem(aux->esq);
        
        cout << aux->num << " ";
        
        if(aux->dir != NULL)
            emOrdem(aux->dir);
    }
    else
        cout << "\n\nA arvore esta vazia";
}

void posOrdem(tNo *aux)
{
    if(aux->esq != NULL)
     posOrdem(aux->esq);
    
    if(aux->dir != NULL)
              posOrdem(aux->dir);
        
    cout << aux->num <<" ";
}

int altura(tNo *aux) 
{
   if (aux == NULL) 
      return -1;
   else 
   {
      int he = altura(aux->esq);
      int hd = altura(aux->dir);
      
      if (he < hd) 
    return hd + 1;
      
      else 
    return he + 1;
   }
}

void rot_dir(tNo *aux, tNo *ant, tArvore &ar)
{
    tNo *q, *temp;
    
    q = aux->esq;
    temp = q->dir;
    q->dir = aux;
    aux->esq = temp;
    
    if(ant != aux)
    {
        if(ant->esq == aux)
            ant->esq = q;
        else
            ant->dir = q;
        
        ar.raiz = ant;
    }
    else
        ar.raiz = q;
}

void rot_esq(tNo *aux, tNo *ant, tArvore &ar)
{
    tNo *q, *temp;
    
    q = aux->dir;
    temp = q->esq;
    q->esq = aux;
    aux->dir = temp;
    
    if(ant != aux)
    {
        if(ant->esq == aux)
            ant->esq = q;
        else
            ant->dir = q;
        
        ar.raiz = ant;
    }
    else
        ar.raiz = q;
}