Arvores balanceadas
#include
typedef struct arv{ int info,altura; struct arv *esq, *dir;
}*Arv;
Arv aloca_Arv(){ Arv aux=(struct arv*)malloc(sizeof(struct arv)); if (aux==NULL) printf("\n\n\t\tSem espaco de memoria."); return aux;
}
int altura(Arv raiz ){ if( raiz == NULL ) return 0; else return raiz->altura;
}
int calcular_altura(Arv esq, Arv dir ){ int ae, ad; ae=altura(esq); ad=altura(dir); if(ae>ad) return ae+1; else return ad+1;
}
int altura_maior(int a, int b){ if (a>=b) return a; else return b;
}
Arv rot_dir(Arv no){ Arv aux; aux = no->esq; no->esq = aux->dir; aux->dir = no; no->altura = altura_maior(altura(no->esq),altura(no->dir))+1; aux->altura = altura_maior(altura(aux->esq),altura(no))+1; return aux;
}
Arv rot_se(Arv no){ Arv aux; aux = no->dir; no->dir = aux->esq; aux->esq = no; no->altura = altura_maior(altura(no->esq),altura(no->dir))+1; aux->altura = altura_maior(altura(aux->dir),altura(no))+1; return aux;
}
Arv rd_esq_dir(Arv no){ no->esq = rot_se( no->esq ); return rot_dir(no);
}
Arv rd_dir_esq(Arv no){ no->dir=rot_dir(no->dir); return rot_se(no);
}
void verificaavl(Arv *no){ if ((*no)!=NULL){ if ( (altura((*no)->dir) - altura((*no)->esq))==-2){ if ( (altura((*no)->esq->dir) - altura((*no)->esq->esq) )==-1) *no=rot_dir(*no); else *no=rd_esq_dir(*no); }else if ( (altura((*no)->dir) - altura((*no)->esq))==2){ if((altura((*no)->dir->dir)-altura((*no)->dir->esq))==1) *no=rot_se(*no); else *no=rd_dir_esq(*no);