Arvor AVL

AVL
#include "TADpilha.h" void Init(Tree **raiz)
{ *raiz=NULL;
}
Tree* CriaNo(int info)
{ Tree *nova=(Tree*)malloc(sizeof(Tree)); nova->info=info; nova->esq=NULL; nova->dir=NULL; return nova;
}
void rotacao_esquerda(Tree **p)
{ Tree *q, *temp; q = (*p)->dir; temp = q->esq; q->esq = *p;
(*p)->dir = temp;
*p = q;
}
void rotacao_direita(Tree **p)
{
Tree *q, *temp; q = (*p)->esq; temp = q->dir; q->dir = *p;
(*p)->esq = temp;
*p = q;
}
int Altura(Tree *raiz)
{ int esq,dir; if(raiz!=NULL) { esq = Altura(raiz->esq); dir = Altura(raiz->dir); if(esq > dir) return esq+1; else return dir+1;
}
else return 0;
}
void insereAVL(Tree **raiz, int info, int &flag)
{
int fb, fb_filho; if(*raiz == NULL)
{ *raiz = CriaNo(info);

flag = 0;
}
else
{
if(info > (*raiz)->info) insereAVL(&(*raiz)->dir, info, flag); else insereAVL(&(*raiz)->esq, info, flag); if(!flag) { fb = Altura((*raiz)->dir) - Altura((*raiz)->esq); if(abs(fb) == 2) // desbalaneceado
{ flag = 1; if(fb == 2)
{ fb_filho = Altura((*raiz)->dir->dir)-Altura((*raiz)->dir->esq); if(fb_filho == 1) rotacao_esquerda(&(*raiz)); else
{ rotacao_direita(&(*raiz)->dir); rotacao_esquerda(&(*raiz)); }
}
else
{
fb_filho = Altura((*raiz)->esq->dir)-Altura((*raiz)->esq->esq); if(fb_filho == -1) rotacao_direita(&(*raiz)); else
{ rotacao_esquerda(&(*raiz)->esq); rotacao_direita(&(*raiz)); }
}
}
}
}
}

bool Folha(Tree *e)
{ return (e->esq == NULL && e->dir == NULL);
}
bool um_filho(Tree *e)
{ return (e->esq == NULL || e->dir == NULL);
}

void ExclusaoABB(Tree **raiz, Tree *e, Tree *pai, char lado)
{
if(Folha(e))
{ if(e != pai)
{ if(e->info > pai->info)

pai->dir = NULL; else pai->esq = NULL;
}
else
*raiz = NULL; free(e); } else { if(um_filho(e)) { if(e != pai)
{
if(e->info > pai->info) if(e->esq != NULL) pai->dir = e->esq; else pai->dir = e->dir; if(e->info < pai->info) if(e->esq != NULL) pai->esq = e->esq; else pai->esq =