#include <iostream>

typedef int infotyp;


class avlBaum
{ private:
    infotyp info;
    int hoehe;
    avlBaum *LS, *RS;

    int hoehe_avl();
    avlBaum* RR(avlBaum *W);
    avlBaum* RL(avlBaum *W);
    avlBaum* DRR(avlBaum *W);
    avlBaum* DRL(avlBaum *W);
    int balance();
    avlBaum* rotiere ();
    avlBaum* loesche_partner(infotyp &partnerinfo);

  public:
    avlBaum()
    { 
    }
    avlBaum* suchen(infotyp was);
    avlBaum* einfuegen(infotyp was);
    avlBaum* loeschen(infotyp was);
    void preorder();
    void inorder();
    void postorder();
    void zeige();
};


int avlBaum::hoehe_avl()      // Gibt die H'o'he des (Teil)baums zurueck
{ if (this == NULL) return 0;
  int hl, hr;
  if (this->LS == NULL) hl = 0;
     else hl = this->LS->hoehe;
  if (this->RS == NULL) hr = 0;
     else hr = this->RS->hoehe;
  if (hl > hr)                // liefere das Maximum der linken und rechten Hoehe
     return (1+hl);
  else
     return (1+hr);       
}


// die folgenden 4 Methoden sind eine exakte Umsetzung der Bildchen im Skript S. 29
avlBaum* avlBaum::RR (avlBaum *W)   // Rotation Rechts
{ avlBaum *B = W->LS;
  W->LS = B->RS;
  B->RS = W;
  W->hoehe = W->hoehe_avl();
  B->hoehe = B->hoehe_avl();
  return B;    // gib einen Pointer auf die neue Wurzel zurueck
}


avlBaum* avlBaum::RL (avlBaum *W)   // Rotation links
{ avlBaum *B = W->RS;
  W->RS = B->LS;
  B->LS = W;
  W->hoehe = W->hoehe_avl();
  B->hoehe = B->hoehe_avl();
  return B;
}

avlBaum* avlBaum::DRR (avlBaum *W)  // Doppelrotation rechts
{ avlBaum *B = W->LS,
          *C = W->LS->RS;
  W->LS = C->RS;
  B->RS = C->LS;
  C->LS = B;
  C->RS = W;
  B->hoehe = B->hoehe_avl();
  W->hoehe = W->hoehe_avl();
  C->hoehe = C->hoehe_avl();
  return C;
}

avlBaum* avlBaum::DRL (avlBaum *W)  // Doppelrotation links
{ avlBaum *B = W->RS,
          *C = W->RS->LS;
  W->RS = C->LS;
  B->LS = C->RS;
  C->RS = B;
  C->LS = W;
  B->hoehe = B->hoehe_avl();
  W->hoehe = W->hoehe_avl();
  C->hoehe = C->hoehe_avl();
  return C;
}

int avlBaum::balance()              // Gib den Unterschiede der Hoehe
{ if (this == NULL) return 0;       // links und rechts zur'u'ck
  return (LS->hoehe_avl()-RS->hoehe_avl());
}


avlBaum* avlBaum::rotiere ()     // Findet heraus, welcher der vier
{ int bal;                       // Rotationstypen angebracht ist, und
                                 // f'u'hrt diese Rotation durch.
  bal = balance();  // Hoehenunterschied ermitteln
  switch (bal)
  { case 0 :
    case 1 :
    case -1: hoehe = hoehe_avl();
             return this;        // keine Rotation n'o'tig
    case 2 : if (LS->LS->hoehe_avl() >= LS->RS->hoehe_avl())//Baum ist links tiefer
                return RR(this);
             else
                return DRR(this);
    case -2 : if (RS->RS->hoehe_avl() >= RS->LS->hoehe_avl())//Baum ist rechts tiefer
                return RL(this);
             else
                return DRL(this);
    default : //darf nicht vorkommen
              cout <<"\n\nFehler!!! Kein AVL-Baum!!!\n\n";
              return NULL;            
  }
}


avlBaum* avlBaum::suchen (infotyp was) // nach einem Element suchen
{ avlBaum *wo=this;  // Wurzel
  while (wo != NULL)
  { if (wo->info == was) break;
    if (wo->info < was ) wo = wo->RS;
       else wo = wo->LS;
  }
  return wo;
}

avlBaum* avlBaum::einfuegen(infotyp was)
{ if (this == NULL)
  { avlBaum *W = new avlBaum;
    W->info = was;
    W->RS  = NULL;
    W->LS = NULL;
    W->hoehe = 1;
    return W;
  }
  if (info == was) return this;
  if (info > was ) LS = LS->einfuegen (was);
     else RS = RS->einfuegen (was);
  int b = balance();
  if ( b==2 || b == -2) return rotiere();
  hoehe = hoehe_avl();
  return this;
}


avlBaum* avlBaum::loesche_partner(infotyp &partnerinfo)
{ if (RS == NULL)
  { partnerinfo = info;
    return LS;
  }
  RS = RS->loesche_partner(partnerinfo);
  int b = balance();
  if ( b==2) return rotiere();
  hoehe = hoehe_avl();
  return this;
}

avlBaum* avlBaum::loeschen(infotyp was)
{ // leerer Baum:
  if (this == NULL) return NULL;
  // Baum ist nicht leer; Loeschknoten noch nicht gefunden
  if (info != was )
  { if (info > was)
      LS = LS->loeschen (was);
    else
      RS =RS->loeschen (was);
    int b = balance();
    if ( b==2 || b == -2) return rotiere();
    hoehe = hoehe_avl();
    return this;
  }
  // Loeschknoten gefunden:
  int grad = 0;
  if (LS != NULL) grad++;
  if (RS != NULL) grad++;
  switch (grad)
  { case 0:   return NULL;
    case 1:   if (LS != NULL)
                  return LS;
              else
                  return RS;
    case 2:   infotyp i;
              LS = LS->loesche_partner(i);
              info = i;
              hoehe = hoehe_avl();
              return this;
   }
  return this; 
}


void avlBaum::inorder()       // Baum ausgeben in Vorordnung
{ if (this==NULL) return;
  LS->inorder();
  cout << info<<"  Hoehe: " <<hoehe<< endl;
  RS->inorder();
}


void avlBaum::preorder()      // Baum ausgeben in Zwischenordnung
{ if (this==NULL) return;
  cout << info<<"  Hoehe: " <<hoehe<< endl;
  LS->preorder();
  RS->preorder();
}

void avlBaum::postorder()     // Baum ausgeben in Nachordnung
{ if (this==NULL) return;
  LS->postorder();
  LS->postorder();
  cout << info<<"  Hoehe: " <<hoehe<< endl;
}


char menu()                   // Benutzerinterface
{ char was;
  cout <<"\n\nAktion:\n";
  cout <<"\ne: Einfuegen";
  cout <<"\nl: Loeschen";
  cout <<"\ns: Suchen";
  cout <<"\na: Ausgeben";
  cout <<"\nv: Programm verlassen\n";
  cout <<"-> "; cin  >> was;
  return was;
}


int main(void)
{ int n;
  avlBaum *W=NULL;
  int weiter = 1;
  do
  { switch (menu())
    { case 'e' :  cout <<"\n Einfuegen: ";
                  cin >> n;
                  W = W->einfuegen(n);
                  break;
      case 'l' :  cout <<"\n Loeschen: ";
                  cin >> n;
                  W = W->loeschen(n);
                  break;
      case 's' :  cout <<"\n Suchen: ";
                  cin >> n;
                  if (W->suchen(n)== NULL)
                      cout<<"\n"<<n<<" ist nicht vorhanden\n";
                  else
                     cout<<"\n"<<n<<" ist vorhanden\n";
                  break;
      case 'a' :  if (W==NULL)
                    cout << "\n Der Baum ist leer \n";
                  else
                  { cout << "\n Der Baum in Inorder: \n";
                    W->inorder();
                    cout <<"\n\n.. und in Preorder:\n";
                    W->preorder();
                  }  
                  break;
      case 'v' :  cout << "Programm wird verlassen.\n";
                  return 0;
      default : weiter = 0;
    }
  } while  (weiter);
  cin >> n;
  return 0;
}