/*******************************  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 = ((SuchBaum)s.left()).findMax(); // Maximum im linken
                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
    }
}