Anbei meine beiden Klassen Cnode und RbTree.
Kurz gesagt geht soweit alles, nur das beim Einfügen ab und an Knoten "verloren gehen". Ich hab jetzt schon über 2 Stunden nur den Fehler gesucht, aber nicht gefunden. Ich hoffe jmd von euch kann mir nochmal helfen :/.
Cnode.java
RbTree.java
Ich wäre für eure Hilfe echt Dankbar, schreibe in ein par Tagen eine Klausur und möchte mich nicht ewig hieran aufhalten müssen weil ich vor lauter Bäumen den Wald nimmer seh ;P.
In diesem Fall verschwindet das Element 20. oO
Grüsse an alle freaks da draussen
Kurz gesagt geht soweit alles, nur das beim Einfügen ab und an Knoten "verloren gehen". Ich hab jetzt schon über 2 Stunden nur den Fehler gesucht, aber nicht gefunden. Ich hoffe jmd von euch kann mir nochmal helfen :/.
Cnode.java
Java:
/**
* Klasse Cnode.java (colored node)
*
* @author Andreas Jenkuhn
* @version 0.1
* @date 20.März 2010
* @Repräsentiert einen Knoten im Rot-Schwarz Baum
*
* -----------------------------------------------------------------------------
* @KONSTRUKTOREN:
* Cnode() => erzeugt einen schwarzen nil-Knoten //
* Cnode(Object key) => erzeugt einen roten Knoten mit key=inhalt //
* Cnode(Object key, Object data) => erzeugt einen roten Knoten mit key und inhalt //
* -----------------------------------------------------------------------------
* @ATTRIBUTE (alle private):
* Cnode left, right => linkes, rechtes Kind des Knotens //
* boolean red, black => mit red!=black //
* Object key, data => Key und Inhalt des Knotens //
* -----------------------------------------------------------------------------
* @METHODEN:
* getKey() => return Object key //
* getData() => return Object data //
* setData(Object o) => set data //
* getLeft() => return linker Kindsknoten //
* setLeft(Cnode n) => set linker Kindsknoten //
* getRight() => return rechter Kindsknoten //
* setRight(Cnode n) => set rechter Kindsknoten //
* isRed() => return boolean red //
* isBlack() => return boolean black //
* getColor() => return String 'red' oder 'black' //
* isNil() => return boolean //
* toString() => return '(Black(key)-(data))'
* '(Red(key)-(data))'
* '[Black][nil]'
* -----------------------------------------------------------------------------
*/
public class Cnode {
private Cnode left,right;
private boolean red, black, nil;
private Object key, data;
/**
* Standardkonstruktor Cnode()
* erzeugt einen nil-Knoten
*/
public Cnode() {
this.nil = true;
setBlack();
}
/**
* Konstruktor Cnode(Object key)
*
* @param Object key - Schlüssel + Inhalt des neuen Knotens
*/
public Cnode(Object key) {
this(key,key); // erstelle Knoten mit key=data
}
/**
* Konstruktor CNode(Object key, Object data)
*
* @param Object key - Schlüssel des neuen Knotens
* @param Object data - Inhalt des neuen Knotens
*/
public Cnode(Object key, Object data) {
this.nil = false; // ist kein nil mehr
setRed(); // ist beim einfügen rot
this.key = key;
this.data = data;
left = new Cnode(); // nil als linkes Kind
right = new Cnode(); // nil als rechtes Kind
}
/**
* Methode getData()
*
* @return Object - übergibt Inhalt des Knoten
*/
public Object getData() {
return data;
}
/**
* Methode setData()
*
* @param Object data - Inhalt des Knoten als Object
*/
public void setData(Object data) {
this.data = data;
}
/**
* Methode getKey()
*
* @return Object - übergibt Key des Knoten
*/
public Object getKey() {
return key;
}
/**
* Methode getLeft()
*
* @return Cnode - übergibt linken Kindsknoten
*/
public Cnode getLeft() {
//kein nil? dann links weitergeben
if (!nil) return left;
// Falls man das Kind eines nil-Knoten erfragt
// wird zur Vermeidung einer null-Rückgabe
// ein nil-Knoten übergeben
else return new Cnode();
}
/**
* Methode setLeft()
*
* @param n - Knoten welcher linkes Kind werden soll
* @return boolean - ob anfügen erfolgerich war
*/
public boolean setLeft(Cnode n) {
// übergibt ob Knoten erfolgreich angehängt wurde
// Man kann nur an einen Knoten anhängen,
// wenn der aktuelle Knoten kein nil-Knoten ist
if (!nil) this.left = n; else return false;
return true;
}
/**
* Methode getRight()
*
* @return Cnode - übergibt rechten Kindsknoten
*/
public Cnode getRight() {
//kein nil? dann return rechtes Kind
if (!nil) return right;
// Falls man das Kind eines nil-Knoten erfragt
// wird zur Vermeidung einer null-Rückgabe
// ein nil-Knoten übergeben
else return new Cnode();
}
/**
* Methode setRight()
*
* @param n - Knoten welcher rechtes Kind werden soll
* @return boolean - ob anfügen erfolgerich war
*/
public boolean setRight(Cnode n) {
// übergibt ob Knoten erfolgreich angehängt wurde
// Man kann nur an einen Knoten anhängen,
// wenn der aktuelle Knoten kein nil-Knoten ist
if (!nil) this.right = n; else return false;
return true;
}
/**
* Methode setBlack()
*
* färbt Knoten schwarz
*/
public void setBlack() {
this.black = true;
this.red = false;
}
/**
* Methode setRed()
*
* färbt Knoten rot
*/
public void setRed() {
this.black = false;
this.red = true;
}
/**
* Methode isRed()
*
* @return boolean - Knoten rot?
*/
public boolean isRed() {
return red;
}
/**
* Methode isBlack()
*
* @return boolean - Knoten schwarz?
*/
public boolean isBlack() {
return black;
}
/**
* Methode isNil()
*
* @return boolean - ein nil-Knoten?
*/
public boolean isNil() {
return nil;
}
/**
* Methode getColor()
*
* @return String - Farbe des Knotens
*/
public String getColor() {
if (red) return "Red";
else return "Black";
}
/**
* Methode compareTo()
*
* @param Cnode n - Knoten mit dem verglichen werden soll
* @return -1, 0, 1 wenn kleiner, gleich, grösser
*/
public int compareTo(Object m) {
// // Vergleich nach keys der Knoten
// Object obj = m.getKey();
//
// System.out.println("m: " + m.getClass());
//
// System.out.println("m.getKey(): " + (m.getKey().getClass()));
return ((Comparable)key).compareTo((Comparable)(((Cnode)m).getKey()));
}
/**
* Methode toString()
*
* @return String - "(Farbe(Schlüssel)-(Inhalt))" bzw. "[nil]"
*/
public String toString() {
if (!nil) return "(" + getColor()
+ "(" + data.toString() + ")-"
+ "(" + key.toString() + "))";
else return "[" + getColor() + "][nil]";
}
}RbTree.java
Java:
public class RbTree {
private Cnode root;
private Cnode child, parent, grand, luncle, runcle, n;
private String temp;
private static RbTree tree;
public RbTree(Cnode root) {
this.root = root; // Am Anfang kommt die Wurzel
this.root.setBlack(); // und die ist schwarz
}
public boolean searchKey(Cnode tempNode, Object key) {
Cnode temptemp = new Cnode(key);
child = tempNode;
boolean found = false;
if (tempNode.getKey().equals(key))
return true;
else {
if ( temptemp.compareTo(tempNode) < 0) {
if (!child.getLeft().isNil())
found = searchKey(child.getLeft(), key);
} else { // k > tempRoot
if (!child.getRight().isNil())
found = searchKey(child.getRight(), key);
}
if (found) {
if ( tempNode.getLeft().equals(child) || tempNode.getRight().equals(child) ) {
parent = tempNode;
}
if ( tempNode.getLeft().equals(parent) ) {
grand = tempNode;
luncle = null;
runcle = tempNode.getRight();
}
if ( tempNode.getRight().equals(parent) ) {
grand = tempNode;
luncle = tempNode.getLeft();
runcle = null;
}
}
return found;
}
}
public boolean insert(Object key) {
n = new Cnode(key);
if (searchKey(root, key)) {
System.out.println("--> key gefunden!");
return false; // einfügen erfolglos da schon vorhanden
}
if ( n.compareTo(child) < 0 ) // n < child
child.setLeft(n); // d.h. n nach links
else
child.setRight(n);
while (repairNode(n)) repairNode(grand); // repariere rekursiv bis false kommt (false=keine Reperatur mehr)
return true;
}
private boolean repairNode(Cnode n) {
searchKey(root, n.getKey()); // initialisiere die Familienknoten
if ( case1(n) || case2(n) || case3(n) || case4(n) || case5(n) ) return true;
return false;
}
private boolean case1(Cnode n) { // Knoten ist Wurzel
if (n==root) {
root.setBlack();
return false; // da Wurzel, trotz Reparatur kein true mehr nötig
}
return false; // als Entscheidung zur weiteren Kontrolle eines Knoten
}
private boolean case2(Cnode n) { // Vaterknoten ist schwarz
return false;
// Fall 2 ist für einen schwarzen Vater. Dann ist nichts zu machen.
// Da alle Fälle eines roten Vaters woanders geprüft werden ist diese
// Methode "abstrakt" und returnt immer false und ist nur der Übersichtlichkeit
// halber enthalten.
}
private boolean case3(Cnode n) { // Vater & Onkel sind rot
if (parent!=null && parent.isRed() && runcle!=null && runcle.isRed()) {
parent.setBlack();
runcle.setBlack();
grand.setRed();
return true;
}
if (parent!=null && parent.isRed() && luncle!=null && luncle.isRed()) {
parent.setBlack();
luncle.setBlack();
grand.setRed();
return true;
}
return false;
}
private boolean case4(Cnode n) { // Kind ist rechts vom roten Vater und dieser links vom Opa. Kein oder schwarzer Onkel
if (parent!=null && runcle!=null && parent.isRed() && runcle.isBlack() && (n == parent.getRight()) ) {
rol(parent);
case5(parent);
return true;
} // Kind ist links vom roten Vater und dieser rechts vom Opa. Kein oder schwarzer Onkel
if (parent!=null && luncle!=null && parent.isRed() && luncle.isBlack() && (n == parent.getLeft()) ) {
ror(parent);
case5(parent);
return true;
}
return false;
}
private boolean case5(Cnode n){ // Kind ist links vom roten Vater und dieser ist rechts vom Opa. Kein oder schwarzer Onkel.
if (parent!=null && runcle!=null && parent.isRed() && runcle.isBlack() && (n == parent.getLeft())) {
ror(grand);
parent.setBlack();
grand.setRed();
return true;
} // Kind ist rechts vom roten Vater und dieser ist links vom Opa. Kein oder schwarzer Onkel.
if (parent!=null && luncle!=null && parent.isRed() && luncle.isBlack() && (n == parent.getRight())) {
rol(grand);
parent.setBlack();
grand.setRed();
return true;
}
return false;
}
// Linksrotation
private void rol(Cnode n) {
if (n==root) root = n.getRight();
Cnode oldRight;
oldRight = n.getRight();
n.setRight(oldRight.getRight().getLeft());
oldRight.setLeft(n);
}
// Rechtsrotation
private void ror(Cnode n) {
if (n==root) root = n.getLeft();
Cnode oldLeft;
oldLeft = n.getLeft();
n.setLeft(oldLeft.getLeft().getRight());
oldLeft.setRight(n);
}
public String toString() {
temp = "";
return (toString(root));
}
// Inorderausgabe des Baumes
public String toString(Cnode tempNode) {
if (!tempNode.getLeft().isNil())
toString(tempNode.getLeft());
temp += "\n" + tempNode.toString();
if (!tempNode.getRight().isNil())
toString(tempNode.getRight());
return temp;
}
// /////////////////////////////////////////////////////////////////////////////////////
private void start() {
// TESTS TESTS TESTS
System.out.println("1");
System.out.println(tree.toString());
tree.insert(new Integer(50));
System.out.println("root: " + root);
System.out.println(tree.toString());
tree.insert(new Integer(30));
System.out.println("root: " + root);
System.out.println(tree.toString());
tree.insert(new Integer(10));
System.out.println("root: " + root);
System.out.println(tree.toString());
System.out.println("2");
n = new Cnode(new Integer(20));
tree.insert(new Integer(20));
System.out.println("node: " + n);
System.out.println(tree.toString());
tree.insert(new Integer(60));
System.out.println("root: " + root);
System.out.println(tree.toString());
System.out.println("3");
System.out.println(searchKey(root, 20));
System.out.println("4");
}
public static void main(String[] args) {
tree = new RbTree(new Cnode(40));
try {
tree.start();
} catch (Exception e) {
System.out.println(e);
}
}
}Ich wäre für eure Hilfe echt Dankbar, schreibe in ein par Tagen eine Klausur und möchte mich nicht ewig hieran aufhalten müssen weil ich vor lauter Bäumen den Wald nimmer seh ;P.
In diesem Fall verschwindet das Element 20. oO
Grüsse an alle freaks da draussen
