import java.util.*;

class Knoten<T extends Comparable<T>>{
    T inhalt;
    Knoten<T> o, l, r;
    Knoten(T el){ inhalt = el;}
    Knoten(T el, Knoten<T> oben){ inhalt = el; o = oben;}
    public String toString(){  return inhalt.toString();}
    }

class BSBaum<T extends Comparable<T>>{
    private Knoten<T> wurzel = null;

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

    void einfuegen(T ... t){
		   for (T el : t)einfuegen(el);
		   }
    
    
    void einfuegen(T t){
		   if (wurzel == null) wurzel = new Knoten<T>(t);
		   else rekEinfuegen(t, wurzel);
		   }

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

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

    void loesche1(Knoten<T> sohn){  // Loescht Knoten mit max. einem Sohn 
      // Bestimme den Enkel - kann null sein 
			Knoten<T> enkel = (sohn.l == null) ? sohn.r : sohn.l;	 
			if (sohn == wurzel)  { wurzel = enkel;  wurzel.o = null; return; }
		      // Ab hier ist klar: Vater existiert 
			Knoten<T> 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<T> kp){
				Knoten<T> 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.inhalt.compareTo(min.o.inhalt) == 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.inhalt = min.inhalt; // Kopiere Inhalt nach oben
				loesche1(min);
        }	

    Knoten<T> suche(T t){ return rekSuche(t, wurzel);}
		Knoten<T> rekSuche(T t, Knoten<T> k){
				if (k == null) return null;
				if (t.compareTo(k.inhalt) == 0) return k;
				if (t.compareTo(k.inhalt) < 0) return rekSuche(t, k.l);
				else return rekSuche(t, k.r);
				}

    
    void ausgabeVorw(){
    	System.out.println("--------- Ausgabe vorwärts -------------");
        Knoten<T> 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<T> kp = sucheMax();
        while (kp != null) { 
           System.out.print(kp);
           kp = vorgaenger(kp);
           }
        System.out.println();
        } 
        
    void dumpKnoten(Knoten<T> 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<T> 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 static void main(String args[]) {
        System.out.println("Baum Tester");
        System.out.println("");
        
        BSBaum<Character> buchstabenBaum = new BSBaum<Character>();
        buchstabenBaum.einfuegen('B','A','U','M','B','E','I','S','P','I','E','L');

        System.out.println();
        
        buchstabenBaum.dumpBaum();

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