/*******************************  SuchBaum.java *******************************/

import AlgoTools.IO;

/** Implementation eines binaeren Suchbaums ueber Comparable-Objekten.       
    Bereitgestellt werden die im Interface Menge angekuendigten Methoden 
    lookup, insert und delete als oeffentliche Methoden. 
    
    Zur Implementation wird von allen dreien die private Methode find benutzt, 
    die fuer die Navigation im Baum zustaendig ist. 
    
    Die Methode delete verwendet zusaetzlich noch die private Methode findMax.
*/


public class SuchBaum extends VerweisBaum implements Menge {


  private SuchBaum find(Comparable x) {              // liefert den Suchbaum 
                                                     // mit x in der Wurzel
                                                     // (ggf. leerer Baum) 
    if (empty())                                 return this;
    if(((Comparable)value()).compareTo(x) == 0)  return this;
    if(((Comparable)value()).compareTo(x) >  0)  return 
       ((SuchBaum)left()).find(x);
    else                                         return 
       ((SuchBaum)right()).find(x);
    }


  public Comparable lookup(Comparable x){   // Sucht x im SuchBaum
                                            // falls gefunden: 
    return (Comparable)find(x).inhalt;      // liefert Comparable-Object
    }                                       // null sonst


  public boolean insert(Comparable x) {     // fuegt x in SuchBaum ein
                                            // liefert true, falls erfolgreich
                                            // false sonst

    SuchBaum s = find(x);                   // SuchBaum mit x in der Wurzel 
                                            // oder leer

    if (s.empty()) {                        // wenn leer, d.h. x noch nicht
                                            // im SuchBaum enthalten:
        s.inhalt = x;                       // setzte Inhalt auf x
        s.links  = new SuchBaum();          // neuer leerer SuchBaum links
        s.rechts = new SuchBaum();          // neuer leerer SuchBaum rechts
        return true;
    }
    else return false;
  }



  public boolean delete(Comparable x) {     // loescht x aus SuchBaum,
                                            // liefert true, falls erfolgreich 
                                            // false sonst
    
    SuchBaum s = find(x);                   // SuchBaum mit x in der Wurzel 
                                            // oder leer
    SuchBaum ersatz;                        // Ersatzknoten

    if (s.empty()) return false;            // wenn x nicht gefunden: false
    else {                                  // wenn x gefunden
      if      (s.left().empty())  
        ersatz = (SuchBaum)s.right();
      else if (s.right().empty()) 
        ersatz = (SuchBaum)s.left();
      else {                                // Knoten mit x hat zwei Soehne
        ersatz =                            // ermittele das Maximum
          ((SuchBaum)s.left()).findMax();   // im linken Teilbaum
        s.inhalt = ersatz.inhalt;           // ersetze Inhalt
        s = ersatz;                         // zu ersetzen
        ersatz = (SuchBaum)ersatz.left();   // Ersatz: linker
      }
      s.inhalt = ersatz.inhalt;             // ersetze die Komponenten
      s.links  = ersatz.links;
      s.rechts = ersatz.rechts;
      return true;
    }
  }

  private SuchBaum findMax() {              // sucht im nichtleeren SuchBaum 
                                            // liefert den SuchBaum 
                                            // mit dem Maximum in der Wurzel
    SuchBaum hilf = this;

    while (!hilf.right().empty()) 
      hilf = (SuchBaum)hilf.right();
    return hilf;                            // der rechteste Nachfahre von this
  } 
}