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

#define MAXCMD 100 //Maximalni delka prikazu

//Uzel stromu: klic, vyvazenost, levy a pravy syn
typedef struct tag_NODE { int key, bal; struct tag_NODE *left, *right; } NODE;

//Vypis stromu TREE, POS je horizontalni pozice na obrazovce
void write_tree(NODE *tree, int pos)
{
  int i = 3 * pos;

  if(tree)
  {
    write_tree(tree->right, pos + 1); //Pravy podstrom
    while(i) putchar(' '), i--; //Odsazeni
    printf("%d\n", tree->key); //Vypis klice
    write_tree(tree->left, pos + 1); //Levy podstrom
  }
}


//Jednoducha rotace doleva
void tree_rot_left(NODE **p)   /*                         */
{                              /*     A            B      */
  NODE *a = *p;                /*    / \          / \     */
  NODE *b = a->right;          /*   #   B    =>  A   #    */
                               /*      / \      / \  @    */
  a->right = b->left;          /*      #  #    #   #      */
  b->left = a;                 /*         @               */
  *p = b;                      /*                         */

  a->bal = b->bal ? 0 :  1; /* Pokud byl B vyvazeny, nebude */
  b->bal = b->bal ? 0 : -1; /* novy strom vyvazen dokonale  */
}


//Jednoducha rotace doprava
void tree_rot_right(NODE **p)  /*                         */
{                              /*      B           A      */
  NODE *b = *p;                /*     / \         / \     */
  NODE *a = b->left;           /*    A   #   =>  #   B    */
                               /*   / \          @  / \   */
  b->left = a->right;          /*  #   #           #   #  */
  a->right = b;                /*  @                      */
  *p = a;                      /*                         */

  b->bal = a->bal ? 0 : -1; /* Pokud byl A vyvazeny, nebude */
  a->bal = a->bal ? 0 :  1; /* novy strom vyvazen dokonale  */
}


//Dvojita rotace doleva
void tree_drot_left(NODE **p)  /*                           */
{                              /*     A             B       */
  NODE *a = *p;                /*    / \          /   \     */
  NODE *c = a->right;          /*   #   C    =>  A     C    */
  NODE *b = c->left;           /*   #  / \      / \   / \   */
                               /*     B   #    #   # #   #  */
  c->left = b->right;          /*    / \  #    #   @     #  */
  a->right = b->left;          /*   #   #                   */
  b->left = a;                 /*   @                       */
  b->right = c;
  *p = b;

  switch(b->bal) //Vyvazeni A a C je urceno vyvazenim B
  {
    case -1: a->bal =  0; c->bal = 1; break;
    case  0: a->bal =  0; c->bal = 0; break;
    case  1: a->bal = -1; c->bal = 0; break;
  }
  b->bal = 0;
}


//Dvojita rotace doprava
void tree_drot_right(NODE **p) /*                          */
{                              /*      C            B       */
  NODE *c = *p;                /*     / \         /   \     */
  NODE *a = c->left;           /*    A   #   =>  A     C    */
  NODE *b = a->right;          /*   / \  #      / \   / \   */
                               /*  #   B       #   # #   #  */
  a->right = b->left;          /*  #  / \      #   @     #  */
  c->left = b->right;          /*    #   #                  */
  b->left = a;                 /*    @                      */
  b->right = c;
  *p = b;

  switch(b->bal) //Vyvazeni A a C je urceno vyvazenim B
  {
    case -1: a->bal =  0; c->bal = 1; break;
    case  0: a->bal =  0; c->bal = 0; break;
    case  1: a->bal = -1; c->bal = 0; break;
  }
  b->bal = 0;
}


//Provede vyvazani vrcholu (zadaneho adresou ukazatele), je-li to potreba
void tree_balance(NODE **p)
{
  if((*p)->bal == 2) //Pokud se narusilo vyvazeni (pravy podstrom je vetsi)
  {
    if(((*p)->right)->bal == -1) /* Podle vyvazeni praveho podstromu se rozhodneme,*/
      tree_drot_left(p);         /* zda provest jednoduchou nebo dvojitou rotaci   */
    else
      tree_rot_left(p);
  }

  if((*p)->bal == -2) //Pokud se narusilo vyvazeni (levy podstrom je vetsi)
  {
    if(((*p)->left)->bal == 1) /* Podle vyvazeni leveho podstromu se rozhodneme,*/
      tree_drot_right(p);      /* zda provest jednoduchou nebo dvojitou rotaci  */
    else
      tree_rot_right(p);
  }
}


//Prida novy klic X do stromu, P je adresa ukazatele na koren
//Vraci, jak se zmenila vyska podstromu (-1, 0, nebo 1)
int tree_add(int x, NODE **p)
{
  int change; //Zmena vyvazeni (-1, 0, 1)

  if(!*p) //Je-li pointer na uzel NULL, vytvorime novy uzel
  {
     *p = (NODE*)malloc(sizeof(NODE)); //Novy uzel
    (*p)->key = x; //Ulozime hodnotu klice
    (*p)->left = NULL;  /* Zatim nema   */
    (*p)->right = NULL; /* zadneho syna */
    (*p)->bal = 0; //List je vyvazeny
    return 1; //Vyska podstromu se zvetsila
  }

  // Hodnota se porovnava s klicem, je-li mensi, jdeme doleva, jinak doprava
  if(x < (*p)->key)
    change = -tree_add(x, &(*p)->left);
  else
    change = tree_add(x, &(*p)->right);

  (*p)->bal += change; //Upravime vyvazeni, pokud se zmenila vyska podstromu
  tree_balance(p); //Provedeme pripadne rotace pro vyvazeni vrcholu

  /* Vyska se zmenila jen pokud se zmenila vyska podstromu */
  /* a oba podstromy predtim mely stejnou vysku            */
  return (change && (*p)->bal) ? 1 : 0;
}


//Vyhleda nejpravejsi vrchol v podstromu, P je adresa ukazatele na koren
//Vraci, jak se zmenila vyska podstromu (-1, 0, nebo 1) a v P_LEAF nalezeny vrchol
int tree_find_max(NODE **p, NODE **p_max)
{
  int change; //Zmena vyvazeni (-1, 0, 1)

  if((*p)->right) //Ma-li vrchol praveho syna
  {
    change = tree_find_max(&(*p)->right, p_max); //Jdeme dal doprava
    (*p)->bal += change; //Upravime vyvazeni, pokud se zmenila vyska podstromu
    tree_balance(p); //Provedeme pripadne rotace pro vyvazeni vrcholu

    /* Vyska se zmenila jen pokud se zmenila vyska podstromu a vysky   */
    /* podstromu jsou stejne (diky snizeni jednoho z nich nebo rotaci) */
    return (change && !(*p)->bal) ? -1 : 0;
  }
  else
  {
    *p_max = *p; //Vracime nalezeny vrchol
    *p = (*p)->left; //Vrchol nahradime levym synem
    return -1; //Vyska podstromu se snizila
  }
}


//Odstrani ze stromu prvek s klicem X, P je adresa ukazatele na koren
int tree_del(int x, NODE **p)
{
  int change; //Zmena vyvazeni (-1, 0, 1)
  NODE *px = *p; //Vrchol stromu, kde jsme nasli X
  NODE *q; //Nejpravejsi vrchol v levem podstromu

  if(!px) //Pro pripad, ze by klic ve strome nebyl
    return 0;

  if(px->key == x) //Pokud jsme klic nasli
  {
    if(!px->left || !px->right) //Pokud ma vrchol nejvyse jednoho syna
    {
      *p = px->left ? px->left : px->right; /* Vrchol odstranime, misto */
      free(px);                             /* nej vlozime jeho syna    */
      return -1; //Podstrom se snizil
    }

    change = -tree_find_max(&px->left, &q); //Najdeme nejpravejsi vrchol v levem podstromu
    q->left = px->left;   /* Prepojime na nej syny  */
    q->right = px->right; /* odstranovaneho vrcholu */
    q->bal = px->bal; //Zkopirujeme vyvazeni odstranovaneho vrcholu
    *p = q; //Nasmerujeme ukazatel na novy vrchol
    free(px); //A nakonec odstranovany vrchol opravdu uvolnime
  }
  else
  {
    // Hodnota se porovnava s klicem, je-li mensi, jdeme doleva, jinak doprava
    if(x < px->key)
      change = -tree_del(x, &px->left);
    else
      change = tree_del(x, &px->right);
  }
  
  (*p)->bal += change; //Upravime vyvazeni, pokud se zmenila vyska podstromu
  tree_balance(p); //Provedeme pripadne rotace pro vyvazeni vrcholu

  /* Vyska se zmenila jen pokud se zmenila vyska podstromu a vysky   */
  /* podstromu jsou stejne (diky snizeni jednoho z nich nebo rotaci) */
  return (change && !(*p)->bal) ? -1 : 0;
}


//Hledani klice X ve stromu s korenem TREE,
//vraci ukazatel na vrchol nebo NULL (prevek nebyl nalezen)
NODE *tree_search(int x, NODE *tree)
{
  while(tree && tree->key != x) /* Postupujeme, dokud mame kam (pointer */
  {                             /* neni nulovy) a hodnotu jsme nenasli  */
    if(x < tree->key)     /* Je-li hodnota mensi, */
      tree = tree->left;  /* jdeme doleva,        */
    else                  /* je-li vetsi,         */
      tree = tree->right; /* jdeme doprava        */
  }
  return tree; //Pokud jsme prvek nenasli, je TREE NULL
}


//-=<MAIN>=-
int main()
{
  int x; //Cislo pro pridani / odstraneni ze stromu
  NODE *tree = NULL; //Koren stromu (zatim prazdny)
  char cmd[MAXCMD] = "h"; //Prikaz uzivatele (na zacatku 'h': napoveda)

  while(cmd[0] != 'q') //Dokud jsme nedostali prikaz na ukonceni
  {
    switch(cmd[0]) //Prikaz se rozlisuje dle 1. znaku
    {
      case 'a': sscanf(cmd + 1, "%d", &x); tree_add(x, &tree); break; //Pridani klice
      case 'd': sscanf(cmd + 1, "%d", &x); tree_del(x, &tree); break; //Odebrani klice
      case 'h': puts("Commands: a - Add value, d - Delete Value, p - Print tree, q - Quit, h - Help"); break;
      case 'p': write_tree(tree, 0); //Vypis stromu
    }

    printf("> "); //Oznaceni, ze program chce vstup
    fgets(cmd, MAXCMD, stdin); //Nacteni radky ze vstupu (fgets kontroluje preteceni)
  }
  return 0;
}