Guten Tag, ich habe einen Rotschwarz baum Algorithmus geschrieben, welches eigentlich auch funktioniert. Aber ich habe vorhin gemerkt das bei der Zahlenfolge: (35,9,50,57,68,43,46) meine 50 einfach verschwindet. Also die 50 sollte rechts der 46 liegen, aber nope da steht einfach ein null. Es wird in der LinksRotation Methode verschluckt, aber ich verstehe nicht warum. Weil bei allen anderen Inputs funktioniert der Code richtig. Ich kopiere mal alles rein, danke schon mal wenn Ihr mir helfen könnt! (Und die Wurzel ist immer Rot, ich weiss auch nicht warum, mein Lehrer meint das dass auch geht und er möchte das so haben) so sollte es aussehen:
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) {
return 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)) { //wenn die kinder rot sind dann tausche farben
tauscheFarben(h);
}
return h;
}
public Knoten linksRotation(Knoten h) {
Knoten x = h.rechtesKind;
h.rechtesKind = h.linkesKind;
x.linkesKind = h;
x.farbe = h.farbe;
h.farbe = 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;
}
//prüfen ob Knoten rot ist, null referenzen sind immer schwarz
public boolean istRot(Knoten x) {
if (x == null) {
return false;
}
return x.farbe == ROT;
}
public class Knoten {
private Integer key;
private 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(35,0);
bst.put(9,1);
bst.put(50,2);
bst.put(57,3);
bst.put(68,4);
bst.put(43,5);
bst.put(46,6);
/* Let us create following BST
35
/ \
9 57
/ \ / \
46 68
/ \
45 50
*/
}
}
Zuletzt bearbeitet:
