//---------------------- ARVORE_AVL


int contaAvl(No *no){
	if(!no) return 0;
	return contaAvl(no->dir) + 1  + contaAvl(no->esq);
}

int retMax(No *n_dir,No * n_esq){
	int dir, esq;
	dir = contaAvl(n_dir);
	esq = contaAvl(n_esq);
	if(dir < esq)return dir;
	else return esq;
}

No* rotacoes_d(No *n)
{
	No* aux = n->esq;
	n->esq = aux->dir;
	aux->dir = n;

	n->altura = retMax(n->dir,n->esq)+1;
	aux->altura = retMax(n->dir,n->esq)+1;
	return aux;
}


No* rotacoes_e(No *n)
{
	No* aux = n->dir;
	n->dir = aux->esq;
	aux->esq = n;

	n->altura = retMax(n->dir,n->esq)+1;
	aux->altura = retMax(n->dir,n->esq)+1;
	return aux;
}

No* esquerdaDireita(No* no){
    no-> esq = rotacoes_e(no-> esq);
    return rotacoes_d(no);
}

No* direitaEsquerda(No* no){
    no->dir = rotacoes_d(no->dir);
    return rotacoes_e(no);
}

No* insere_avl(No *no,int valor){
    if(!no) no = cria_no(valor);
    if (valor < no->valor)
    {
        no->esq = insere_avl(no->esq,valor);
        if((no->esq->altura - no->dir->altura) == 2)
            if(valor < no->esq->valor)
                no = rotacoes_d(no);
            else
                no = esquerdaDireita(no);
    }else{
        if(valor > no->dir->valor)
            no->dir = insere_avl(no->dir,valor);
        if((no->dir->altura - no->esq->altura) == 2)
            if(valor > no->dir->valor)
                no = rotacoes_e(no);
            else
                no = direitaEsquerda(no);
    }
    no->altura = retMax(no->dir,no->esq)+1;
    return no;

}

void insere_arvore_avl(Colecao* c, int valor)
{
    insere_avl(c->inicio, valor);
    return;
}