/* protótipo das funções auxiliares... */
Tree insertRight(Tree t, TreeEntry e, int *cresceu);
Tree balanceRight(Tree t);
Tree insertLeft(Tree t, TreeEntry e, int *cresceu);
Tree balanceLeft(Tree t);
Tree rotateRight(Tree t);
Tree rotateLeft(Tree t);



/*
  Inserção numa árvore AVL.

  o parâmetro "cresceu" é uma flag passada por referência (1 indica
que a inserção fez crescer a altura da árvore; 0 indica que a
altura se manteve.
*/
Tree insertTree(Tree t, TreeEntry e, int *cresceu) {
  if (t==NULL){
    t=(Tree)malloc(sizeof(struct treenode));
    t->entry=e;
    t->right=NULL;
    t->left=NULL;
    t->bf=EH;
    *cresceu=1;
  }
  else if (e==t->entry) {
    printf("ERRO!");
  }
  else if (e>t->entry) {
    t=insertRight(t,e,cresceu);
  }
  else {
    t=insertLeft(t,e,cresceu);
  }
  return(t);
}

Tree insertRight(Tree t, TreeEntry e, int *cresceu) {
  t->right=insertTree(t->right,e,cresceu);
  if (*cresceu) {
    switch (t->bf) {
    case LH:
      t->bf=EH;
      *cresceu=0;
      break;
    case EH:
      t->bf=RH;
      *cresceu=1;
      break;
    case RH:
      t=balanceRight(t);
      *cresceu=0;
    }
  }
  return t;
}

Tree balanceRight(Tree t) {
  Tree aux;

  if (t->right->bf==RH) {
    // Rotacao simples a esquerda
    t=rotateLeft(t);
    t->bf=EH;
    t->left->bf=EH;
  }
  else {
    //Dupla rotacao
    t->right=rotateRight(t->right);
    t=rotateLeft(t);
    switch (t->bf) {
    case EH:
      t->left->bf=EH;
      t->right->bf=EH;
      break;
    case LH:
      t->left->bf=EH;
      t->right->bf=RH;
      break;
    case RH:
      t->left->bf=LH;
      t->right->bf=EH;
    }
    t->bf=EH;
  }
  return t;
}

Tree insertLeft(Tree t, TreeEntry e, int *cresceu) {
  // ...completar...
}

Tree balanceLeft(Tree t) {
  // ...completar...
}

Tree rotateRight(Tree t) {
  // ...completar...
}

Tree rotateLeft(Tree t) {
  Tree aux;

  if ((! t)||(! t->right)) {
    printf("Erro\n");
  }
  else {
    aux=t->right;
    t->right=aux->left;
    aux->left=t;
    t=aux;
  }

  return t;
}