Arvore AVL
#include
#define OK 1
#define ERRO 0
typedef struct def_arvore { int Dado; int altura; struct def_arvore *FilhoEsq; struct def_arvore *FilhoDir; struct def_arvore *Pai; } tipo_arvore;
//tipo_arvore *nodo=NULL;
int altura(tipo_arvore* t){ if (t == NULL) return 0; return t->altura;
}
int max(int a, int b){ return (a > b) ? a : b;
}
tipo_arvore* aloca(int dado){ tipo_arvore* raiz = (tipo_arvore*) malloc (sizeof(tipo_arvore)); raiz->Dado = dado; raiz->FilhoDir = raiz->FilhoEsq = NULL; raiz->altura = 0; return (raiz);
}
tipo_arvore* rotacao_direita(tipo_arvore* p){ tipo_arvore* q = p->FilhoEsq; tipo_arvore* temp = q->FilhoDir; q->FilhoDir = p; p->FilhoEsq = temp; p = q; p->altura = max(altura(p->FilhoEsq), altura(p->FilhoDir))+1; q->altura = max(altura(q->FilhoEsq), altura(q->FilhoDir))+1; return q;
}
tipo_arvore* rotacao_esquerda(tipo_arvore* p){ tipo_arvore* q = p->FilhoDir; tipo_arvore* temp = q->FilhoEsq; q->FilhoEsq = p; p->FilhoDir = temp; p = q; p->altura = max(altura(p->FilhoEsq), altura(p->FilhoDir))+1; q->altura = max(altura(q->FilhoEsq), altura(q->FilhoDir))+1; return q;
}
int fatorBal(tipo_arvore* t){ if (t == NULL) return 0; return altura(t->FilhoEsq) - altura(t->FilhoDir);
}
tipo_arvore* insere(tipo_arvore* aux, int dado){ if (aux == NULL) return (aloca(dado)); if (dado < aux->Dado) aux->FilhoEsq = insere(aux->FilhoEsq, dado); else aux->FilhoDir = insere(aux->FilhoDir, dado); // Atualiza a altura do nó aux->altura = max(altura(aux->FilhoEsq), altura(aux->FilhoDir)) + 1; // Verifica o fator de balanceamento pra ver se está balanceado int bal = fatorBal(aux);