Mine

import java.util.Iterator;import java.util.*;public class AVLBaum<E extends Comparable<E>> implements AVLInterface<E> {	/** die Wurzel des Baumes */	private Knoten<E> root;	/** die Anzahl an gespeicherten Elementen */	private int size;	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#getRoot()	 */	public Knoten<E> getRoot() {		return root;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#getNode(E)	 */	public Knoten<E> getNode(E value) {		// Schleppzeiger zum Speichern des gewuenschten Vorgaengers		Knoten<E> schlepp = null;		Knoten<E> node = root;		while (node != null) {			// Schleppzeiger weitersetzen			schlepp = node;			final int result = node.value.compareTo(value);			if (result == 0) {				// gesuchter Knoten gefunden				return node;			} else if (result > 0) {				// auf der linken Seite weiter suchen				node = node.left;			} else {				// auf der rechten Seite weiter suchen				node = node.right;			}		}		// Knoten nicht gefunden, Schleppzeiger zeigt auf potenziellen		// Vorgaenger		return schlepp;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#size()	 */	public int size() {		return size;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#isEmpty()	 */	public boolean isEmpty() {		return root == null;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#clear()	 */	public void clear() {		root = null;		size = 0;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#contains(E)	 */	public boolean contains(E value) {		// Wenn der Baum nicht leer und der Wert gueltig ist,		// muss ueberprueft werden, ob der Wert im Baum gefunden wurde.		return root != null && value != null				&& getNode(value).value.compareTo(value) == 0;	}	/**	 * haengt den neuen Knoten an die Stelle des alten Knoten im Baum	 * 	 * @param alt	 * @param neu	 * @return <code>true</code>, wenn der Knoten links angefuegt wurde	 */	private boolean swap(Knoten<E> alt, Knoten<E> neu) {		// alten Knoten aus dem Baum entfernen		// Vaterreferenz wird beim Ersetzen zurueckgesetzt		alt.setLeft(null);		alt.setRight(null);		if (alt == root) {			// Wurzel ersetzen			root = neu;			return false;		} else if (alt.parent.left == alt) {			// links ersetzen			alt.parent.setLeft(neu);			return true;		} else {			// rechts ersetzen			alt.parent.setRight(neu);			return false;		}	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#add(E)	 */	public boolean add(E value) {		// pruefen, ob der Wert schon enthalten ist		if (value == null) {			return false;		}		final Knoten<E> n = getNode(value);		if (n != null && n.value.compareTo(value) == 0) {			return false;		}		// wenn nicht, an entsprechendem Knoten einfuegen		final Knoten<E> neu = new Knoten<E>(value);		if (n == null) {			// Baum war vorher leer			root = neu;		} else if (n.value.compareTo(value) < 0) {			n.setRight(neu);			// Ausbalancieren: Teilbaum ist rechts gewachsen			rebalance(n, false, true);		} else {			n.setLeft(neu);			// Ausbalancieren: Teilbaum ist links gewachsen			rebalance(n, true, true);		}		size++;		// Q: Baum ist leer oder von der Wurzel ab strukturell konsistent		// TODO: momentan ohne Balance- und Hoehenpruefung		assert root == null || root.subBaumKonsistent(null, true);		return true;	}	/*	 * (non-Javadoc)	 * 	 * @see AVLInterface#remove(E)	 */	public boolean remove(E value) {		// pruefen, ob der Wert schon enthalten ist		if (value == null) {			return false;		}		final Knoten<E> node = getNode(value);		if (node == null || node.value.compareTo(value) != 0) {			return false;		}		final Knoten<E> parent = node.parent;		// wenn ja, loesche diesen		if (node.left == null) {			// haenge rechten Ast anstelle des zu loeschenden Knotens			// funktioniert auch fuer Blaetter			final boolean left = swap(node, node.right);			// Ausbalancieren: Teilbaum ist <code>left</code> geschrumpft			rebalance(parent, left, false);		} else if (node.right == null) {			// haenge linken Ast anstelle des zu loeschenden Knotens			final boolean left = swap(node, node.left);			// Ausbalancieren: Teilbaum ist <code>left</code> geschrumpft			rebalance(parent, left, false);		} else {			// innerer Knoten mit zwei Aesten			// suche kleinsten Knoten auf der rechten Seite			Knoten<E> a = node.right;			while (a.left != null) {				a = a.left;			}			// ziehe den Wert nach oben			node.value = a.value;			final Knoten<E> parenta = a.parent;			// und loesche den anderen Knoten, der nur einen rechten Ast hat			final boolean left = swap(a, a.right);			// Ausbalancieren: Teilbaum a ist <code>left</code> geschrumpft			rebalance(parenta, left, false);		}		size--;		// Q: Baum ist leer oder von der Wurzel ab strukturell konsistent		// TODO: momentan ohne Balance- und Hoehenpruefung		assert root == null || root.subBaumKonsistent(null, true);		return true;	}	public Knoten<E> rotateRight(Knoten<E> x) {	    if ((x == null) || (x.left == null)) {		return null;	    }	    Knoten<E> save1 = x.left.right;	    Knoten<E> save2 = x.left;	    Knoten<E> parent = x.parent;	    	    if (parent != null) {		if (parent.left == x) {		    x.setLeft(save1);		    save2.setRight(x);		    parent.setLeft(save2);		    return parent.left;		}		else {		    x.setLeft(save1);		    save2.setRight(x);		    parent.setRight(save2);		    return parent.right;		}	    }	    else {		x.setLeft(save1);		save2.setRight(x);		root = save2;		return root;	    }	}	public Knoten<E> rotateLeft(Knoten<E> x) {	    	    if ((x == null) || (x.right == null)) {		return null;	    }	    Knoten<E> save1 = x.right.left;	    Knoten<E> save2 = x.right;	    Knoten<E> parent = x.parent;	    if (parent != null) {		if (parent.left == x) {		    x.setRight(save1);		    save2.setLeft(x);		    parent.setLeft(save2);		    return parent.left;		}		else {		    x.setRight(save1);		    save2.setLeft(x);		    parent.setRight(save2);		    return parent.right;		}	    }	    else {		x.setRight(save1);		save2.setLeft(x);		root = save2;		return root;	    }	}	public Knoten<E> doubleRight(Knoten<E> x) {	    if ((x == null) || (x.left == null)) {		return null;	    }	    	    rotateLeft(x.left);	    return rotateRight(x);	}	public Knoten<E> doubleLeft(Knoten<E> x) {	    if ((x == null) || (x.right == null)) {		return null;	    }	    Knoten<E> save = rotateRight(x.right);	    return rotateLeft(x);	}	public void rebalance(Knoten<E> x, boolean left, boolean grown) {	    if (x == null) {		return;	    }	    x.height = heightHelp(x);	    if (Math.abs(x.balance()) <= 1) {		rebalance(x.parent, false, false);	    }	    else {		if (x.balance() > 1) {		    if (x.left.balance() < 0) {			Knoten<E> save = doubleRight(x);			rebalance(save.parent, false, false);		    }		    else {			Knoten<E> save = rotateRight(x);			rebalance(save.parent, false, false);		    }		}		else {		    if (x.right.balance() <= 0) {			Knoten<E> save = rotateLeft(x);			rebalance(save.parent, false, false);		    }		    else {			Knoten<E> save = doubleLeft(x);			rebalance(save.parent, false, false);		    }		}	    }	}	public int height() {		    return heightHelp(getRoot());	}	private int heightHelp(Knoten<E> wurzel) {	    int hoehe;	    int hoeheLinks = -1;	    int hoeheRechts = -1;	    if (wurzel == null) {		return 0;	    }	    if (wurzel.left != null) {		hoeheLinks = heightHelp(wurzel.left);	    }	    if (wurzel.right != null) {		hoeheRechts = heightHelp(wurzel.right);	    }	    if (hoeheRechts >= hoeheLinks) {		hoehe = hoeheRechts + 1;	    }	    else {		hoehe = hoeheLinks + 1;	    }	    return hoehe;	}	public E first() {	    Knoten<E> buffer = getRoot();	    while (buffer.left != null) {		buffer = buffer.left;	    }	    return buffer.value;	}	public E last() {	    Knoten<E> buffer = getRoot();	    while (buffer.right != null) {		buffer = buffer.right;	    }	    return buffer.value;	}	public Iterator<E> iterator() {	    return new AVLIterator();	}	private LinkedList<E> liste(Knoten<E> wurzel, LinkedList<E> list) {	    if (wurzel != null) {		liste(wurzel.left, list);		list.add(wurzel.value);		liste(wurzel.right, list);	    }	    return list;	}	private class AVLIterator implements Iterator<E> {	    Iterator<E> it;	    LinkedList<E> liste;	    E letztes;	    public AVLIterator() {		liste = new LinkedList<E>();		it = liste(AVLBaum.this.getRoot(), liste).iterator();	    }	    public boolean hasNext() {		return it.hasNext();	    }	    public E next() throws NoSuchElementException {		if (hasNext()) {		    letztes = it.next();		    return letztes;		}		else {		    throw new NoSuchElementException();		}	    }	    public void remove() throws IllegalStateException {		if (letztes != null) {		    AVLBaum.this.remove(letztes);		    letztes = null;		}		else {		    throw new IllegalStateException();		}	    }	}	public String toString() {		return this.getClass().getSimpleName() + "(" + size() + ")";	}/*	public void toString(Knoten<E> root) {	    if (root != null) {		System.out.print("Wert: " + root + " Vater: " + root.parent + " linkes Kind: " + root.left + " rechtes Kind: " + root.right);		System.out.println();		toString(root.left);		toString(root.right);	    }	}	public static void main(String[] args) {		AVLBaum<Integer> c = new AVLBaum<Integer>();		for (int i = 1; i <= 13; i++) {		    c.add(i);		}		c.add(0);		c.remove(9);		c.remove(11);		c.toString(c.getRoot());		c.add("W"); c.add("Y"); c.add("S"); c.add("G"); c.add("U");		c.doubleRight(c.getNode("Y"));		c.toString(c.getRoot());		System.out.println();		c.rotateRight(c.getNode("W"));		c.toString(c.getRoot());		System.out.println();		c.rotateLeft(c.getNode("S"));		c.toString(c.getRoot());	}*/}