/*
 * Árvore 2-3
 *
 * Uma implementação com vetores seria mais flexível/elegante?
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct no23{
  int nch;                        /* Número de chaves no nó */  
  struct no23* esq;               /* Apontador esquerdo */
  int chesq;                      /* Chave esquerda     */ 
  struct no23* cen;               /* Apontador central  */ 
  int chdir;                      /* Chave direita      */ 
  struct no23* dir;               /* Apontador direito  */
} No23;

/* Variável global para facilitar visualização */
No23* arv = NULL;

/* Cria um nó interno com uma única chave */
No23* no1(No23* esq, int chesq, No23* cen) {
  No23* n = (No23*) malloc (sizeof (No23));
  n->nch = 1;
  n->esq = esq;
  n->chesq = chesq;
  n->cen = cen;
  return n;
}

/* Cria um nó interno com duas chaves */
No23* no2(No23* esq, int chesq, No23* cen, int chdir, No23* dir) {
  No23* n = (No23*) malloc (sizeof (No23));
  n->nch = 2;
  n->esq = esq;
  n->chesq = chesq;
  n->cen = cen;
  n->chdir = chdir;
  n->dir = dir;
  return n;
}

/* Cria uma folha com uma única chave */
No23* folha1(int chesq) {
  No23* n = (No23*) malloc (sizeof (No23));
  n->nch = 1;
  n->esq = NULL;
  n->chesq = chesq;
  n->cen = NULL;
  return n;
}

/* Cria uma folha com duas chaves */
No23* folha2(int chesq, int chdir) {
  No23* n = (No23*) malloc (sizeof (No23));
  n->nch = 2;
  n->esq = NULL;
  n->chesq = chesq;
  n->cen = NULL;
  n->chdir = chdir;
  n->dir = NULL;
  return n;
}

/* Cria a árvore:
                  20 42
          /         |          \
       16         25 31         46
      /	 \	/   |   \     /     \
     5	  17  21  27 29  34  43 44  61
*/
No23 *exemplo() {
  return no2(no1(folha1(5), 16, folha1(17)),
	       20,
	       no2(folha1 (21),
		     25,
		     folha2 (27,29),
		     31,
		     folha1(34)),
	       42,
	       no1(folha2(43, 44), 46, folha1(61)));
}

/* Imprime o conteúdo da árvore no formato 
   (((5) 16 (17)) 20 ((21) 25 (27 29) 31 (34)) 42 ((43 44) 46 (61)))
 */ 
void imprime(No23* arv) {
  if (arv != NULL) {
    printf("(");
    if (arv->esq) { // Não é folha
      imprime(arv->esq);
      if (arv->nch >= 1) {  /* Teste extra para o remove (passos intermediários) */
	printf(" %d ", arv->chesq);
	imprime(arv->cen);
	if (arv->nch == 2) {
	  printf(" %d ", arv->chdir);
	  imprime(arv->dir);
	}
      }
    }
    else { // É folha
      if (arv->nch >= 1)  /* Teste extra para o remove (passos intermediários) */
	printf("%d", arv->chesq);
      if (arv->nch == 2) 
	printf(" %d", arv->chdir);
    }
    printf(")");
  }
}

int altura(No23* n){
  int h = 0;
  while (n != NULL) {
    h++;
    n = n->esq;
  }
  return h;
}


No23* busca(No23* n, int chave) {
  if (n == NULL)
    return NULL;
  if (chave < n->chesq)
    return busca (n->esq, chave);
  if (chave == n->chesq)
    return n;
  if (n->nch == 1)
    return busca (n->cen, chave);
 if (chave < n->chdir)
    return busca (n->cen, chave);
  if (chave == n->chdir)
    return n;  
  return busca (n->dir, chave);
}

void libera(No23* arv) {
}


/****************************** Remoção **************************/

/* Remove chave à esquerda, alterando o valor de n->nch e 
   deslocando se for o caso, a chave à direita. */
void remove_ch_esq(No23* n) {
  if (n->nch == 2) {
    n->esq = n->cen;
    n->chesq = n->chdir;
    n->cen = n->dir;
  }
  n->nch--;
  imprime(arv);
  printf("\n");
}

/* Remove a chave à direita, simplesmente alterando o valor 
   de n->nch. */
void remove_ch_dir(No23* n) {
  n->nch = 1;
  imprime(arv);
  printf("\n");
}


/* Nó à esquerda está vazio. Arruma a árvore. */
void esquerda_vazio (No23* n) {
  n->esq->chesq = n->chesq;
  n->esq->cen = n->cen->esq;
  if (n->cen->nch == 2) {
    n->chesq = n->cen->chesq;
    n->esq->nch = 1;
    remove_ch_esq(n->cen);
  }
  else {
    n->esq->chdir = n->cen->chesq;
    n->esq->dir = n->cen->dir;
    n->esq->nch = 2;
    remove_ch_esq(n);
    free(n->cen);
  }
}

/* Nó central está vazio. Arruma a árvore. */
void central_vazio (No23* n) {
  if (n->esq->nch == 2) {
    n->cen->cen = n->cen->esq;
    n->cen->chesq = n->chesq;
    n->cen->esq = n->esq->dir;
    n->chesq = n->esq->chdir;
    n->cen->nch = 1;
    n->esq->nch = 1;
    remove_ch_dir(n->esq);
  }
  else {
    n->cen->chesq = n->chdir;
    n->cen->cen = n->dir->esq; 
    if (n->dir->nch == 2) {
      n->chdir = n->dir->chesq;
      n->cen->nch = 1;
      remove_ch_esq(n->dir);
    }
    else {
      n->cen->chdir = n->dir->chesq;
      n->cen->dir = n->cen->dir;
      n->cen->nch = 2;
      remove_ch_esq(n);
      free(n->dir);
    }
  }
}

/* Nó central está vazio. Arruma a árvore. */
void direita_vazio (No23* n) {
  if (n->cen->nch == 2) {
    n->dir->cen = n->dir->esq;
    n->dir->chesq = n->chdir;
    n->dir->esq = n->cen->dir;
    n->chdir = n->cen->chdir;
    n->cen->nch = 1;
    n->dir->nch = 1;
    remove_ch_dir(n->cen);
  }
  else {
    n->cen->chesq = n->chdir;
    n->cen->cen =  n->dir->esq;
    n->cen->chdir = n->dir->chdir;
    n->cen->dir = n->dir->cen;
    n->cen->nch = 2;
    remove_ch_dir(n);
    free(n->dir);
  }
}

/* Substitui a chave posicionada em *ap_ch pela chave
   mais à esquerda da árvore n. */
void substitui_rec(No23* n, int* ap_ch) {
  if (n->esq == NULL) {
    *ap_ch = n->chesq;
    remove_ch_esq(n);
  }
  else {
    substitui_rec(n->esq, ap_ch);
    if (n->esq->nch == 0) 
      esquerda_vazio(n);
  }
}
		   
/* Remove a chave ch da árvore ch. */
int remove_rec(No23* n, int ch) {
  if (n->chesq == ch) {
    if (n->esq == NULL) 
      remove_ch_esq(n);
    else
      substitui_rec(n->cen, &n->chesq);
    return 1;
  }
  if (n->nch == 2 && n->chdir == ch) {
    if (n->esq == NULL) 
      remove_ch_dir(n);
    else
      substitui_rec(n->dir, &n->chdir);
    return 1;
  }

  if (n->esq == NULL) /* Não encontrou */
    return 0;

  if (ch < n->chesq) {
    if (!remove_rec (n->esq, ch)) 
      return 0;
    if (n->esq->nch == 0) 
      esquerda_vazio(n);
  }  
  else
    if (n->nch == 1 || ch < n->chdir) {
      if (!remove_rec(n->cen, ch))
	return 0;
      if (n->cen->nch == 0)
	central_vazio(n);
    }
    else {
      if (remove_rec(n->dir, ch))
	return 0;
      if (n->dir->nch == 0)
	direita_vazio(n);
    }
  return 1;
} 


/* Remove a chave ch da árvore *apn. Retorna 0 caso a chave não 
   tenha sido encontrada. */
int remove_ch(No23** apn, int ch) {
  if (*apn == NULL)
    return 0;
  if (!remove_rec(*apn, ch))
    return 0;

  if ((*apn)->nch == 0) {
    No23* r = *apn;
    *apn = (*apn)->esq;
    free(r);
  }
  return 1;
}


/****************************** Inserção **************************/


/* Insere ch e dir no nó n. Se o nó "explodir" retorna a chave
   central em *rch e o novo nó em *apr.                 
   Não testa repetição de chaves.                                 */
void insere_no(No23* n, int ch, No23* dir, int *rch, No23** rdir) {
  if (n->nch == 1) {
    if (ch < n->chesq) {
      n->dir = n->cen;      
      n->chdir = n->chesq;
      n->cen = dir;
      n->chesq = ch;
    }
    else {
      n->dir = dir;      
      n->chdir = ch;
    }
    n->nch = 2;
    *rdir = NULL; 
  }
  else {
    if (ch < n->chesq) {
      *rch = n->chesq;
      *rdir = no1(n->cen, n->chdir, n->dir);
      n->chesq = ch;
      n->cen = dir;
    }
    else if (ch < n->chdir) {
      *rch = ch;
      *rdir = no1(dir, n->chdir, n->dir);
    }
    else {
      *rch = n->chdir; 
      *rdir = no1(n->dir, ch, dir); 
    }
    n->nch = 1;
  }
}

/* Insere ch na árvore cuja raiz é n. Se a raiz n "explodir" retorna a
   chave central em *rch e o novo nó em *apr. Retorna 0 se a chave ch 
   já estiver na árvore */
int insere_rec(No23* n, int ch, int *rch, No23** rdir) {
  if (ch == n->chesq ||
      (n->nch == 2 && ch == n->chdir))
    return 0;

  if (n->esq == NULL) {
    insere_no(n, ch, NULL, rch, rdir);
    return 1;
  }

  int res;
  
  if (ch < n->chesq) 
    res = insere_rec (n->esq, ch, rch, rdir);
  else
    if (n->nch == 1 || ch < n->chdir)
      res = insere_rec(n->cen, ch, rch, rdir);
    else
      res = insere_rec(n->dir, ch, rch, rdir);

  if (res == 0)
    return 0;
  
  if (*rdir) 
    insere_no(n, *rch, *rdir, rch, rdir);

  return 1;
}

/* Insere ch na árvore cuja raiz é *apn. Retorna 0 se a chave ch 
   já estiver na árvore */
int insere (No23** apn, int ch) {
  if (*apn == NULL) {
    *apn = folha1(ch);
    return 1;
  }
  No23* apr;
  int rch;
  
  if (!insere_rec(*apn, ch, &rch, &apr))
    return 0;

  if (apr != NULL)
    *apn = no1(*apn, rch, apr);
  
  return 1;
}


/* arv é variável global */
int main() {
  /*  arv = exemplo();
      imprime(arv);  */

  char c;
  int i;

  arv = NULL;  
  printf("\n> ");

  while (scanf("%c %d", &c, &i) != EOF) {
    if (c == 'i') {
      insere(&arv, i);
      imprime(arv);
    }
    else if (c == 'r')
      remove_ch(&arv, i);
    printf("\n> ");
  }

  return 0;
}