/*
 * Á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--;
}

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


/* Nó à esquerda está vazio. Arruma a árvore. */
void esquerda_vazio (No23* n) {
}

/* Nó central está vazio. Arruma a árvore. */
void central_vazio (No23* n) {
}

/* Nó central está vazio. Arruma a árvore. */
void direita_vazio (No23* n) {
}

/* Substitui a chave posicionada em *ap_ch pela chave
   mais à esquerda da árvore n. */
void substitui_rec(No23* n, int* ap_ch) {
}
		   
/* Remove a chave ch da árvore ch. */
int remove_rec(No23* n, int ch) {
  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) {
}

/* 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) {
  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;
}