Rot-Schwarz-Baum

Diskutiere Rot-Schwarz-Baum im Java Basics - Anfänger-Themen Bereich.
G

Gansa

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);


    }
}
 
X

Xyz1

Stimmt, ist mir auch gerade aufgefallen :D nur der Algorithmus wird beschrieben

/e Doch, eine C++ Implementierung ist angegeben...
 
F

fhoffmann

Java:
    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
    }
Was soll das sein?
Eine rekursive Funktion? Dann hast du sie falsch implementiert!
Hier findet kein rekursiver Aufruf statt.
Du gibst zwar x einen neuen Wert, aber du rufst die Funktion nicht für diesen neuen Wert auf.
 
Zuletzt bearbeitet:
J

JustNobody

Java:
    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
    }
Was soll das sein?
Eine rekursive Funktion? Dann hast du sie falsch implementiert!
Hier findet kein rekursiver Aufruf statt.
Du gibst zwar x einen neuen Wert, aber du rufst die Funktion nicht für diesen neuen Wert auf.
Aber für das Finden muss man es ja nicht zwingend rekursiv gestalten. Er hat es halt mit einer Schleife gelöst, die entweder abbricht, wenn er am Ende nichts mehr zum vergleichen hat oder eben durch return des Wertes, wenn er ihn gefunden hat.

Wo siehst du hier das Problem?
 
J

JustNobody

Ok, ich habe Deinen Code jetzt einmal ausgeführt. Wäre natürlich super gewesen, wenn Du geschrieben hättest, was genau nicht funktioniert....

Ein "klappt nicht" ist einfach keine Aussage bei so komplexen Dingen. Da kann man doch genau sagen:
Beim Einfügen des ersten Wertes bekomme ich eine NullPointerException in der Zeile:

Java:
    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);  // <== Hier kommt die NPE
        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;
    }
Und die if-Abfrage bei h==null macht so in der Form absolut nichts! Du erzeugst eine neue lokale Variable Knoten, welche aber dann sofort vergessen wird. Und dann rennt er in den vergleich mit h.key und da h null ist, kommt die NPE.

Wenn h null ist, willst Du doch einen neuen Knoten erzeugen und direkt zurück geben:
Java:
        if (h == null) {
            return new Knoten(key, wert, ROT);
        }
 
F

fhoffmann

Aber für das Finden muss man es ja nicht zwingend rekursiv gestalten. Er hat es halt mit einer Schleife gelöst, die entweder abbricht, wenn er am Ende nichts mehr zum vergleichen hat oder eben durch return des Wertes, wenn er ihn gefunden hat.

Wo siehst du hier das Problem?
Du hast recht - ich habe hier nicht genau genug hingeguckt,
 
G

Gansa

Ok, ich habe Deinen Code jetzt einmal ausgeführt. Wäre natürlich super gewesen, wenn Du geschrieben hättest, was genau nicht funktioniert....

Ein "klappt nicht" ist einfach keine Aussage bei so komplexen Dingen. Da kann man doch genau sagen:
Beim Einfügen des ersten Wertes bekomme ich eine NullPointerException in der Zeile:

Java:
    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);  // <== Hier kommt die NPE
        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;
    }
Und die if-Abfrage bei h==null macht so in der Form absolut nichts! Du erzeugst eine neue lokale Variable Knoten, welche aber dann sofort vergessen wird. Und dann rennt er in den vergleich mit h.key und da h null ist, kommt die NPE.

Wenn h null ist, willst Du doch einen neuen Knoten erzeugen und direkt zurück geben:
Java:
        if (h == null) {
            return new Knoten(key, wert, ROT);
        }
Vielen Dank!!!! Das war mir eine große Hilfe!
 
Thema: 

Rot-Schwarz-Baum

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben