rotateLeft implementierung

[lenaxx7]

Kann mir einer weiterhelfen? Möchte eine linksrotation um die Wurzel im Suchbaum implementieren, das scheint aber so nicht zu stimmen.

public void rotateLeft() {
        if(root == null) {
            return;
        }
        if(root.getRight() == null) {
            return;
        }
        SearchTreeNode<K, V> r = root.getRight();
        SearchTreeNode<K, V> right = root.getRight();
        SearchTreeNode<K, V> left = root.getLeft();
        SearchTreeNode<K, V> rl = right.getLeft();
        SearchTreeNode<K, V> rr = right.getRight();
        right = root; //rechtes Element wird zu root
        rr = root.getRight(); //rechtes Element von rechts rutsch hoch zu rechtes Element von root
        root = root.getLeft(); //root rutscht runter zu linkes Element von root
        if(rl != null) {
            rl = root.getRight();
        }
        if(left != null) {
            left = root.getLeft();
        }               
    }

 

[mihe7]

Du musst schon auch was setzen, nicht nur lesen.

 

[kneitzel]

Es bringt nichts, ständig neue Threads mit dem gleichen Thema auf zu machen. Da sinkt die Lust, sich mit Deinem Thema zu beschäftigen doch enorm.

Und generell ist meine Empfehlung bei sowas, sich das immer im Detail aufzuschreiben. Wo geht welcher Node hin, wie werden die Childs gesetzt? Wenn Du das einmal sauber aufgezeichnet hast, dann ist die Implementierung einfach.

Und bei den Zuweisungen machst Du natürlich einiges an "Sinnbefreiten", denn wenn Du rr erst etwas zuweist und dann sofort etwas anderes zuweist, dann ist die erste Zuweisung unnötig. Und das alles ist auch von den Zuweisungen her nicht wirklich verständlich:

right = root; //rechtes Element wird zu root

Den Kommentar verstehe ich so, dass das rechte Element zu root wird. Aber die Zuweisung speichert ja das Root Element im rechten Element....


Generell sind das ja Referenzen. Also sowas wie Adressen. Du schreibst Deine Adresse auf einen Zettel 8Also kopierst sie aus dem Personalausweis oder so).
Dann änderst Du auf diesem Zettel die Adresse.
==> Dadurch hat sich Deine Adresse auf dem Personalausweis doch nicht geändert. Lediglich auf dem Zettel steht eine andere Adresse.

Vorgehen kann nur sein:
a) alle Elemente, die Wichtig sind, merken.
b) dann alles setzen (Also setLeft / setRight). Dabei werden Werte, die Du Dir gemerkt hast, überschrieben.

Dann kennen wir den genauen Aufbau nicht. Was ist root? Du willst ja in der Regel mitten im Baum eine Drehung machen. Daher passt das alles nicht. Wenn Du in einer Variablen root den Knoten hast, an dem du drehen willst, bringt eine Zuweisung eines anderen Knoten nichts, denn auf diesen Knoten wird ja ggf. bereits verwiesen. Und diese Referenz müsstest Du ja auch ändern.
Die Lösung, die ich da kenne: Der Knoten bleibt an seiner Stelle, statt dessen wird nur der gespeicherte Wert vertauscht.