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


public class SuchBaum extends Baum {

    // Auf das Konstrukt Comparable<Type> wird in diesem Beispiel verzichtet,
	// da es in diesem Stadium der Vorlesung noch nicht bekannt ist.
	
    // sucht x im SuchBaum: liefert den SuchBaum mit x in der Wurzel, ggf. leer
    private SuchBaum find(Comparable x) { 
        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);
    }



    /** Sucht x im SuchBaum: liefert null, wenn x nicht gefunden wurde,
     * sonst Comparable-Objekt x */
    public Comparable lookup(Comparable x) { 
        return (Comparable)find(x).inhalt;
    }



    /** fuegt x in SuchBaum ein: liefert true, wenn erfolgreich, sonst false.*/
    public boolean insert(Comparable x) { 
        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;
    }




    /** loescht x aus SuchBaum: liefert true, wenn erfolgreich geloescht, 
     *  sonst false */
    public boolean delete(Comparable x) { 
        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;
        }
    }

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

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