#include <iostream>
#include <iomanip>
using namespace std;

class slownik
{
   struct wezel
    {
        wezel * p, * left, * right;
        int  bf,key;
        string s,ang;
    };
  public:

    wezel * root;  // korzeñ drzewa
    int count;       // liczba wêz³ów

// **********************************************
// *** Definicje funkcji sk³adowych klasy AVL ***
// **********************************************

// Konstruktor klasy AVL
//----------------------

slownik()
{
  root = NULL;
  count = 0;
}

// Destruktor klasy AVL
//---------------------

~slownik()
{
  while(root) delete(remove(root));
}

// Rotacja RR
//-----------

wezel * rotationRR(wezel * A)
{
  wezel * B = A->right, * P = A->p;

  A->right = B->left;
  if(A->right) A->right->p = A;
  B->left = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == -1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = -1; B->bf = 1;
  }
  return B;
}

// Rotacja LL
//-----------

wezel * rotationLL(wezel * A)
{
  wezel * B = A->left, * P = A->p;

  A->left = B->right;
  if(A->left) A->left->p = A;
  B->right = A;
  B->p = P;
  A->p = B;
  if(P)
  {
    if(P->left == A) P->left = B; else P->right = B;
  }
  else root = B;

  if(B->bf == 1)
  {
    A->bf = B->bf = 0;
  }
  else
  {
    A->bf = 1; B->bf = -1;
  }

  return B;
}

// Rotacja RL
//-----------

wezel * rotationRL(wezel * A)
{
  wezel * B = A->right, * C = B->left, * P = A->p;

  B->left = C->right;
  if(B->left) B->left->p = B;
  A->right = C->left;
  if(A->right) A->right->p = A;
  C->left = A;
  C->right = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf == -1) ?  1 : 0;
  B->bf = (C->bf ==  1) ? -1 : 0;
  C->bf = 0;

  return C;
}

// Rotacja LR
//-----------

wezel * rotationLR(wezel * A)
{
  wezel * B = A->left, * C = B->right, * P = A->p;

  B->right = C->left;
  if(B->right) B->right->p = B;
  A->left = C->right;
  if(A->left) A->left->p = A;
  C->right = A;
  C->left = B;
  A->p = B->p = C;
  C->p = P;
  if(P)
  {
    if(P->left == A) P->left = C; else P->right = C;
  }
  else root = C;

  A->bf = (C->bf ==  1) ? -1 : 0;
  B->bf = (C->bf == -1) ?  1 : 0;
  C->bf = 0;

  return C;
}

// Wstawia element do struktury AVL
//---------------------------------

bool insert(wezel * n)
{
  wezel * x = root, * y, * z;

  y = n->left = n->right = NULL;
  n->bf = 0;

  while(x)
  {
    if(x->s.compare(n->s) == 0)
    {
      delete n;
      return false;
    }
    y = x;
    x = (n->s.compare(x->s)<0) ? x->left : x->right;
  }

  count++;

  if(!(n->p = y))
  {
    root = n;
    return true;
  }
  if(n->s.compare(y->s) < 0) y->left = n; else y->right = n;
  if(y->bf)
  {
    y->bf = 0;
    return true;
  }
  y->bf = (y->left == n) ? 1 : -1;
  z = y->p;
  while(z)
  {
    if(z->bf) break;
    z->bf = (z->left == y) ? 1 : -1;
    y = z; z = z->p;
  }

  if(!z) return true;

  if(z->bf == 1)
  {
    if(z->right == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == -1) rotationLR(z); else rotationLL(z);
    return true;
  }
  else
  {
    if(z->left == y)
    {
      z->bf = 0;
      return true;
    }
    if(y->bf == 1) rotationRL(z); else rotationRR(z);
    return true;
  }
}

// Wyszukuje element wg wartoœci klucza
//-------------------------------------

wezel * search(string slowo)
{
  wezel * x = root;

  while((x) && (x->s.compare(slowo) != 0))
    x = (x->s.compare(slowo) >0) ? x->left : x->right;

  return x;
}

wezel * minNode(wezel * x)
{
  while(x->left) x = x->left;
  return x;
}

wezel * maxNode(wezel * x)
{
  while(x->right) x = x->right;
  return x;
}

// Zwraca wêze³ poprzednika
//-------------------------

wezel * pred(wezel * x)
{
  if(x->left) return maxNode(x->left);

  wezel * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->right != y));

  return x;
}

// Zwraca wêze³ nastêpnika
//------------------------

wezel * succ(wezel * x)
{
  if(x->right) return minNode(x->right);

  wezel * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->left != y));

  return x;
}

// Usuwa element x ze struktury AVL. Zwraca usuniêty wêze³
//--------------------------------------------------------

wezel * remove(wezel * x)
{
  wezel * t, * y, * z;
  bool nest;

  if((x->left) && (x->right))
  {
    y = remove(pred(x));
    count++;
    nest = false;
  }
  else
  {
    if(x->left)
    {
      y = x->left; x->left = NULL;
    }
    else
    {
      y = x->right; x->right = NULL;
    }
    x->bf = 0;
    nest = true;
  }

  if(y)
  {
    y->p = x->p;
    if(y->left  = x->left)  y->left->p  = y;
    if(y->right = x->right) y->right->p = y;
    y->bf = x->bf;
  }

  if(x->p)
  {
    if(x->p->left == x) x->p->left = y; else x->p->right = y;
  }
  else root = y;

  if(nest)
  {
    z = y;
    y = x->p;
    while(y)
    {
      if(!(y->bf))
      {

// Przypadek nr 1

        y->bf = (y->left == z) ? -1 : 1;
        break;
      }
      else
      {
        if(((y->bf ==  1) && (y->left  == z)) || ((y->bf == -1) && (y->right == z)))
        {

// Przypadek nr 2

          y->bf = 0;
          z = y; y = y->p;
        }
        else
        {
          t = (y->left == z) ? y->right : y->left;
          if(!(t->bf))
          {

// Przypadek 3A

            if(y->bf == 1) rotationLL(y); else rotationRR(y);
            break;
          }
          else if(y->bf == t->bf)
          {

// Przypadek 3B

            if(y->bf == 1) rotationLL(y); else rotationRR(y);
            z = t; y = t->p;
          }
          else
          {

// Przypadek 3C

            if(y->bf == 1) rotationLR(y); else rotationRL(y);
            z = y->p; y = z->p;
          }
        }
      }
    }
  }
  count--;
  return x;
}

// Przechodzi przez drzewo AVL metod¹ preorder
//--------------------------------------------

void preorder(wezel * x)
{
  if(x)
  {
    cout << x->s <<" "<< x->ang << endl;  // tutaj przetwarzamy bie¿¹cy wêze³
    preorder(x->left);
    preorder(x->right);
  }
}

// Przechodzi przez drzewo AVL metod¹ inorder
//-------------------------------------------

void inorder(wezel * x)
{
  if(x)
  {
    inorder(x->left);
    cout << x->s <<" "<< x->ang << endl;  // tutaj przetwarzamy bie¿¹cy wêze³
    inorder(x->right);
  }
}

// Przechodzi przez drzewo AVL metod¹ postorder
//---------------------------------------------

void postorder(wezel * x)
{
  if(x)
  {
    postorder(x->left);
    postorder(x->right);
    cout << x->s <<" "<< x->ang <<endl;  // tutaj przetwarzamy bie¿¹cy wêze³
  }
}

// Przechodzi przez drzewo wypisuj¹c zawartoœæ wêz³ów
void walk(wezel * x)
{
  cout << x->s << " : bf = " << setw(2) << x->bf << " : Left-> ";
  if(x->left) cout << setw(3) << x->left->s;
  else        cout << "NIL";
  cout << ", Right-> ";
  if(x->right) cout << setw(3) << x->right->s;
  else         cout << "NIL";
  cout << " : parent -> ";
  if(x->p) cout << setw(3) << x->p->s;
  else     cout << "NIL";
  cout << endl;
  if(x->left)  walk(x->left);
  if(x->right) walk(x->right);
}

int wypisz(slownik *T)
{
    int z;
   z=T->coutAVLcount();
   if (z==0)
    cout<<"Slownik jest pusty"<<endl;
  else
    T->walk(T->root);

return 0;
}
// Wypisuje do cout liczbê wêz³ów drzewa AVL
//------------------------------------------

int coutAVLcount()
{
  return count;
}

void add(slownik * T)
{
  cout << "Dodawanie nowych slow\n"
          "-------------------------------------\n\n";
  cout << "Podaj liczbe slow do dodania."<<endl;

  int i,n;

  wezel * x;

  cin >> n;
  for(i = 0; i < n; i++)
  {
    x = new wezel;
    cout<<"Podaj slowo"<<endl;
    cin >> x->s;
    cout<<"Podaj tlumaczenie \n"<<"Gdy go brak wstaw '-'"<<endl;
    cin>>x->ang;
    T->insert(x);
  }

  cout << endl;
  T->walk(T->root);

}

// Usuwa wêze³ o zadanym kluczu
//-----------------------------

void del(slownik * T)
{
  cout << "Usuwanie wezla drzewa AVL o zadanym kluczu\n"
          "------------------------------------------\n\n";

  wezel * x;
  string key;
  cout << "Podaj slowo do usuniecia : "; cin >> key;

  x = T->search(key);

  if(x)
  {
    delete T->remove(x);
    cout << endl;
    if(T->root) T->walk(T->root);
  }
  else cout << "\nBrak takiego slowa\n";
}

void szukaj(slownik * T)
{
  cout << "Sprawdzenie obecnosci slowa w slowniku\n"
          "--------------------------------------------------------\n\n"
          "Podaj slowo : "<<endl;

  string slowo;
  cin >> slowo;
  if(T->search(slowo)) cout << "Slowo znalezione."<<endl<<T->search(slowo)->s<<" - "<<T->search(slowo)->ang;
  else               cout << "Nie znaleziono takiego slowa\n";
}

// Przechodzi przez drzewo algorytmem preorder
void preorder(slownik * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem preorder\n"
          "--------------------------------------------\n\n";
  T->preorder(T->root);
}

// Przechodzi przez drzewo algorytmem inorder
void inorder(slownik * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem inorder\n"
          "-------------------------------------------\n\n";
  T->inorder(T->root);
}

// Przechodzi przez drzewo algorytmem postorder
void postorder(slownik * T)
{
  cout << "Przechodzenie drzewa AVL algorytmem postorder\n"
          "---------------------------------------------\n\n";
  T->postorder(T->root);
}
};

main()
{
  slownik * T = new slownik();
  int choice;
  slownik a;
  do
  {
    cout << "Slownik MENU\n"
            "==============================\n\n"
            "Wybor Funkcja\n"
            "-----------------------------\n"
            " [0]  Koniec\n"
            " [1]  Dodaj slowo\n"
            " [2]  Usun slowo\n"
            " [3]  Znajdz slowo\n"
            " [4]  Wyswietl drzewo\n"
            " [5]  pusto\n"
            " [6]  pusto\n"
            " [7]  Preorder\n"
            " [8]  Inorder\n"
            " [9]  Postorder\n"
            "-----------------------------\n"
            "Twoj wybor : ";
    cin >> choice;

    switch(choice)
    {
      case 1 : a.add(T);       break;
      case 2 : a.del(T);       break;
      case 3 : a.szukaj(T);     break;
      case 4 : a.wypisz(T);      break;
      case 5 :     break;
      case 6 :       break;
      case 7 : a.preorder(T);  break;
      case 8 : a.inorder(T);   break;
      case 9 : a.postorder(T); break;
    }
    if((choice >= 1) && (choice <= 9))
    {
      cout << endl;
    }

  } while(choice);

  delete T;
}