import java.io.IOException;

class Element implements Comparable{
    Character Inhalt;
    Element(Character c){ Inhalt = c;}
    public int compareTo(Object o){
        Element e = (Element) o;
        return Inhalt.compareTo(e.Inhalt);} 
    }


class Knoten{
    Element e;
    Knoten o, l, r;
    Knoten(Element el){ e = el;}
    Knoten(Element el, Knoten oben){ e = el; o = oben;}
    public String toString(){return (e.Inhalt).toString();}
    }

class SuchBaum{
    private Knoten wurzel = null;

    boolean istLeer(){ return wurzel == null;}


     void einfuegen(Element e){
		if (wurzel == null) wurzel = new Knoten(e);
		else rekEinfuegen(e, wurzel);
		}

	void rekEinfuegen(Element e, Knoten bp){
					// Beginn: Code für Implementierungsinvariante
		if (e.compareTo(bp.e) == 0){
			Knoten neu = new Knoten(e, bp);
			if (bp.l != null) bp.l.o = neu;
			neu.l = bp.l;
			bp.l = neu;
			return;
			} 		// Ende des Codes für Implementierungsinvariante
		if (e.compareTo(bp.e) < 0) 
			if (bp.l == null) bp.l = new Knoten(e, bp);
			else rekEinfuegen(e, bp.l);
		else
			if (bp.r == null) bp.r = new Knoten(e, bp);
			else rekEinfuegen(e, bp.r);
		}
        
    Knoten sucheMin(){ return sucheMin(wurzel);}
	
    Knoten sucheMin(Knoten kp){
			if (kp == null) return kp;
			while (kp.l != null) kp = kp.l;
			return kp;
			}
        
    Knoten sucheMax(){ return sucheMax(wurzel); }    
    
    Knoten sucheMax(Knoten kp){
        if (kp == null) return kp;
        while (kp.r != null) kp = kp.r;
        return kp;
        }  
    
        
    Knoten nachfolger(Knoten kp){
			if (kp == null) return kp;
			if (kp.r != null) return sucheMin(kp.r);
			Knoten oben = kp.o;
			while((oben != null) && (oben.r == kp)) {
				kp = oben; 
				oben = kp.o;
				}
			return oben;
			}  
      
        
    Knoten vorgaenger(Knoten kp){
        if (kp == null) return kp;
        if (kp.l != null) return sucheMax(kp.l);
        Knoten Oben = kp.o;
        while((Oben != null) && (Oben.l == kp)) {kp = Oben; Oben = kp.o;}
        return Oben;
        }        

    void loescheKnoten(Knoten kp){
	if (kp == null) return; 
	if (kp.l == null || kp.r == null) loesche1(kp); 
	else loesche2(kp);
        }

    void loesche1(Knoten sohn){  // Loescht Knoten mit max. einem Sohn 
      // Bestimme den Enkel - kann null sein 
			Knoten enkel = (sohn.l == null) ? sohn.r : sohn.l;	 
			if (sohn == wurzel)  { wurzel = enkel;  wurzel.o = null; return; }
		      // Ab hier ist klar: Vater existiert 
			Knoten vater = sohn.o;	 
		      //Verbinde Vater zum Enkel 
			if (vater.l == sohn) vater.l = enkel; else vater.r = enkel; 
		      // Verbinde Enkel zum Vater 
			if (enkel != null) enkel.o = vater; 	
        }

    void loesche2(Knoten kp){
				Knoten min = sucheMin(kp.r);
			      // Beginn: Berücksichtigung von Duplikaten 
				min.l = kp.l;
				if (min.l != null) min.l.o = min; // Vaterknoten korrekt?		
				while(min.e.compareTo(min.o.e) == 0) min = min.o;	
				kp.l = min.l;
				if (kp.l != null) kp.l.o = kp;	// Vaterknoten korrekt? 
				min.l = null; // Damit loesche1 anwendbar wird 
			      // Ende: Berücksichtigung von Duplikaten 
				kp.e = min.e; // Kopiere Inhalt nach oben
				loesche1(min);
        }	

    Knoten suche(Element e){ return rekSuche(e, wurzel);}
			Knoten rekSuche(Element e, Knoten bp){
				if (bp == null) return null;
				if (e.compareTo(bp.e) == 0) return bp;
				if (e.compareTo(bp.e) < 0) return rekSuche(e, bp.l);
				else return rekSuche(e, bp.r);
				}

    
    void ausgabeVorw(){
    	System.out.println("--------- Ausgabe vorwärts -------------");
        Knoten kp = sucheMin();
        while (kp != null) { 
           System.out.print(kp);
           kp = nachfolger(kp);
           }
        System.out.println();
        } 
    
    void ausgabeRueckw(){
        System.out.println("--------- Ausgabe rückwärts -------------");
        Knoten kp = sucheMax();
        while (kp != null) { 
           System.out.print(kp);
           kp = vorgaenger(kp);
           }
        System.out.println();
        } 
        
    void DumpKnoten(Knoten z){
        System.out.println("Ausgabe von Knoten: " + z);
        if (z.o != null) System.out.println("Vorgänger-Knoten: " + z.o);
         else System.out.println("Kein Vorgänger-Knoten!");
        if (z.l != null) System.out.println("Linker Nachfolger-Knoten: " + z.l);
         else System.out.println("Kein linker Nachfolger-Knoten!"); 
        if (z.r != null) System.out.println("Rechter Nachfolger-Knoten: " + z.r);
         else System.out.println("Kein rechter Nachfolger-Knoten!");    
        }  
        
    void DumpTeilBaum(Knoten z, int Level){
        if (z == null) return;
        System.out.println("----------------------");
        System.out.print("Level: " + Level + " ");
        DumpKnoten(z);
        if (z.l != null) DumpTeilBaum(z.l, Level + 1);
        if (z.r != null) DumpTeilBaum(z.r, Level + 1);
        } 
        
    void DumpBaum(){
        System.out.println("--------- Dump Baum -------------");
        DumpTeilBaum(wurzel, 0);    
        }         
}


public class BaumS {

    public static void main(String args[]) {
        System.out.println("Baum Tester");
        System.out.println("");
        String Beispiel = "BAUMBEISPIEL";
        int L = Beispiel.length();
        SuchBaum MeinBaum = new SuchBaum();

        for (int i = 0; i < L; i++){
            char c = Beispiel.charAt(i);
            System.out.print(c);
            Element e = new Element(new Character(c));
            MeinBaum.einfuegen(e);
            }
        System.out.println();
        
        MeinBaum.DumpBaum();

        if (MeinBaum.istLeer())System.out.println("Sch...! Der Baum blieb leer!");
        else {
            MeinBaum.ausgabeVorw();
            MeinBaum.ausgabeRueckw();
           
            Element such = new Element(new Character('B'));
            Knoten zsuch = MeinBaum.suche(such);
            System.out.println("--->> Löschen von: " + zsuch);
            if (zsuch != null){
                MeinBaum.DumpKnoten(zsuch);
                MeinBaum.loescheKnoten(zsuch);
                MeinBaum.ausgabeVorw();
                MeinBaum.ausgabeRueckw();
                MeinBaum.DumpBaum();
                }
            else System.out.println("Gesuchtes Element <" + such + "> nicht gefunden");
            
            }
        System.out.println("");
        }
      }