/******************************  AVLBaum.java  ********************************/

import AlgoTools.IO;

/** Ein AVLBaum ist ein SuchBaum, bei dem alle Knoten ausgeglichen
 *  sind. Das heisst fuer jeden seiner Knoten unterscheiden sich
 *  die Hoehen seiner beiden Teilbaeume maximal um eins.
 */

public class AVLBaum extends SuchBaum {
  
  private class Status {                 // Innere Klasse zur Uebergabe eines
                                         // Status in der Rekursion
    private boolean unbalanciert;        // unbalanciert ist true, wenn beim
  }                                      // Einfuegen ein Sohn groesser geworden
                                         // ist.
                                         // simuliertes Call-by-Reference 
  
  public static void printAVLBaum(Baum b, int tiefe) {
    
    if (!b.empty()) {                    // Wenn Baum nicht leer:
      printAVLBaum(b.right(), tiefe+1);  // rechten Teilbaum ausgeben
      for (int i=0; i<tiefe; i++)        // entsprechend der Rekursions-
        IO.print("    ");                // tiefe einruecken
      IO.println(((VerweisBaum)b).wurzel);// Wurzel und Balance ausgeben
      printAVLBaum(b.left(), tiefe+1);   // linken Teilbaum ausgeben
    }
  }

  
  
  
  
  
  
  
  public boolean insert(Comparable x) {  // fuegt x in den AVLBaum ein: true,
                                         // wenn erfolgreich, sonst false.
                                         // Kapselt die Methode insertAVL
    return insertAVL(x, (AVLKnoten)wurzel, null, new Status());
  }
  
                                         // tatsaechliche rekursive Methode zum
                                         // Einfuegen
  private boolean insertAVL(Comparable x, AVLKnoten k, AVLKnoten v, Status s) {
    
    boolean eingefuegt;

    if (k == null) {                     // Unter einem Blatt:
                                         // Hier kann eingefuegt werden.
      if (v == null)                     // kein Vater:
        wurzel = new AVLKnoten(x);       // Einfuegen in der Wurzel
      else {                             // Vater vorhanden:
        if (x.compareTo(v.inhalt) < 0)   // Element mit Inhalt von Vater vergl.
          v.links = new AVLKnoten(x);    // und als entsprechend als linken oder
        else                             // rechten Sohn einfuegen
          v.rechts = new AVLKnoten(x);
        s.unbalanciert = true;           // Teilbaum wurde groesser
      }
      return true;                       // Einfuegen erfolgreich
    }
    
    else if (x.compareTo(k.inhalt) == 0) {  
                                         // Element schon im AVLBaum vorhanden
      return false;                      // Einfuegen nicht erfolgreich
    }
    
    else {                               
      if (x.compareTo(k.inhalt) < 0) {   // Element ist kleiner als Knoteninhalt
      
        eingefuegt = insertAVL(x, (AVLKnoten)k.links, k, s);
                                         // Setze Suche im linken Teilbaum fort
        
        if (s.unbalanciert) {            // Falls linker Teilbaum hoeher wurde

          if (k.balance == 1) {          // alte Unausgeglichenheit ausgeglichen
            k.balance = 0;               // => neue Balance = 0
            s.unbalanciert = false;      // Teilbaum ist jetzt ausgeglichen
          }
          
          else if (k.balance == 0)       // Noch keineRotation noetig
            k.balance = -1;              // Balance wird angeglichen
          
          else {                         // Balance wird angeglichen
            if (((AVLKnoten)k.links).balance == -1)
              rotateLL(k);
            else
              rotateLR(k);
            s.unbalanciert = false;      // Teilbaum ist danach ausgeglichen
          }
        }
      }
      
      else {                             // Element groesser als Knoteninhalt
        
        eingefuegt = insertAVL(x, (AVLKnoten)k.rechts, k, s);
                                         // Setze Suche im rechten Teilbaum fort
        
        if (s.unbalanciert) {            // Falls recht. Teilbaum groesser wurde
          if (k.balance == -1) {         // alte Unausgeglichenheit ausgeglichen
            k.balance = 0;               // => neue Balance = 0
            s.unbalanciert = false;      // Teilbaum ist jetzt ausgeglichen
          }
          else if (k.balance == 0)       // Noch keineRotation noetig
            k.balance = 1;               // Balance wird angeglichen

          else {                         // Balance wird angeglichen
            if (((AVLKnoten)k.rechts).balance == 1)
              rotateRR(k);
            else
              rotateRL(k);
            s.unbalanciert = false;      // Teilbaum ist danach ausgeglichen
          }
        }
      }
      return eingefuegt;                 // true, falls im linken oder rechten
    }                                    // Teilbaum eingefuegt, sonst false
  }

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  private void rotateLL(AVLKnoten k) {
  
    IO.println("LL-Rotation im Teilbaum mit Wurzel " + k.inhalt);

    AVLKnoten a1 = (AVLKnoten)k.links;   // Merke linken
    AVLKnoten a2 = (AVLKnoten)k.rechts;  // und rechten Teilbaum

                                         // Idee: Inhalt von a1 in die Wurzel k
    k.links = a1.links;                  // Setze neuen linken Sohn
    k.rechts = a1;                       // Setze neuen rechten Sohn
    a1.links = a1.rechts;                // Setze dessen linken und
    a1.rechts = a2;                      // rechten Sohn

    Object tmp = a1.inhalt;              // Ihnalt von k.rechts (==a1)
    a1.inhalt = k.inhalt;                // wird mit Wurzel k
    k.inhalt = tmp;                      // getauscht

    ((AVLKnoten)k.rechts).balance = 0;   // rechter teilbaum balanciert
    k.balance = 0;                       // Wurzel k balanciert
  }

  
  private void rotateLR(AVLKnoten k) {
  
    IO.println("LR-Rotation im Teilbaum mit Wurzel " + k.inhalt);

    AVLKnoten a1 = (AVLKnoten)k.links;   // Merke linken 
    AVLKnoten a2 = (AVLKnoten)a1.rechts; // und dessen rechten Teilbaum
    
                                         // Idee: Inhalt von a2 in die Wurzel k
    a1.rechts = a2.links;                // Setze Soehne von a2
    a2.links = a2.rechts;
    a2.rechts = k.rechts;
    k.rechts = a2;                       // a2 wird neuer rechter Sohn

    Object tmp = k.inhalt;               // Inhalt von k.rechts (==a2)
    k.inhalt = a2.inhalt;                // wird mit Wurzel k
    a2.inhalt = tmp;                     // getauscht

    ((AVLKnoten)k.links).balance = (a2.balance == 1) ? -1 : 0;
                                         // neue Balance fuer linken Sohn

    ((AVLKnoten)k.rechts).balance = (a2.balance == -1) ? 1 : 0;
                                         // neue Blance fuer rechten Sohn

    k.balance = 0;                       // Wurzel k ist ausgeglichen
  }

  
  
  
  
  
  
  
  
  
  private void rotateRR(AVLKnoten k) {
  
    IO.println("RR-Rotation im Teilbaum mit Wurzel " + k.inhalt);

    AVLKnoten a1 = (AVLKnoten)k.rechts;  // Merke rechten
    AVLKnoten a2 = (AVLKnoten)k.links;   // und linken Teilbaum

                                         // Idee: Inhalt von a1 in die Wurzel k
    k.rechts = a1.rechts;                // Setze neuen rechten Sohn
    k.links = a1;                        // Setze neuen linken Sohn
    a1.rechts = a1.links;                // Setze dessen rechten und
    a1.links = a2;                       // linken Sohn

    Object tmp = a1.inhalt;              // Ihnalt von k.links (==a1)
    a1.inhalt = k.inhalt;                // wird mit Wurzel k
    k.inhalt = tmp;                      // getauscht

    ((AVLKnoten)k.links).balance = 0;    // linker teilbaum balanciert
    k.balance = 0;                       // Wurzel k balanciert
  }

  
  private void rotateRL(AVLKnoten k) {
  
    IO.println("RL-Rotation im Teilbaum mit Wurzel " + k.inhalt);

    AVLKnoten a1 = (AVLKnoten)k.rechts;  // Merke rechten
    AVLKnoten a2 = (AVLKnoten)a1.links;  // und dessen linken Teilbaum

                                         // Idee: Inhalt von a1 in die Wurzel k
    a1.links = a2.rechts;                // Setze Soehne von a2
    a2.rechts = a2.links;
    a2.links = k.links;
    k.links = a2;                        // a2 wird neuer linker Sohn

    Object tmp = k.inhalt;               // Inhalt von k.links (==a2)
    k.inhalt = a2.inhalt;                // wird mit Wurzel k
    a2.inhalt = tmp;                     // getauscht

    ((AVLKnoten)k.rechts).balance = (a2.balance == -1) ? 1 : 0;
                                         // neue Blance fuer rechten Sohn

    ((AVLKnoten)k.links).balance = (a2.balance == 1) ? -1 : 0;
                                         // neue Blance fuer rechten Sohn
    
    k.balance = 0;                       // Wurzel k ist ausgeglichen
  }

  
  
  
  
  
  
  
  
    
  public boolean delete(Comparable x) {  // loescht x im AVLBaum: true, wenn
                                         // erfolgreich, sonst false
                                         // Kapselt die Methode deleteAVL
    return deleteAVL(x, (AVLKnoten)wurzel, null, new Status());
  }

                                         // tatsaechliche rekursive Methode zum
                                         // Loeschen
  private boolean deleteAVL(Comparable x, AVLKnoten k, AVLKnoten v, Status s) {
  
    boolean geloescht;                   // true, wenn geloescht wurde

    if (k == null)                       // Unterhalb eines Blattes:
      return false;                      // Element nicht gefunden, es wurde
                                         // nicht geloescht
    
    else if (x.compareTo(k.inhalt) < 0) {// Element x kleiner als Knoteninhalt
   
      geloescht = deleteAVL(x, (AVLKnoten)k.links, k, s);
                                         // Setze Suche im linken Teilbaum fort

      if (s.unbalanciert)                // Falls linker Teilbaum kleiner
        balance1(k, s);                  // geworden ist, gleiche Hoehe an
      
      return geloescht;                  // true, falls im linken Teilbaum
    }                                    // geloescht wurde
    
    else if (x.compareTo(k.inhalt) > 0) {// Element x groesser als Knoteninhalt
    
      geloescht = deleteAVL(x, (AVLKnoten)k.rechts, k, s);
                                         // Setze Suche im rechten Teilbaum fort
      
      if (s.unbalanciert)                // Falls rechter Teilbaum kleiner
        balance2(k, s);                  // geworden ist, gleiche Hoehe an
      
      return geloescht;                  // true, falls im rechten Teilbaum
    }                                    // geloescht wurde
    
    else {                               // Knoten k enthaelt Element x
                                         // Wenn k keine Soehne hat
      if (k.rechts == null && k.links == null) {

        if (v == null)                   // Hat k keinen Vater, ist k die Wurzel   
          wurzel = null;                 // Setze Wurzel auf null
        else {                           // k hat Vater

          if (x.compareTo(v.inhalt) < 0) // Ist k linker Sohn,
            v.links = null;              // loesche linken Sohn von Vater v
          else                           // Ist k rechter Sohn,
            v.rechts = null;             // loesche rechten Sohn von v
          s.unbalanciert = true;         // Hoehe hat sich geaendert
        }
      }
      


      
      else if (k.rechts == null) {       // Wenn k nur linken Sohn 
        if (v != null) {                 // und einen Vater hat
          if (x.compareTo(v.inhalt) < 0) // setze ihn als neuen linken oder
            v.links = k.links;           // rechten Sohn des Vaters
          else                             
            v.rechts = k.links;

          s.unbalanciert = true;         // Hoehe hat sich geaendert
      	}
        else                             // Wenn k keinen Vater hat war k Wurzel
          wurzel = k.links;              // Dann wird linker Sohn neue Wurzel
      }
      else if (k.links == null) {        // Wenn k nur rechten Sohn
        if (v != null) {                 // und einen Vater hat,
          if (x.compareTo(v.inhalt) < 0) // setze ihn als neuen linken oder
            v.links = k.rechts;          // rechten Sohn des Vaters
          else 
            v.rechts = k.rechts;
      	
          s.unbalanciert = true;         // Hoehe hat sich geaendert
      	}
        else                             // Wenn k keinen Vater hat war k Wurzel
          wurzel = k.rechts;             // Dann wird rechter Sohn neue Wurzel
      }
      else {                             // k hat zwei Soehne
                                         // rufe im li. Sohn del() auf
        k.inhalt = del((AVLKnoten)k.links, k, s);
        if (s.unbalanciert)              // Falls linker Teilbaum kleiner
          balance1(k, s);                // geworden ist, gleiche Hoehe an
      }
      return true;                       // es wurde geloescht
    } 
  }                                     
  
  
  private Comparable del(AVLKnoten k, AVLKnoten v, Status s) {
                                         // Suche Ersatz fuer gel. Element
    Comparable ersatz;                   // Ersatz-Element
    
    if (k.rechts != null) {              // Wenn rechter Sohn vorhanden, 
                                         //  suche dort weiter und loesche
      ersatz = del((AVLKnoten)k.rechts, k, s); 
      if (s.unbalanciert)                // Falls rechter Teilbaum kleiner
        balance2(k, s);                  // geworden ist, gleiche Hoehe an
    }
    else {                               // kein rechter Sohn von k vorhanden

      ersatz = (Comparable)k.inhalt;     // Cast, da k.ihnalt vom Typ Object            

      if (((Comparable)k.inhalt).compareTo(v.inhalt) > 0) 
        v.rechts = k.links;              // setze linken Sohn von k an die
      else                               // Stelle von k
        v.links = k.links;
      s.unbalanciert = true;             // Hoehe hat sich geaendert
    }
    return ersatz;                       // Gib Ersatz-Element zurueck
  }
  private void balance1(AVLKnoten k, Status s) {
                                         // Unbalance, weil linker Ast kuerzer
    switch (k.balance) {
      case -1:                           // Balance geaendert, Hoehe nicht
        k.balance = 0;                   // ausgeglichen 
        break;                            
      case 0:                            // Ausgeglichen
        k.balance = 1;                   
        s.unbalanciert = false;
        break;
      case 1:                            // Ausgleichen (Rotation) notwendig
        int b = ((AVLKnoten)k.rechts).balance;  // Balance des linken Sohnes
        if (b >= 0) {
          rotateRR(k);               
          if (b == 0) {
            k.balance = -1;              // Gleiche Balancen an
            ((AVLKnoten)k.links).balance = 1;
            s.unbalanciert = false;
          }
        }
        else
          rotateRL(k);
    }
  }

  
  private void balance2(AVLKnoten k, Status s) {
                                         // Unbalance, weil rechter Ast kuerzer
    switch (k.balance) {
      case 1:                            // Balance geaendert, Hoehe nicht
        k.balance = 0;                   // ausgeglichen
        break;
      case 0:
        k.balance = -1;                  // Ausgeglichen
        s.unbalanciert = false;
        break;
      case -1:                           // Ausgleichen (Rotation) notwendig
        int b = ((AVLKnoten)k.links).balance; // Balance des rechten Sohnes
        if (b <= 0) {
          rotateLL(k);
          if (b == 0) {
            k.balance = 1;               // Gleiche Balancen an
            ((AVLKnoten)k.rechts).balance = -1;
            s.unbalanciert = false;
          }
        }
        else
          rotateLR(k);
    }
  }
}