import java.util.Iterator;
/**
* Created on 30.12.2006
*/
/**
* Dieses Interface beschreibt die Schnittstelle eines AVL-Baums zum Speichern
* von vergleichbaren Werten. Ein AVL-Baum ist ein binaerer Suchbaum, bei dem
* die Hoehe der Aeste eines Teilbaumes nich maximal um eins unterscheidet, also
* jeder Knoten ausgeglichen ist
*
* @author Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
*
* @param <E>
* der Typ der zu speichernden Werte. Diese muessen untereinander
* vergleichbar sein.
*
*/
public interface AVLInterface<E extends Comparable<E>> extends Iterable<E> {
/**
* Diese Klasse stellt einen Knoten im AVLBaum dar.
*
* @author Marc Woerlein (Woerlein@informatik.uni-erlangen.de)
*
* @param <Typ>
* der im Knoten zu speichernde Typ. Dieser muss fuer einen
* allgemeinen Binaerbaum nicht untereinander Vergleichbar sein.
*/
public class Knoten<Typ> {
/** im Knoten gespeicherter Wert */
public Typ value;
/** hoehe des Knotens in Baum */
public int height;
/** Elternknoten */
public Knoten<Typ> parent = null;
/** linkes Kind */
public Knoten<Typ> left = null;
/** rechtes Kind */
public Knoten<Typ> right = null;
/**
* erzeugt einen Knoten fuer den uebergebenen Wert
*
* @param value
*/
public Knoten(Typ value) {
this.value = value;
}
/**
* trennt den Knoten von seinem Elternknoten ab
*/
private void unlink() {
if (parent != null) {
if (parent.left == this) {
parent.left = null;
} else {
parent.right = null;
}
parent = null;
}
}
/**
* fuegt den uebergebenen Knoten als linkes Kind an.
* <p>
* Dafuer enfernt es den alten Knoten und passt die Hoehe dieses Knotens
* an. Elternhoehen werden NICHT aktuallisiert und muessen seperat
* angepasst werden!
*
* @param left
* der neue Knoten, oder <code>null</code> zum loeschen
*/
public void setLeft(Knoten<Typ> left) {
if (this.left != null) {
// alten linken Knoten aushaengen
this.left.parent = null;
this.left = null;
// Hoehe anpassen
height = (right == null ? 0 : right.height + 1);
}
if (left != null) {
// neuen Knoten aus alten Baum aushaengen
left.unlink();
// neuen linken Knoten einhaengen
left.parent = this;
this.left = left;
// Hoehe anpassen
height = (height <= left.height ? left.height + 1 : height);
}
}
/**
* fuegt den uebergebenen Knoten als rechtes Kind an.
* <p>
* Dafuer enfernt es den alten Knoten und passt die Hoehe dieses Knotens
* an. Elternhoehen werden NICHT aktuallisiert und muessen seperat
* angepasst werden!
*
* @param right
* der neue Knoten, oder <code>null</code> zum loeschen
*/
public void setRight(Knoten<Typ> right) {
if (this.right != null) {
// alten rechten Knoten aushaengen
this.right.parent = null;
this.right = null;
// Hoehe anpassen
height = (left == null ? 0 : left.height + 1);
}
if (right != null) {
// neuen Knoten aus alten Baum aushaengen
right.unlink();
// neuen rechten Knoten einhaengen
right.parent = this;
this.right = right;
// Hoehe anpassen
height = (height <= right.height ? right.height + 1 : height);
}
}
/**
* @return die Balance (linke Hoehe - rechte Hoehe) des Knotens
*/
public int balance() {
final int linkeHoehe = (left == null ? -1 : left.height);
final int rechteHoehe = (right == null ? -1 : right.height);
return linkeHoehe - rechteHoehe;
}
/**
* @return <code>true</code>, wenn die eigenen Hoehe zu der der
* Kinder passt
*/
public boolean heightKonsistent() {
final int linkeHoehe = (left == null ? -1 : left.height);
final int rechteHoehe = (right == null ? -1 : right.height);
return height == Math.max(linkeHoehe, rechteHoehe) + 1;
}
/**
* ueberprueft rekursiv, ob der Teilbaum der an diesem Knoten haengt,
* konsistent Aufgebaut ist.
*
* @param parent
* der eigentliche Vorgaenger des Knotens
* @param checkMore
* sagt, das neben den Verzeigerung auch die Hoehen und
* Balancen ueberprueft werden sollen
* @return <code>true</code>, wenn der Teilbaum Konsistent ist
*/
public boolean subBaumKonsistent(Knoten<Typ> parent, boolean checkMore) {
return this.parent == parent
&& (left == null || left.subBaumKonsistent(this, checkMore))
&& (right == null || right.subBaumKonsistent(this,
checkMore))
&& (!checkMore || (Math.abs(balance()) < 2 && heightKonsistent()));
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
public String toString() {
return value.toString() + "(" + height + "/" + balance() + ")";
}
}
/**
* @return den Wurzelkonten des Baumes, oder <code>null</code> bei einem
* leeren Baum
*/
public Knoten<E> getRoot();
/**
* Diese Methode sucht nach dem Knoten, mit dem uebergebenen Wert. Wenn es
* keinen Knoten gibt, der den Wert enthaellt, wird der Knoten, an den der
* gesuchte Wert angehaengt gehoert, zurueck geliefert.
*
* @param value
* der zu suchende/einzufuegende/zuloeschende Wert
* @return den Baumknoten, mit dem gesuchten Wert, oder dessen potentiellen
* Vater
*/
public Knoten<E> getNode(E value);
/**
* @return Anzahl der im Baum gespeicherten Werte
*/
public int size();
/**
* schaut ob der Suchbaum leer ist
*
* @return <code>true</code>, wenn der Suchbaum leer ist ansonsten
* <code>false</code>
*/
public boolean isEmpty();
/**
* loescht alle Werte aus dem Baum, so das er danach leer ist
*/
public void clear();
/**
* schaut nach, ob der uebergebene Wert schon in den Baum eingefuegt wurde
*
* @param value
* der zu suchende Wert
* @return <code>true</code>, wenn der Wert schon im Baum enthalten ist,
* ansonsten <code>false</code>
*/
public boolean contains(E value);
/**
* fuegt einen neuen Wert in den AVL-Baum ein
*
* @param value
* der einzufuegende Wert
* @return <code>true</code>, wenn der Wert neu eingefuegt wurde und
* <code>false</code>, wenn der Wert schon vorher im Baum war
*/
public boolean add(E value);
/**
* entfernt den uebergebenen Wert aus dem AVL-Baum
*
* @param value
* der zu loeschende Wert
* @return <code>true</code>, wenn der Wert aus dem Baum entfernt wurde
* und <code>false</code>, wenn der Wert vorher nicht im Baum war
*/
public boolean remove(E value);
// NEUE METHODEN
/**
* einfache Rotation der Wurzel x eines Teilbaumes nach rechts
*
* @param x
* @return die neue Wurzel des Teilbaumes
*/
public Knoten<E> rotateRight(Knoten<E> x);
/**
* einfache Rotation der Wurzel x eines Teilbaumes nach links
*
* @param x
* @return die neue Wurzel des Teilbaumes
*/
public Knoten<E> rotateLeft(Knoten<E> x);
/**
* doppelte Rotation der Wurzel x eines Teilbaumes nach rechts
*
* @param x
* @return die neue Wurzel des Teilbaumes
*/
public Knoten<E> doubleRight(Knoten<E> x);
/**
* doppelte Rotation der Wurzel x eines Teilbaumes nach links
*
* @param x
* @return die neue Wurzel des Teilbaumes
*/
public Knoten<E> doubleLeft(Knoten<E> x);
/**
* rebalanciert den Baum ab dem Knoten x nach oben
*
* @param x
* der Knoten dessen Kind sich veraendert hat
* @param left
* zeigt an ob am linken (<code>true</code>) oder am rechten (<code>false</code>)
* Ast von x eine Veraenderung statt gefunden hat.
* @param grown
* sagt, ob der veraenderte Teilbaum vergroessert (<code>true</code>)
* oder verkleinert (<code>false</code>) wurde.
*/
public void rebalance(Knoten<E> x, boolean left, boolean grown);
/**
* ermittelt die aktuelle Hoehe des Suchbaumes, also die Laenge des
* laengsten Pfades von der Wurzel zu einem Blatt
*
* @return die (aktuelle) Hoehe des Baumes, oder -1 beim leeren Baum
*/
public int height();
/**
* @return das kleinste gespeicherte Element
*/
public E first();
/**
* @return das groesste gespeicherte Element
*/
public E last();
/**
* @return einen Iterator der sortiert ueber alle gespeicherten Werte
* iteriert.
*/
public Iterator<E> iterator();
}