rotateLeft implementierung

L

lenaxx7

Mitglied
Kann mir einer weiterhelfen? Möchte eine linksrotation um die Wurzel im Suchbaum implementieren, das scheint aber so nicht zu stimmen.
Java:
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();
        }               
    }
 
kneitzel

kneitzel

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

Java:
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Unterschied zwischen List und LinkedList implementierung? Allgemeine Java-Themen 15
boschl2000 Springerproblem-Implementierung funktioniert nicht richtig Allgemeine Java-Themen 1
R In der Ausgabe sollte anstelle des obersten Sterns ein "+" stehen nur scheitere ich bei der Implementierung Allgemeine Java-Themen 9
D Input/Output Implementierung eines CommandHandlers/Parsers für viele Eingaben Allgemeine Java-Themen 26
Stonie Prüfen von direkter Implementierung eines Interfaces Allgemeine Java-Themen 7
S Mutable objects und Implementierung von ChangeEvents Allgemeine Java-Themen 5
W Queue Implementierung Allgemeine Java-Themen 6
C Ein Iterator ist eine Implementierung des Interface Iterable? Allgemeine Java-Themen 2
F Implementierung von Teilprogrammen [Java|Python] Allgemeine Java-Themen 7
I TimSort - Sortieralgorithmus - Erklärung und Pseudocode - Implementierung Allgemeine Java-Themen 2
L Implementierung eines AVT-Baums Allgemeine Java-Themen 2
ruutaiokwu burstsort-implementierung in java? Allgemeine Java-Themen 2
D Implementierung einer Mehrsprachigkeit, wichtig ? Allgemeine Java-Themen 5
D Implementierung einer Rechteverwaltung Allgemeine Java-Themen 2
A Implementierung eines Algorithmus (Farthest Insertion zur Lösung des TSP) in O(n²) Allgemeine Java-Themen 2
R "Countdown" Implementierung Allgemeine Java-Themen 5
K A*-Implementierung flexibler machen Allgemeine Java-Themen 4
J Java-Implementierung diverser Beziehungen zwischen Klassen bzw. Objekten Allgemeine Java-Themen 2
S BlueJ Cäsar-Implementierung Allgemeine Java-Themen 6
S Implementierung Programmneustart Allgemeine Java-Themen 10
R Implementierung eines Interface durch 2 verschiedene Klassen Allgemeine Java-Themen 6
G Implementierung einer Kommunikation Allgemeine Java-Themen 7
S Implementierung einer PluginArchitektur Allgemeine Java-Themen 5
A OOP: Überschreiben/Implementierung von Methoden Allgemeine Java-Themen 5
K Objekt einer konkreten Implementierung eines Interfaces durch übergebenen String Allgemeine Java-Themen 2
R Intervall-Implementierung mit selbstgebauter LinkedList Allgemeine Java-Themen 7
J Best Practice für implementierung von equals(...) Allgemeine Java-Themen 7
Kr0e Eigene RMI Implementierung Allgemeine Java-Themen 3
V Wie finde ich die konkrete Implementierung? Allgemeine Java-Themen 8
G Implementierung vom AKS-Test Allgemeine Java-Themen 11
R software implementierung Allgemeine Java-Themen 3
N Observer/Observable der JAVA-API od. eigene Implementierung Allgemeine Java-Themen 2
K Design / Implementierung Allgemeine Java-Themen 5
B jre browser implementierung ? Allgemeine Java-Themen 4
B Elegantere Lösung bei der Implementierung eines Interfaces Allgemeine Java-Themen 2
G Klasse Queue Implementierung in Java Allgemeine Java-Themen 4
G Eigene PrintService Implementierung. Allgemeine Java-Themen 5

Ähnliche Java Themen


Oben