Hallo, ich habe versucht einen Rot-schwarz baum zu implenetieren und eigentlich sieht alles richtig aus denke ich .. Jedoch habe ich Probleme in der Main Methode, wenn ich zb die zahlen 7 5 4 3 9 einfügen möchte, klappt es nicht. Ich bin schon seit stunden dran und bekomme bald eine Macke .. Ich kopiere meinen ganzen Code mal rein, bin dankbar für jede Hilfe!
Java:
public class BST {
public static final boolean ROT = true; //1
public static final boolean SCHWARZ = false; //0
private Knoten wurzel;
public Integer findeIndex(Integer key) {
Knoten x = wurzel; //pointer zu aktuellem Knoten
while (x != null) {
int vergleich = key.compareTo(x.key);
if (vergleich < 0) {
x = x.linkesKind;
} else if (vergleich > 0) {
x = x.rechtesKind;
} else return x.wert;
}
return null; //key nicht gefunden
}
public void tauscheFarben(Knoten h) { //färbe h rot und Kinder schwarz
h.farbe = ROT;
h.linkesKind.farbe = SCHWARZ;
h.rechtesKind.farbe = SCHWARZ;
}
public Knoten put(Integer key, Integer wert){
wurzel = put(wurzel,key,wert);
return null;
}
public Knoten put(Knoten h, Integer key, Integer wert) {
if (h == null) {
Knoten knoten = new Knoten(key, wert, ROT);
}
int vergleich = key.compareTo(h.key);
if (vergleich < 0) {
h.linkesKind = put(h.linkesKind, key, wert);
} else if (vergleich > 0) {
h.rechtesKind = put(h.rechtesKind, key, wert);
} else h.wert = wert;
if (istRot(h.rechtesKind) && !istRot(h.linkesKind)) {
h = linksRotation(h);
}
if (istRot(h.linkesKind) && istRot(h.linkesKind.linkesKind)) {
h = rechtsRotation(h);
}
if (istRot(h.linkesKind) && istRot(h.rechtesKind)) {
tauscheFarben(h);
}
return h;
}
public Knoten linksRotation(Knoten h) {
Knoten x = h.rechtesKind; //tausche linkes und rechtes Kind
h.rechtesKind = h.linkesKind;
x.linkesKind = h;
x.farbe = h.farbe; //gebe rechtem Kind farbe von h
h.farbe = ROT; //gebe h farbe von rot
return x;
}
public Knoten rechtsRotation(Knoten h) {
Knoten x = h.linkesKind;
h.linkesKind = x.rechtesKind;
x.rechtesKind = h;
x.farbe = h.farbe;
h.farbe = ROT;
return x;
}
//Ist knoten rot? !null referenzen sind immer schwarz!
public boolean istRot(Knoten x) {
if (x == null) {
return false;
}
return x.farbe == ROT;
}
}
Java:
public class Knoten {
public Integer key;
public Integer wert;
public Knoten linkesKind, rechtesKind, eltern;
boolean farbe;
public Knoten(Integer key, Integer wert, boolean farbe) {
this.key = key;
this.wert = wert;
this.farbe = farbe;
}
}
Java:
public class Main {
public static void main (String [] args){
BST bst = new BST();
bst.put(7,99);
bst.put(5,99);
bst.put(4,99);
bst.put(3,99);
bst.put(9,99);
}
}