java.lang.Object
|
+--rbtree
------------------------------------
public class rbtree
extends Object
Name: Rot-Schwarz Baum
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.
Erste Version: 11.12.1999 Letzte Aenderung: 2.1.1999
Um die Klasse rbtree zu benutzen, muss ein Objekt der Klasse erstellt
werden. Die einzelnen Methoden werden an gegebener Stelle beschrieben.
Bemerkung: Derzeit haelt der Rot-Schwarz Baum keine Daten (Objekte), sondern
nur Elemente von Typ Integer, die gleichzeitig Suchschluessel sind.
Invariante
==========
Ein Rot-Schwarz-Baum ist ein Spezialfall eines binaeren Suchbaums. Fuer
einen binaeren Suchbaum muss folgendes gelten:
- Jeder Knoten hat hoechstens 2 Soehne.
- Jeder Knoten hat einen bestimmten Wert (Sortierkriterium).
- Wenn k der Wert eines gegebenen Knoten ist, dann gilt:
- alle Knoten im linken Unterbaum des Knoten haben einen kleineren Suchindex
als k
- alle Knoten im rechten Unterbaum des Knoten haben groessere Werte als k
- Die "Spitze" des Baumes ist die Wurzel (root).
Ein Rot-Schwarz-Baum hat des weiteren folgende Eigenschaften:
- Jeder Knoten ist entweder rot oder schwarz.
- Alle Blaetter sind NIL-Knoten und sind schwarz.
- Wenn ein Knoten ROT ist, sind seine beiden Kinder schwarz.
- Jeder einfache Pfad von der Wurzel bis zu einem Blatt enthaelt die gleiche
Anzahl von schwarzen Knoten.
Die Anzahl der schwarzen Knoten eines Pfades von der Wurzel bis zu einem
Blatt heisst die schwarze Hoehe eines Baumes.
Version:
0.1a Release 12.12.1999
Author:
Jens Herold, Andre Eulenberger, Robert Hoehndorf
------------------------------------
Variable Index
o BLACK
Die Konstante BLACK ist vom Typ Boolean.
o NIL
Die Konstante NIL ist ein leeres Element.
o RED
Die Konstante RED ist vom Typ Boolean.
o root
Dies ist die Wurzel des gesamten Rot-Schwarz Baumes.
Constructor Index
o rbtree()
Method Index
o AVLDraw(rbelement, int)
Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken in dem
Quelltext und braucht nicht beachtet zu werden.
o delete(int)
Datum: 11.12.1999
Diese Methode loescht ein Element.
o deleteFixup(rbelement)
Datum: 11.12.1999
Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem Loeschen
eines Elements.
o draw()
o find(int)
Datum: 11.12.1999
Die Methode find erwartet als Parameter einen Suchschluessel.
o insert(int)
Datum: 11.12.1999
Diese Methode fuegt ein Element ein.
o insertFixup(rbelement)
Datum: 11.12.1999
Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem
Einfuegen eines Elements.
Eine genaue Beschreibung des Algorythmus ist in der Projekt-
dokumentation zu finden.
o rotateLeft(rbelement)
Die Methode rotateLeft erwartet als Parameter ein rbelement.
o rotateRight(rbelement)
Name: rotateRight
Datum: 11.12.1999
Die Methode rotateRight erwartet als Parameter ein rbelement (x).
o tiefe(rbelement)
Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken in dem
Quelltext und braucht nicht beachtet zu werden.
Variables
o BLACK
private static final boolean BLACK
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.
o RED
private static final boolean RED
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.
o root
private rbelement root
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.
o NIL
private static final rbelement NIL
Die Konstante NIL ist ein leeres Element. Leere Elemente sind BLACK per
Def.
Constructors
o rbtree
rbtree()
Methods
o rotateLeft
private void rotateLeft(rbelement x)
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.
o rotateRight
private void rotateRight(rbelement x)
Name: rotateRight
Datum: 11.12.1999
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
o insertFixup
private void insertFixup(rbelement x)
Datum: 11.12.1999
Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem
Einfuegen eines Elements.
Eine genaue Beschreibung des Algorythmus ist in der Projekt-
dokumentation zu finden.
o insert
public boolean insert(int key)
Datum: 11.12.1999
Diese Methode fuegt ein Element ein. Die Methode ist public und muss
zum Einfuegen in den Baum benutzt werden.
Returns:
true wenn der Schluessel erfolgreich eingefuegt wurde.
false wenn der Schluessel bereits vorhanden ist.
o deleteFixup
private void deleteFixup(rbelement x)
Datum: 11.12.1999
Diese Methode erhaelt die Rot-Schwarz-Baum Invariante nach dem Loeschen
eines Elements.
o delete
public boolean delete(int key)
Datum: 11.12.1999
Diese Methode loescht ein Element. Die Methode ist public und muss zum
Loeschen benutzt werden.
Returns:
true wenn der Schluessel erfolgreich geloescht wurde.
false wenn der Schluessel nicht vorhanden ist.
o find
public int find(int key)
Datum: 11.12.1999
Die Methode find erwartet als Parameter einen Suchschluessel. Die
Methode ist public und muss zum Finden bzw. auslesen von Daten benutzt
werden.
Returns:
Liefert den Suchschluessel zurueck.
o draw
public void draw()
o AVLDraw
private void AVLDraw(rbelement e,
int t)
Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken in dem
Quelltext und braucht nicht beachtet zu werden.
o tiefe
private int tiefe(rbelement e)
Diese Methode befindet sich ausschliesslich zu Debugging-Zwecken in dem
Quelltext und braucht nicht beachtet zu werden.