* Name: Rot-Schwarz Baum<br><br>
* Beschreibung: Die Klasse rbtree.java ist eine Javaklasse, welche einen
* ausgeglichenen Baum implementiert. Gewaehlt wurde dafuer ein
* Rot-Schwarz Baum. Die Ausgeglichenheit ist nicht wie bei einem AVL-Baum
* definiert, so dass die max. Tiefendifferenz zwischen zwei
* Unterbaeumen eines Elements hoechstens eins betraegt.
* Ein Baum heisst ausgeglichen, wenn die Operationen Einfuegen,
* Loeschen, Finden in jedem Fall (average und worst cast cost) von
* der Groessenordnung O(log n) sind.<br><br>
* Erste Version: 11.12.1999
* Letzte Aenderung: 2.1.1999<br><br>
*
* Um die Klasse rbtree zu benutzen, muss ein Objekt der Klasse erstellt
* werden.
* Die einzelnen Methoden werden an gegebener Stelle beschrieben.<br><br>
*
* Bemerkung: Derzeit haelt der Rot-Schwarz Baum keine Daten (Objekte), sondern
* nur Elemente von Typ Integer, die gleichzeitig Suchschluessel sind.
*<br><br>
* Invariante<br>
* ==========<br><br>
*
* Ein Rot-Schwarz-Baum ist ein Spezialfall eines binaeren Suchbaums.
* Fuer einen binaeren Suchbaum muss folgendes gelten: <br>
* - Jeder Knoten hat hoechstens 2 Soehne.<br>
* - Jeder Knoten hat einen bestimmten Wert (Sortierkriterium).<br>
* - Wenn k der Wert eines gegebenen Knoten ist, dann gilt:<br>
* - alle Knoten im linken Unterbaum des Knoten haben einen kleineren
* Suchindex als k<br>
* - alle Knoten im rechten Unterbaum des Knoten haben groessere Werte
als k<br>
* - Die "Spitze" des Baumes ist die Wurzel (root).<br><br>
*
* Ein Rot-Schwarz-Baum hat des weiteren folgende Eigenschaften:<br><br>
*
* - Jeder Knoten ist entweder rot oder schwarz.<br>
* - Alle Blaetter sind NIL-Knoten und sind schwarz.<br>
* - Wenn ein Knoten ROT ist, sind seine beiden Kinder schwarz.<br>
* - Jeder einfache Pfad von der Wurzel bis zu einem Blatt enthaelt die
* gleiche Anzahl von schwarzen Knoten.<br><br>
*
* Die Anzahl der schwarzen Knoten eines Pfades von der Wurzel bis zu einem
* Blatt heisst die schwarze Hoehe eines Baumes.<br>
@version 0.1a Release 12.12.1999
@author Jens Herold
@author Andre Eulenberger
@author Robert Hoehndorf
****************************************************************************/
public class rbtree {
/***************************************************************************
* Die Konstante BLACK ist vom Typ Boolean. Da sie nicht von dem
* Endprogramm benutzt werden soll, ist die Konstante private.
* Die Konstante BLACK besitzt den Boolean Wert true.
***************************************************************************/
private final static boolean BLACK = true;
/****************************************************************************
* Die Konstante RED ist vom Typ Boolean. Da sie nicht von dem
* Endprogramm benutzt werden soll, ist die Konstante private.
* Die Konstante RED besitzt den Boolean Wert false.
****************************************************************************/
private final static boolean RED = false;
/****************************************************************************
* Dies ist die Wurzel des gesamten Rot-Schwarz Baumes. Die Wurzel ist vom
* Typ rbelement. Auch die Wurzel ist private, weil der Anwender die Klasse
* rbtree ausschliesslich zum Speichern von Daten benutzen soll, also zur
* Loesung eine Problems, und dazu keine Informationen zu der eigentlichen
* Wurzel benoetigt.
*****************************************************************************/
private rbelement root;
/****************************************************************************
* Die Konstante NIL ist ein leeres Element. Leere Elemente sind BLACK per Def.
*****************************************************************************/
private final static rbelement NIL = new rbelement(null,null,null,BLACK,0);
rbtree () {
root=NIL;
}
/***********************************************************************
* Die Methode rotateLeft erwartet als Parameter ein rbelement.
* Die Methode rotateLeft ist private, da sie ausschliesslich
* zum Ausgleichen des Baum im Anschluss an Einfuegen oder Loeschen
* benutzt wird.
* In dieser Methode wird ein Teil des Baumes nach links rotiert.<br><br>
*<!-
* o Parent<br>
* / \<br>
* o X o<br>
* / \<br>
* o o Y<br>
* / \<br>
* o Z o<br><br>
*
* wird zu:<br><br>
*
* o Parent<br>
* / \<br>
* o Y o<br>
* / \<br>
* o X o<br>
* / \<br>
* o o Z<br><br>
*
*
* So, jetzt ist die Rotation nach links um das Element x abgeschlossen.
* ->
************************************************************************/
private void rotateLeft (rbelement x) {
rbelement y = x.right; // y ist rechter Sohn von x
x.right=y.left;
if (y.left!=NIL) y.left.parent = x;
if (y!=NIL) y.parent=x.parent;
if (x.parent!=NIL && x.parent!=null) {
if (x==x.parent.left)
x.parent.left=y;
else
x.parent.right=y;
} else {
root = y;
}
y.left=x;
if (x!=NIL) x.parent=y;
}
/***********************************************************************
* Name: rotateRight<br>
* Datum: 11.12.1999<br>
* Die Methode rotateRight erwartet als Parameter ein rbelement (x).
* Die Methode rotateRight ist private, da sie ausschliesslich
* zum Ausgleichen des Baum im Anschluss an Einfuegen und Loeschen
* benutzt wird.
* In dieser Methode wird ein Teil des Baumes nach rechts rotiert.
*
* Die Funktion entspricht der Rotation nach links, also siehe rotateLeft
************************************************************************/
private void rotateRight (rbelement x) {
rbelement y = x.left;
x.left=y.right;
if (y.right!=NIL) y.right.parent=x;
if (y!=NIL) y.parent=x.parent;
if (x.parent!=NIL && x.parent!=null) {
if (x==x.parent.right)
x.parent.right=y;
else
x.parent.left=y;
} else {
root=y;
}
y.right=x;
if (x!=NIL)
x.parent=y;
} // Ende der Funktion
/**********************************************************************
* Datum: 11.12.1999<br>
* Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem
* Einfuegen eines Elements.<br>
*
* Eine genaue Beschreibung des Algorythmus ist in der Projekt-
* dokumentation zu finden.
***********************************************************************/
private void insertFixup(rbelement x) {
while ((x!=root) && (x.parent.color==RED)) {
if (x.parent==x.parent.parent.left) {
rbelement y=x.parent.parent.right;
if (y.color==RED) {
x.parent.color=BLACK; // Fall 3.1
y.color=BLACK; // Fall 3.1
x.parent.parent.color=RED; // Fall 3.1
x=x.parent.parent; // Fall 3.1
} else {
/* Das hier ist Fall 3.3. Der Fall 3.3 ist dem Fall 3.2 sehr aehnlich,
* und wir koennen ihn einfach umwandeln in einen Fall 3.2 -> siehe
* detaillierte Beschreibung des Projekts. Wir aktualisieren x
* und rotieren x nach links.
*/
if (x==x.parent.right) {
x=x.parent; // Fall 3.3
rotateLeft(x); // Fall 3.3
}
x.parent.color=BLACK; // Fall 3.2
x.parent.parent.color=RED; // Fall 3.2
rotateRight(x.parent.parent); // Fall 3.2
}
} else {
rbelement y = x.parent.parent.left;
if (y.color==RED) {
x.parent.color=BLACK; // Fall 4.1
y.color=BLACK; // Fall 4.1
x.parent.parent.color=RED; // Fall 4.1
x=x.parent.parent; // Fall 4.1
} else {
if (x==x.parent.left) {
/* Das hier ist Fall 4.3. Der Fall 4.3 ist dem Fall 4.2 sehr aehnlich,
* und wir koennen ihn einfach umwandeln in einen Fall 4.2 -> siehe
* detaillierte Beschreibung des Projekts. Wir aktualisieren x
* und rotieren x nach rechts.
*/
x=x.parent; // Fall 4.3
rotateRight(x); // Fall 4.3
}
x.parent.color=BLACK; // Fall 4.2
x.parent.parent.color=RED; // Fall 4.2
rotateLeft(x.parent.parent); // Fall 4.2
}
}
}
/* An dieser Stelle nehmen wir eine Vereinfachung vor. Es gibt Faelle, in denen
* die Wurzel einbezogen werden muss. Beispiel:
* <!-
* o Wurzel (Rot)
* / \
* Knoten x (rot) o N il
* / \
* N il N il
* ->
* Angenommen, der Knoten x wurde angefuegt. Wenn wir in dieser Situtation die
* Schleife durchlaufen lassen, erhalten wir eine NullPointerException.
* Die Wurzel eines Rot-Schwarz Baumes kann ohne Beeintraechtigung der
* Invariante schwarz verfaerbt werden, da dies die Anzahl der schwarzen
* Knoten auf JEDEM Pfad um eins erhoeht.
*/
root.color=BLACK;
} // Ende der Funktion insertFixup
/**********************************************************************
* Datum: 11.12.1999<br>
* Diese Methode fuegt ein Element ein. Die Methode ist public und muss
* zum Einfuegen in den Baum benutzt werden.
* @return <p>true wenn der Schluessel erfolgreich eingefuegt wurde.<br>
* <p>false wenn der Schluessel bereits vorhanden ist.
***********************************************************************/
public boolean insert (int key) {
rbelement current,parent,x;
x=new rbelement();
current=root;
parent=null;
while (current!=NIL) { // binaere Suche
if (key==current.searchkey)
return false;
parent=current;
current=(key<current.searchkey)?current.left:current.right;
}
x.parent=parent; // Der anzufuegende Knoten
// ist rot und hat zwei
// leere Unterbaeume.
x.left=NIL;
x.right=NIL;
x.color=RED;
x.searchkey=key;
if (parent!=null) { // Bestimmen, wo angefuegt
// werden soll.
if (key<parent.searchkey)
parent.left=x;
else
parent.right=x;
} else {
root=x;
}
insertFixup(x);
return true;
} // End of insert
/**********************************************************************
* Datum: 11.12.1999<br>
* Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem
* Loeschen eines Elements.
***********************************************************************/
private void deleteFixup(rbelement x) {
while ((x!=root) && (x.color==BLACK)) {
if (x==x.parent.left) {
rbelement u=x.parent.right;
if (u.color==RED) {
/** Fall 2 ! Diesen wandeln wir sofort in einen Fall 3. */
u.color=BLACK;
x.parent.color=RED;
rotateLeft(x.parent);
u=x.parent.right;
}
if ((u.left.color==BLACK) && (u.right.color==BLACK)) {
/** Fall 3.1 !
* Es gibt die Moeglichkeit, dass der Vorgaengerknoten von x rot
* ist. In diesem Fall terminiert der Algorythmus. Im anderen Fall
* wurde das doppelte Schwarz (siehe Dokumentation) um eins nach
* oben bewegt und der Algorythmus wird wiederholt.
* Falls bereits der Fall 2 vorher eintrat, wird die while-Schleife
* terminieren, da an dieser Stelle noch nicht - wie im Algorythmus
* gefordert, der Vorgaengerknoten von u schwarz verfaerbt wird.
* Wird der Algorythmus jetzt fortgesetzt (wenn der Vorgaengerknoten
* von u noch rot ist), so terminiert die while-Schleife. Am Ende
* dieser Methode erst wird die Farbe des Vorgaengerknoten wie
* gefordert schwarz gesetzt. */
u.color=RED;
x=x.parent;
} else {
if (u.right.color==BLACK) {
/** Fall 3.2 !
* Diesen Fall verwandeln wir in den Fall 3.3. */
u.left.color=BLACK;
u.color=RED;
rotateRight(u);
u=x.parent.right;
}
/** Fall 3.3 ! */
u.color=x.parent.color;
x.parent.color=BLACK;
u.right.color=BLACK;
rotateLeft(x.parent);
x=root;
}
} else {
/** Ab hier beginnen die symetrischen Faelle. Der Quellcode ist gleich,
* abgesehen davon, dass left und right, also die Seiten links und rechts
* vertauscht sind. */
rbelement u=x.parent.left;
if (u.color==RED) {
/** Fall 2 ! Hier wird der Fall 2 in einen Fall 4 umgewandelt! */
u.color=BLACK;
x.parent.color=RED;
rotateRight(x.parent);
u=x.parent.left;
}
if ((u.right.color==BLACK) && (u.left.color==BLACK)) {
u.color=RED;
x=x.parent;
} else {
if (u.left.color==BLACK) {
u.right.color=BLACK;
u.color=RED;
rotateLeft(u);
u=x.parent.left;
}
u.color=x.parent.color;
x.parent.color=BLACK;
u.left.color=BLACK;
rotateRight(x.parent);
x=root;
}
}
}
/** An dieser Stelle wird x nach schwarz verfaerbt. Einen Nutzen haben
* wir bereits an der Stelle des Falles 3.1 erlaeutert.
* Die while-Schleife terminiert nun ausschliesslich durch den
* bereits erlaeuterten Fall 3.1 und den Fall 3.3. Am Ende der
* Implementierung des Falles 3.3 (und der symmetrische Fall)
* wird x gleich der Wurzel gesetzt. Im Fall 3.1 ist damit die
* Wurzel des ausgeglichenen Teilbaumes schwarz, im Fall 3.3 die
* Wurzel des gesamten Baumes. Da die Wurzel des gesamten Baumes
* vor dem Loeschen schwarz war (siehe Einfuegen), ist sie auch
* nach dem Loeschen in jedem Fall schwarz. */
x.color=BLACK;
} // End of function deleteFixup
/**********************************************************************
* Datum: 11.12.1999<br>
* Diese Methode loescht ein Element. Die Methode ist public und muss
* zum Loeschen benutzt werden.
* @return <p>true wenn der Schluessel erfolgreich geloescht wurde.<br>
* <p>false wenn der Schluessel nicht vorhanden ist.
***********************************************************************/
public boolean delete(int key) {
rbelement x,y,z;
z=root;
while (z!=NIL) { // Standard binaere Suche
if (key==z.searchkey)
break; // z ist das Element, das wir
// loeschen.
else
z=(key<z.searchkey)?z.left:z.right;
}
if (z==NIL) return false; // Den Schluessel gibt es nicht
// in unserem Baum.
if ((z.left==NIL) || (z.right==NIL)) {
y=z;
} else {
y=z.right;
while (y.left!=NIL) y=y.left; // Nachfolger von z
}
if (y.left!=NIL)
x=y.left;
else
x=y.right;
if (x!=NIL)
x.parent=y.parent;
if (y.parent!=null)
if (y==y.parent.left)
y.parent.left=x;
else
y.parent.right=x;
else
root=x;
if (y!=z)
z.searchkey=y.searchkey;
if (y.color==BLACK)
deleteFixup(x);
return true;
} // End of funtion delete
/**********************************************************************
* Datum: 11.12.1999<br>
* Die Methode find erwartet als Parameter einen Suchschluessel.
* Die Methode ist public und muss zum Finden bzw. auslesen von Daten
* benutzt werden.
*
* @return Liefert den Suchschluessel zurueck.
***********************************************************************/
public int find(int key) {
/** Hier ist eine einfache binaere Suche implementiert. */
rbelement current=root;
while (current!=NIL) {
if (key==current.searchkey) {
return key;
} else {
if (key<current.searchkey)
current=current.left;
else
current=current.right;
}
}
return 0;
} // Ende von find
public void draw() {
AVLDraw(root,5);
} // Ende von find
/***********************************************************************
* Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken
* in dem Quelltext und braucht nicht beachtet zu werden.
***********************************************************************/
private void AVLDraw (rbelement e,int t) {
String s = new String();
if (e!=NIL) {
AVLDraw(e.right,t+1);
for (int i=0;i<(t*4+1);i++)
s=s+" ";
System.out.println(" "+s+tiefe(e)+" "+e.color+": "+e.searchkey);
AVLDraw(e.left,t+1);
}
}
/***********************************************************************
* Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken
* in dem Quelltext und braucht nicht beachtet zu werden.
***********************************************************************/
private int tiefe(rbelement e) {
if ( e==NIL ) {
return 0;
}
else {
if ( tiefe(e.left) >= tiefe(e.right) )
return tiefe(e.left)+1;
else
return tiefe(e.right)+1;
}
}
}