/*
 * Eine Knoten-Klasse für die Implementierung von Bäumen.
 * Hab's mal ganz edel mit Comparables statt einfach mit
 * int-Werten gemacht.
 */
class Node {
	
	/*
	 * Wir definieren alle unsere Bäume in derselben Package,
	 * deswegen sind die Variablen durch das protected-Attribut
	 * vor Zugriff von außen (aus anderen Packages) geschützt.
	 * Man könnte auch "ordentlich" kapseln und Getter- & Setter-
	 * Methoden verwenden, was den Code aber extrem aufblähen
	 * würde.
	 */
	protected Comparable  value;  // Wert
	protected Node        left;   // linker Kind-Knoten
	protected Node        right;  // rechter Kind-Knoten
	
	
	public Node(Comparable value, Node left, Node right) {
		this.value  = value;
		this.left   = left;
		this.right  = right;
	}
	
}


/* 
 * Dieses Interface dient dazu, Baumimplementierungen vor
 * "unqualifizierten" Zugriffen von außen zu schützen. (Damit
 * z.B. nicht irgendwelche Knoten direkt in die Datenstruktur
 * eingefügt werden, ohne die Sortierung zu beachten, etc.
 */
interface BinaryTree {
	
	public void insert(Comparable value);
	
	public void remove(Comparable value);
	
}


/* 
 * Eine Implementierung des BinaryTree-Interface
 */
public class BinTree implements BinaryTree {
	
	Node root;
	
	public BinTree(Node root) {
		this.root = root;
	}
	
	
	/*
	 * Fügt ein Element in den Binärbaum ein.
	 * (Mehrfaches einfügen ist erlaubt.)
	 */
	public void insert(Comparable value) {
		
		Node temp = root;
		Node parent = null;
		
		while (temp != null) {
			
			parent = temp;
			
			if (value.compareTo(temp.value) < 0) {
				temp = temp.left;
			}
			else {
				temp = temp.right;
			}
		}
		
		if (parent != null) {
			if (value.compareTo(parent.value) > 0) {
				parent.right = new Node(value, null, null);
			}
			else {
				parent.left = new Node(value, null, null);
			}
		}
		
	}
	
	
	/*
	 * Ersetzt das zu löschende Element mit dem
	 * größten Element aus dem linken Unterbaum
	 */
	public void remove(Comparable value) {
		
		Node temp = root;
		Node parent = null;
		
		// Knoten suchen
		while ((temp != null) && (temp.value.compareTo(value) != 0)) {
			
			parent = temp;
			
			if (value.compareTo(temp.value) < 0) {
				temp = temp.left;
			}
			else {
				temp = temp.right;
			}
		}
		
		// wenn gefunden, Knoten löschen
		if (temp != null) {
			
			// wenn linker Unterbaum existiert, mit größtem Element daraus ersetzen
			if (temp.left != null) {
				
				Node temp2 = temp.left;  // der Knoten, der nach oben versetzt wird
				Node parent2 = temp;     // der Elternknoten von dem, der nach oben versetzt wird
				
				while (temp2.right != null) {
					parent = temp2;
					temp2 = temp2.right;
				}
				
				if (temp2 != temp.left) temp2.left = temp.left;
				temp2.right = temp.right;
				parent2.right = temp2.left;
				
				if (parent.left == temp) {
					parent.left = temp2;
				}
				else {
					parent.right = temp2;
				}
				
			}
			else { // sonst einfach mit rechtem Unterbaum ersetzen
			
				if (parent.left == temp) {
					parent.left = temp.right;
				}
				else {
					parent.right = temp.right;
				}
			}
		}
	}
	
	
	/*
	 * Gibt den Baum als AVL-Baum zurück
	 */
	public static BinTree getAvlTree(BinTree b) {
		// TODO
		return null;		
	}
	
	
	/*
	 * Wir überschreiben die toString-Methode von
	 * Object, damit sich der Baum leicht ausgeben lässt
	 * (s. main-Methode).
	 *
	 * ACHTUNG: Die Methode is HÖLLE langsam, weil massen-
	 *  haft Strings konkateniert werden. Schnell implementiert,
	 *  aber extrem unperformant.
	 */
	public String toString() {
		
		return getTreeAsString(root);
	}
	
	private String getTreeAsString(Node n) {
		
		if (n != null) {
			//System.out.println(n.value);
			return "(" + getTreeAsString(n.left) + ") " + n.value + " (" + getTreeAsString(n.right) + ")";
		}
		
		return "*";
	}
	
	
	public static void main(String[] args) {
		
		/*
		 * Also - Bau'n wir'n Baum:
		 *
		 *                     10
		 *           .----------'---------.
		 *           7                   12
		 *      .----'----.          .----'----.
		 *      5         9         11        15
		 *    .-'       .-'
		 *    2         8
		 *
		 * ...und dann löschen wir die 7:
		 *
		 *                     10
		 *           .----------'---------.
		 *           5                   12
		 *      .----'----.          .----'----.
		 *      2         9         11        15
		 *             .--'
		 *             8
		 *
		 */
		
		
		BinTree tree = new BinTree( new Node(new Integer(10), null, null) );
		
		tree.insert(new Integer(7));
		tree.insert(new Integer(12));
		tree.insert(new Integer(5));
		tree.insert(new Integer(9));
		tree.insert(new Integer(11));
		tree.insert(new Integer(15));
		tree.insert(new Integer(2));
		tree.insert(new Integer(8));
		
		System.out.println(tree);
		
		tree.remove(new Integer(7));
		
		System.out.println(tree);
		
	}
	
}