rotação/balanceamento - avl

[Murilo Marchiori]

Olá, amigos, bom dia.

Gostaria de saber se seria possivel uma pequena ajuda dos senhores com relação a um rebalanceamento de arvores avl. Na verdade, meu programa já está quase pronto, minha dificuldade é numa chamada de função. Segue meu codigo abaixo:

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


int main()
{
    int op=0, info=0, recebe=0;
    tArvore arvore;
    tNo *aux;
    
    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");
    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)
{
    //lembrar de verificar se o numero já existe
    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
        
        altura_raiz = altura(alt->dir) - altura(alt->esq);
        altura_ant = altura(ant->dir) - altura(ant->esq);
        
        /*
                
        if(altura_raiz > 0 && altura_ant > 0)
            //rotacao simples à esq da raiz
        else
            if(altura_raiz < 0 && altura_ant < 0)
                //rotacao simples à dir da raiz
            else
                if(altura_raiz < 0 && altura_ant > 0)
                {
                    //rotacao dupla 
                    //primeiro ant a esq
                    //depois raiz a direita
                }
                else
                {
                    //rotacao dupla 
                    //primeiro ant a dir
                    //depois raiz a esq
                }
        
        */
    }
}

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;
    
    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->dir == aux)
            {
                aux_ant->dir = NULL;
                delete aux;
            }
            else
            {
                aux_ant->dir = NULL;
                delete aux;
            }
        }
        else
            if(aux->dir != NULL && aux->esq != NULL) //caso3 - dois filhos
            {
                      tNo *menor, *anterior;
               
                      anterior = NULL;
                      menor = aux->esq;
               
                     while(menor->dir != NULL)
                     {
                    anterior = menor;
                menor = menor->dir;
             }
                    
            aux->num = menor->num;
               
            anterior->dir = menor->esq;
               
            delete menor;
            }
            else
                if(aux->dir == NULL) //caso2 - somente o filho da esquerda
                {
                       if(aux_ant->dir == aux)
                    {
                        aux_ant->dir = aux->esq;
                        delete aux;
                    }
                    else
                    {
                        aux_ant->esq = aux->esq;
                        delete aux;
                    }
                }
                else //caso2 - somente o filho da direita
                {
                    if(aux_ant->dir == aux)
                    {
                        aux_ant->dir = aux->dir;
                        delete aux;
                    }
                    else
                    {
                        aux_ant->esq = aux->dir;
                        delete aux;
                    }               
                }
                
    return 1;
                        
    }
    else
    {
        cout << "\n\nNo não encontrado.";
        return 0;
    }
 }

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

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

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; // altura de árvore vazia é -1
   else 
   {
      int he = altura(aux->esq);
      int hd = altura(aux->dir);
      
      if (he < hd) 
        return hd + 1;
      
      else 
        return he + 1;
   }
}

/*

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

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

*/

Minhas duas funções de rebalanceamento já estão feitas, elas estão comentadas no final do código, se os senhores quiserem dar uma olhada.

Mas eu gostaria de uma ajuda na função de inserção... Logo depois de inserir um numero, calculo as alturas dos nós, e tal... essa parte ta beleza... depois, tenho q rotacionar (isso esta comentado no final da função inserção)... mas eu não sei como chamar a função, não sei qual parametro passar... vocês podem ver pelo meu codigo de balanceamento que eu passo pra essa função o nó que quero rotacionar, o nó anterior a ele, e a raiz... mas e quando eu rotaciono a raiz? qual é o nó anterior a ela?

enfim, seria possivel uma ajuda somente na hora de chamar as funções de balanceamento?

Editado Novembro 20, 2010 por Murilo Marchiori