Rot-Schwarz-Bäume Java

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

Gansa

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:
mihe7

mihe7

Es wird in der LinksRotation Methode verschluckt, aber ich verstehe nicht warum.
Schauen wir mal:
Java:
    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;
    }
In der dritten Zeile ersetzt Du das linke Kind von x - sofern da vorher eines war, ist es weg.
 
G

Gansa

Schauen wir mal:
Java:
    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;
    }
In der dritten Zeile ersetzt Du das linke Kind von x - sofern da vorher eines war, ist es weg.
Okay danke jetzt hast geklappt. Aber jetzt wurde die 46 als Wurzel genommen, also mein Baum wurde nicht wie oben im Kommentar erstellt :/
 
G

Gansa

Was hast Du denn geändert?
habe es als Kommentar im code geschrieben was ich geändert habe,
davor stand bei mir

h.rechtesKind = h.linkesKind;

aber jetzt wird eben die 46 als Wurzel genommen ..
Java:
   public Knoten linksRotation(Knoten h) {
        Knoten x = h.rechtesKind;
        h.rechtesKind = x.linkesKind; //hier stand davor  h.rechtesKind = h.linkesKind;
        x.linkesKind = h;
        x.farbe = h.farbe;
        h.farbe = ROT;
        return x;
    }
 
G

Gansa

Äh:

bezog sich auf x.linkesKind = h :)


Nachtrag: Vergiss es.
Kannst du mir bei meinem zweiten Problem helfen? warum die 46 auf einmal die Wurzel wird, obwohl es so aussehen sollte

Java:
/* Let us create following BST
      35
   /     \
  9      57
 /  \    /  \
        46  68
       / \
      45  50

 */
Alle red black tree simulationen im Netz geben mir genau so einen tree, was ich per Hand auch so aufmalen würde, aber mein Code sagt das 46 die Wurzel sein müsse, ich verstehe nicht was das Problem ist.
 
mihe7

mihe7

Vielleicht hilft Dir ja mal eine Ausgabe, nach jedem Einfügen:
Code:
[35,0,true]lr
[35,0,true]r[9,1,true]lr
[35,0,true][50,2,false]lr[9,1,false]lr
[35,0,true][57,3,false]r[50,2,true]lr[9,1,false]lr
[57,3,true][68,4,false]lr[35,0,true][50,2,false]lr[9,1,false]lr
[57,3,true][68,4,false]lr[35,0,true][50,2,false]r[43,5,true]lr[9,1,false]lr
[46,6,true][57,3,false][68,4,false]lr[50,2,false]lr[35,0,false][43,5,false]lr[9,1,false]lr
Darstellung: [key,wert,farbe] - inorder (Wurzel, links, rechts), ein l steht, wenn der linke Kindknoten nicht vorhanden ist, analog r für den fehlenden rechten Kindknoten.

Da fällt mir spontan mal auf, dass die zweite Zeile
Code:
  35
  /
 9
beide Knoten als rot anzeigt... Die dritte Zeile eine falsche Reihenfolge hat:
Code:
  35
 /  \
50   9
 
G

Gansa

Vielleicht hilft Dir ja mal eine Ausgabe, nach jedem Einfügen:
Code:
[35,0,true]lr
[35,0,true]r[9,1,true]lr
[35,0,true][50,2,false]lr[9,1,false]lr
[35,0,true][57,3,false]r[50,2,true]lr[9,1,false]lr
[57,3,true][68,4,false]lr[35,0,true][50,2,false]lr[9,1,false]lr
[57,3,true][68,4,false]lr[35,0,true][50,2,false]r[43,5,true]lr[9,1,false]lr
[46,6,true][57,3,false][68,4,false]lr[50,2,false]lr[35,0,false][43,5,false]lr[9,1,false]lr
Darstellung: [key,wert,farbe] - inorder (Wurzel, links, rechts), ein l steht, wenn der linke Kindknoten nicht vorhanden ist, analog r für den fehlenden rechten Kindknoten.

Da fällt mir spontan mal auf, dass die zweite Zeile
Code:
  35
  /
9
beide Knoten als rot anzeigt... Die dritte Zeile eine falsche Reihenfolge hat:
Code:
  35
/  \
50   9
Hey ich wollte dich noch fragen wie du so eine schöne Ausgabe hinbekommen hast. Ich bekomme nur die werte und die Farbe auf die Reihe aber ob es ein linkes oder rechtes Kind ist, das konnte ich bis jetzt nicht umsetzen. Habe es versucht aber da ich nur ein System.out habe, kann Ich schlecht lk oder rk rein schreiben, das das abwechselnd ausgegeben wird. Meine print methode sieht bis jetzt so aus:

Java:
    public void inorder() {
        System.out.println("Farbe der Wurzel: "+ wurzel.key + " " + wurzel.farbe);
        inorderRec(wurzel);

    }

    // Durchlaufen des BST
    void inorderRec(Knoten wurzel) {
        if (wurzel != null) {

            inorderRec(wurzel.linkesKind);
            System.out.println(wurzel.key + " " + wurzel.farbe);
            inorderRec(wurzel.rechtesKind);

        }
    }


}
 
mihe7

mihe7

Hey ich wollte dich noch fragen wie du so eine schöne Ausgabe hinbekommen hast.
Naja, schön ist das nicht:
Java:
    public String toString() {
        StringBuilder b = new StringBuilder();
        if (wurzel == null) b.append("leer");
        else {
            java.util.Stack<Knoten> stack = new java.util.Stack<>();
            stack.push(wurzel);
            while (!stack.isEmpty()) {
                Knoten w = stack.pop();
                b.append('[').append(w.key).append(',').append(w.wert)
                    .append(',').append(w.farbe).append(']');
                if (w.linkesKind != null) {
                    stack.push(w.linkesKind);
                } else b.append("l");
                if (w.rechtesKind != null) {
                    stack.push(w.rechtesKind);
                } else b.append("r");
            }
        }
        return b.toString();

    }
 
G

Gansa

Naja, schön ist das nicht:
Java:
    public String toString() {
        StringBuilder b = new StringBuilder();
        if (wurzel == null) b.append("leer");
        else {
            java.util.Stack<Knoten> stack = new java.util.Stack<>();
            stack.push(wurzel);
            while (!stack.isEmpty()) {
                Knoten w = stack.pop();
                b.append('[').append(w.key).append(',').append(w.wert)
                    .append(',').append(w.farbe).append(']');
                if (w.linkesKind != null) {
                    stack.push(w.linkesKind);
                } else b.append("l");
                if (w.rechtesKind != null) {
                    stack.push(w.rechtesKind);
                } else b.append("r");
            }
        }
        return b.toString();

    }
Danke!
 
Thema: 

Rot-Schwarz-Bäume Java

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben