Semana_7/AVL.c
bool excluirAVL(PONT* raiz, TIPOCHAVE ch, bool* alterou){
  PONT atual = *raiz;
  if (!atual) {
    *alterou = false;
    return false;
  }
  if (atual->chave == ch){
    PONT substituto, pai_substituto;
    if(!atual->esq || !atual->dir) { // tem zero ou um filho
      if(atual->esq) substituto = atual->esq;
      else substituto = atual->dir;
      *raiz = substituto;
      free(atual);
      *alterou = true;
      return true;
    }
    else {   // tem dois filhos
      substituto = maiorAEsquerda(atual,&pai_substituto);
      atual->chave = substituto->chave;
      ch = substituto->chave; // continua o codigo excluindo o substituto
    }
  }
  bool res;
  if (ch > atual->chave) {
    res = excluirAVL(&(atual->dir), ch, alterou);
    printf("Excluir recursivo a direita: %i(%i)\n", atual->chave, atual->bal);
    if (*alterou){
       switch (atual->bal){
          case 1: atual->bal = 0;
          return true;
          case 0: atual->bal = -1;
          *alterou = false;
          return true;
          case -1: *raiz = rotacaoL(atual);
          if (atual->bal != 0) *alterou = false;
          return true;
       }
    }
  }else{
    res = excluirAVL(&(atual->esq), ch, alterou);
    printf("Excluir recursivo a esquerda: %i(%i)\n", atual->chave, atual->bal);
    if (*alterou){
       switch (atual->bal){
          case -1: atual->bal = 0;
          return true;
          case 0: atual->bal = 1;
          *alterou = false;
          return true;
          case 1: *raiz = rotacaoR(atual);
          if (atual->bal != 0) *alterou = false;
          return true;
       }
    }
  }
  return res;
}
/* exclui a chave com valor igual a ch   */
exclui a chave com valor igual a ch
exclui a chave com valor igual a ch
bool excluirAVL(PONT* raiz, TIPOCHAVE ch, bool* alterou){
  PONT atual = *raiz;
  if (!atual) {
    *alterou = false;
    return false;
  }
  if (atual->chave == ch){
    PONT substituto, pai_substituto;
    if(!atual->esq || !atual->dir) { 
      if(atual->esq) substituto = atual->esq;
      else substituto = atual->dir;
      *raiz = substituto;
      free(atual);
      *alterou = true;
      return true;
    }
    else {   
      substituto = maiorAEsquerda(atual,&pai_substituto);
      atual->chave = substituto->chave;
      ch = substituto->chave; 
    }
  }
  bool res;
  if (ch > atual->chave) {
    res = excluirAVL(&(atual->dir), ch, alterou);
    printf("Excluir recursivo a direita: %i(%i)\n", atual->chave, atual->bal);
    if (*alterou){
       switch (atual->bal){
          case 1: atual->bal = 0;
          return true;
          case 0: atual->bal = -1;
          *alterou = false;
          return true;
          case -1: *raiz = rotacaoL(atual);
          if (atual->bal != 0) *alterou = false;
          return true;
       }
    }
  }else{
    res = excluirAVL(&(atual->esq), ch, alterou);
    printf("Excluir recursivo a esquerda: %i(%i)\n", atual->chave, atual->bal);
    if (*alterou){
       switch (atual->bal){
          case -1: atual->bal = 0;
          return true;
          case 0: atual->bal = 1;
          *alterou = false;
          return true;
          case 1: *raiz = rotacaoR(atual);
          if (atual->bal != 0) *alterou = false;
          return true;
       }
    }
  }
  return res;
}
bool excluirAVL ( PONT * raiz , TIPOCHAVE ch , bool * alterou ) { PONT atual = * raiz ; if ( ! atual ) { * alterou = false ; return false ; } if ( atual -> chave == ch ) { PONT substituto , pai_substituto ; if ( ! atual -> esq || ! atual -> dir ) { if ( atual -> esq ) substituto = atual -> esq ; else substituto = atual -> dir ; * raiz = substituto ; free ( atual ) ; * alterou = true ; return true ; } else { substituto = maiorAEsquerda ( atual , & pai_substituto ) ; atual -> chave = substituto -> chave ; ch = substituto -> chave ; } } bool res ; if ( ch > atual -> chave ) { res = excluirAVL ( & ( atual -> dir ) , ch , alterou ) ; printf ( " \n " , atual -> chave , atual -> bal ) ; if ( * alterou ) { switch ( atual -> bal ) { case 1 : atual -> bal = 0 ; return true ; case 0 : atual -> bal = -1 ; * alterou = false ; return true ; case -1 : * raiz = rotacaoL ( atual ) ; if ( atual -> bal != 0 ) * alterou = false ; return true ; } } } else { res = excluirAVL ( & ( atual -> esq ) , ch , alterou ) ; printf ( " \n " , atual -> chave , atual -> bal ) ; if ( * alterou ) { switch ( atual -> bal ) { case -1 : atual -> bal = 0 ; return true ; case 0 : atual -> bal = 1 ; * alterou = false ; return true ; case 1 : * raiz = rotacaoR ( atual ) ; if ( atual -> bal != 0 ) * alterou = false ; return true ; } } } return res ; }
exclui a chave com valor igual a ch
exclui a chave com valor igual a ch
// tem zero ou um filho // tem dois filhos // continua o codigo excluindo o substituto