ESTRUTURA DE DADOS

[Guest tiagooot]

não consigo implementar em C++ a funcao de remocao em ARVORE AVL !!

Poderia alguém me ajudar nesta funcao !!!

SEGUE abaixo o programa sem a Opcao de remover !!

**********************************************************************

/*

Este programa insere elementos em uma arvore AVL,

fazendo as rotacoes necessarias para manter o balanceamento correto

*/

#include <iostream.h>

#include <conio.h>

struct AVL

{ int num, alte, altd;

AVL *esq, *dir;

};

AVL *rotacao_esq(AVL *no)

{ AVL *aux1, *aux2;

aux1 = no->dir;

aux2 = aux1->esq;

no->dir = aux2;

aux1->esq = no;

if (no->dir == NULL)

no->altd = 0;

else

{ if (no->dir->alte > no->dir->altd)

no->altd = no->dir->alte + 1;

else no->altd = no->dir->altd + 1;

}

if (aux1->esq->alte > aux1->esq->altd)

aux1->alte = aux1->esq->alte + 1;

else aux1->alte = aux1->esq->altd + 1;

return aux1;

}

AVL *rotacao_dir(AVL *no)

{ AVL *aux1, *aux2;

aux1 = no->esq;

aux2 = aux1->dir;

no->esq = aux2;

aux1->dir = no;

if (no->esq == NULL)

no->alte = 0;

else

{ if (no->esq->alte > no->esq->altd)

no->alte = no->esq->alte + 1;

else no->alte = no->esq->altd + 1;

}

if (aux1->dir->alte > aux1->dir->altd)

aux1->altd = aux1->dir->alte + 1;

else aux1->altd = aux1->dir->altd + 1;

return aux1;

}

AVL *inserir(AVL *r, int n)

{ AVL *novo;

int d;

if (r == NULL)

{ novo = new(AVL);

novo->num = n;

novo->alte=0;

novo->altd=0;

novo->esq = NULL;

novo->dir = NULL;

r=novo;

}

else

{

if (n < r->num)

{ r->esq = inserir(r->esq, n);

if (r->esq->alte > r->esq->altd)

r->alte = r->esq->alte + 1;

else r->alte = r->esq->altd + 1;

d = r->altd - r->alte;

if (d == 2)

{

if (r->dir->altd - r->dir->alte == 1)

{ cout << "\nRotação simples para esquerda";

r = rotacao_esq®;

}

else {

cout << "\nRotação Dupla: ";

cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda";

getch();

r->dir=rotacao_dir(r->dir);

r=rotacao_esq®;

}

}

if (d == -2)

{ if (r->esq->altd - r->esq->alte == -1)

{ cout << "\nRotação simples para direita";

r = rotacao_dir®;

}

else {

cout << "\nRotação Dupla: ";

cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita";

getch();

r->esq=rotacao_esq(r->esq);

r=rotacao_dir®;

}

}

}

else

{ r->dir = inserir(r->dir, n);

if (r->dir->alte > r->dir->altd)

r->altd = r->dir->alte + 1;

else r->altd = r->dir->altd + 1;

d = r->altd - r->alte;

if (d == 2)

{ if (r->dir->altd - r->dir->alte == 1)

{ cout << "\nRotação simples para esquerda";

r=rotacao_esq®;

}

else { cout << "\nRotação Dupla: ";

cout << "o filho rotaciona para a direita e o nó desbalanceado rotaciona para esquerda";

getch();

r->dir=rotacao_dir(r->dir);

r=rotacao_esq®;

}

}

if (d == -2)

{ if (r->esq->altd - r->esq->alte == -1)

{ cout << "\nRotação simples para direita";

r=rotacao_dir®;

}

else { cout << "\nRotação Dupla: ";

cout << "o filho rotaciona para a esquerda e o nó desbalanceado rotaciona para direita";

getch();

r->esq=rotacao_esq(r->esq);

r=rotacao_dir®;

}

}

}

}

return r;

} //fim inserir

void mostrar(AVL *r, int nivel)

{

if(r !=NULL)

{

mostrar(r->esq, nivel+1);

cout << "\n " << r->num << "\t Nivel" << nivel;

mostrar(r->dir, nivel+1);

}

} //fim mostrar

void main()

{ int op, aux;

AVL *raiz;

raiz = NULL;

do {

clrscr();

cout << "\n1- Inserir";

cout << "\n2- Mostrar";

cout << "\n3- Sair";

cout << "\nDigite a opção desejada: ";

cin >> op;

if(op==1)

{ cout << "\nDigite um número: ";

cin >> aux;

raiz = inserir(raiz, aux);

cout << "\nElemento inserido com sucesso. ";

}

else if (op==2)

{ mostrar(raiz,0);

}

getch();

} while (op != 3);

} //fim void main()