Rot-Schwarz-Baum

Gansa

Aktives Mitglied
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

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

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

fhoffmann

Top Contributor
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:
K

kneitzel

Gast
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?
 
K

kneitzel

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

Gansa

Aktives Mitglied
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!
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Rot-Schwarz-Baum min und max-Tiefe Java Basics - Anfänger-Themen 1
T Rot-schwarz Baum Problem Java Basics - Anfänger-Themen 3
G Rot-Schwarz-Bäume Java Java Basics - Anfänger-Themen 10
A BufferedImage zeigt nur schwarz Java Basics - Anfänger-Themen 3
M Rot Schwarz Bäume, ausführen? Java Basics - Anfänger-Themen 6
N Erste Schritte HSV color space - schwarz und weiß nur anhand von Saturation oder Multiplikator ermitteln Java Basics - Anfänger-Themen 14
B Theorie Rot-Schwarz-Bäume Java Basics - Anfänger-Themen 2
S JFrame ist nicht schwarz Java Basics - Anfänger-Themen 5
J Frame bleibt schwarz beim Laden Java Basics - Anfänger-Themen 11
B Durchsichtige Images werden beim kopieren schwarz Java Basics - Anfänger-Themen 21
G eclipse Konsole schwarz Java Basics - Anfänger-Themen 4
D spezifische Knoten in einem Baum zählen Java Basics - Anfänger-Themen 9
HelpInneed Baum ausgeben (aber mal anders) Java Basics - Anfänger-Themen 3
G AVL-Baum Java Basics - Anfänger-Themen 1
L Baum aus Integer Liste erstellen Java Basics - Anfänger-Themen 0
CptK Interface Baum visualisieren Java Basics - Anfänger-Themen 37
CptK Best Practice Merge-Sort als Baum darstellen Java Basics - Anfänger-Themen 3
E Baum pfadweise durchlaufen Java Basics - Anfänger-Themen 11
O Naives links rechts einfügen in ADT Baum Java Basics - Anfänger-Themen 8
L Traversierungsverfahren Baum: LevelOrder Java Basics - Anfänger-Themen 17
L Rekursion im Baum Java Basics - Anfänger-Themen 9
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L B+Baum innere Knoten erstellen Java Basics - Anfänger-Themen 3
D B-Baum einfügen und löschen Java Basics - Anfänger-Themen 2
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
D Werte AVL-Baum löschen Java Basics - Anfänger-Themen 2
M Binären Baum Kinder setzen Java Basics - Anfänger-Themen 12
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 4
U 2-3-4 Baum Top-Down Java Basics - Anfänger-Themen 0
J Überprüfen, ob eine 2D Matrix ein Baum ist Java Basics - Anfänger-Themen 5
R Baum erzeugen Java Basics - Anfänger-Themen 61
B Baum Traversierung Postorder Java Basics - Anfänger-Themen 6
B OOP Über einen AVL-Baum iterieren (NullPointer) Java Basics - Anfänger-Themen 5
A Voller Baum Java Basics - Anfänger-Themen 7
S n-ärer Baum Java Basics - Anfänger-Themen 6
O Unterschied Baum <-> Automat Java Basics - Anfänger-Themen 2
K Tiefen- und Breitensuche beim Baum durch Stack und Warteschlange Java Basics - Anfänger-Themen 1
C kompletter baum Java Basics - Anfänger-Themen 2
M Collections Iterator und generischer Baum Java Basics - Anfänger-Themen 0
M Baum Code kurze frage ... Java Basics - Anfänger-Themen 6
D Ein Objekt in einem Baum finden und ausgeben. Java Basics - Anfänger-Themen 4
A min() Methode Baum Java Basics - Anfänger-Themen 1
J Baum rekursiv durchlaufen Java Basics - Anfänger-Themen 2
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
T Baum mit Turtle zeichnen Java Basics - Anfänger-Themen 2
Screen 2,4 Baum Frage Java Basics - Anfänger-Themen 6
A Rekursion in Baum und ArrayList als Rückgabe Java Basics - Anfänger-Themen 2
P Pythagoras Baum - Berechnung der Punkte Java Basics - Anfänger-Themen 9
C 2-3 Baum Java Basics - Anfänger-Themen 6
H Baum Java Basics - Anfänger-Themen 4
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
B Baum > Baum-Swing Java Basics - Anfänger-Themen 4
L eigenen Baum schreiben Java Basics - Anfänger-Themen 5
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
T Array in einen Baum zu überführen Java Basics - Anfänger-Themen 3
S Das reinschreiben einer Klasse in den Baum Java Basics - Anfänger-Themen 6
H B-Baum: Knoten Position als Parameter oder als Variable im Objekt? Java Basics - Anfänger-Themen 4
A Baum mit geometricfigur Werte Java Basics - Anfänger-Themen 6
D Datentypen Einfügen im RotSchwarz Baum Java Basics - Anfänger-Themen 2
F FileSystem in Baum darstellen/wurzel festlegen Java Basics - Anfänger-Themen 3
G List als Rückgabewert einer rekursiven Methode (Baum) Java Basics - Anfänger-Themen 3
I Baum graphisch darstellen Java Basics - Anfänger-Themen 2
P Binärer Baum mit Composite-Entwurfsmuster Java Basics - Anfänger-Themen 2
L Baum Swing AVL Java Basics - Anfänger-Themen 4
Binary.Coder 2-3-4 Baum vs. (2,4) Baum Java Basics - Anfänger-Themen 2
ModellbahnerTT Ab-Baum Applet Java Basics - Anfänger-Themen 3
P Baum-Menü in Java Java Basics - Anfänger-Themen 5
H Baum Java Basics - Anfänger-Themen 11
G AVL Baum Java Basics - Anfänger-Themen 20
J Baum spiegeln Java Basics - Anfänger-Themen 7
N 2-3 Baum, Einfügen Java Basics - Anfänger-Themen 5
G Rekursion mit Return - Baum durchlaufen Java Basics - Anfänger-Themen 4
G Baum Datenstruktur Java Basics - Anfänger-Themen 2
V Baum mit log n Aufwand für Einfügen und Löschen und. Java Basics - Anfänger-Themen 5
H Tiefensuche im binären Baum Java Basics - Anfänger-Themen 2
P Problem mit Darstellung im Baum Java Basics - Anfänger-Themen 4
G Binärer Baum Java Basics - Anfänger-Themen 3
M Binärer Baum Tiefe Java Basics - Anfänger-Themen 14
G universeller baum Java Basics - Anfänger-Themen 13
G Baum testen Java Basics - Anfänger-Themen 20
B Array To Baum Java Basics - Anfänger-Themen 2
B Baum to Array Java Basics - Anfänger-Themen 17
H Löschen in einem binären Baum führt zu einem StackOverflow Java Basics - Anfänger-Themen 2
L Binären Baum speichern Java Basics - Anfänger-Themen 6
R Pythagoras-Baum Java Basics - Anfänger-Themen 5
W Baum durchlaufen Java Basics - Anfänger-Themen 3
T binärer Baum Java Basics - Anfänger-Themen 3
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
P allg. Baum aus Liste Java Basics - Anfänger-Themen 2
J String in binären Baum umwandeln Java Basics - Anfänger-Themen 7
R binärer Baum Java Basics - Anfänger-Themen 2
F Abstrakte Klasse Baum Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben