immutabler AVLBaum rotieren

[HazlNut]

Servus liebe Programmiergemeinde!

Ich hoffe mal ich bin hier richtig mit meiner Frage ansonsten bitte ich das zu entschuldigen und mir mitteilen

Ich habe gerade eine Aufgabe über immutable AVLBäumen zu bearbeiten und habe bereits einiges programmiert und auch genau wie der Professor es haben möchte. Allerdings hänge ich gerade hart an der rotieren Methode und ich hoffe ich kann vielleicht von euch einige Ratschläge sammeln um es dann endlich zu schaffen. Hier erst mal meine Klasse AVLNode mit allen Methoden:

package avlBaum;

public class AVLNode {
	private final int key;
	private final String value;
	private final  int height;
	private final int balanceFactor;
	private final AVLNode right;
	private final AVLNode left;

	AVLNode(int key) {
		this(key, "");
	}

	AVLNode(int key, String value) {
		this(key, value, null, null);
	}
	
	AVLNode(int key, String value, AVLNode right, AVLNode left){
		this.key = key;
		this.value = value;
		this.right = right;
		this.left = left;
		
		if(this.right != null && this.left != null){
			this.height = Math.max(this.right.height, this.left.height)+1;
		}else if(this.right != null){
			this.height = this.right.height +1;
		}else if(this.left != null){
			this.height = this.left.height+1;
		}else{
			this.height = 0;
		}
		
		if(this.right != null && this.left != null){
			this.balanceFactor = this.left.height - this.right.height;
		}else if(this.right != null){
			//??
			this.balanceFactor = 0;
		}else if(this.left != null){
			//??
			this.balanceFactor = 0;
		}else{
			this.balanceFactor = 0;
		}
	}
	
	public AVLNode insert(int key) {
		// Case gleich
		if (key == this.key) {

		}
		// Case links
		if (key < this.key) {
			AVLNode rechts = this.right;
			if (this.left == null) {
				AVLNode links = new AVLNode(key);
				return new AVLNode(this.key, this.value, rechts, links);
			} else {
				return new AVLNode(this.key, this.value, rechts, this.left.insert(key));
			}
		}
		// Case rechts
		if (key > this.key) {
			AVLNode links = this.left;
			if (this.right == null) {
				AVLNode rechts = new AVLNode(key);
				return new AVLNode(this.key, this.value, rechts, links);
			} else {
				return new AVLNode(this.key, this.value, this.right.insert(key), links);
			}
		}
		return null;
	}
	
	public AVLNode checkBalance(AVLNode avlNode){		
		if(avlNode.balanceFactor > 1){	
//			return this.rotateLeft(avlNode);
			return null;
		}else if(avlNode.balanceFactor < -1){
//			return this.rotateRight(avlNode);
		}else{
			return avlNode;
		}
	}
	
	private AVLNode rotateRight(AVLNode avlNode){
		
	}
}

Habe wirklich ewig gegoogled und irgendwie nie das gefunden, was mir die Abfolge des Algorithmus zum rotieren wirklich verständlich zeigt.
Der Knoten, andem rotiert wird, wird in der Hierarchie eins nach oben gelegt und (bei rechts rotieren) seine Linken nachfolger auch wieder links eingeordnet.
Dadurch dass unser Prof wirklich bei jeder Aktion einen komplett neuen Baum erzeugt haben möchte, fällt es mir echt schwer da was zu code zu bringen. Habe auch schon relativ lange gebraucht um die insert- Methode so hinzubekommen.

Wäre da im Prinzip einfach eine Anweisung wie:

private AVLNode rotateRight(AVLNode avlNode){
		return new AVLNode(avlNode.key, avlNode.value, AVLNode.right, this);
	}

Habe da gerade ziemliche Probleme, nachzuvollziehen, ob bei dieser Anweisung dann noch alle benötigten Referenzen die bestehen sollen, da sind oder nicht.

Hoffe ich konnte mich so ausdrücken, dass ihr mein Problem versteht :lol:
Und bedanke mich auch schonmal für Antworten!

LG HazlNut!

 

[Katharsas]

Hoffe ich konnte mich so ausdrücken, dass ihr mein Problem versteht :lol:

LG HazlNut!

Ich verstehe nicht genau, was der Konstruktor

 AVLNode(int key, String value, AVLNode right, AVLNode left)

macht. Der erstellt doch bloß einen Wurzelknoten, an dem der linke und rechte Teilbaum dann hängen oder?

Edit:
Wenn ja, dann hast du glaube ich ein bisschen was falsch verstanden. Dein Prof möchte sicher nicht, dass bei jeder Aktion eine neuer Baum erzeugt werden soll. In dem Fall wäre nämlich eine clone() Methode angebracht, die alle Knoten rekursiv neu erzeugt, was eigentlich nichts mit AVL-Bäumen zu tun hat.
Ich würde eher darauf tippen, dass der Prof immer den kompletten Baum zurückbekommen will bei jedem Methodenaufruf. In dem Fall wäre der AUfruf von Konstruktoren unnötig (außer beim Einfügen).

Aber ich kann mich auch irren. Vor allem die final Teilbäume sind irritierend. Wie soll man denn so den Baum ändern, ohne ihn jedesmal kompliziert per Konstruktor zusammenzubasteln?

 

[HazlNut]

Ich verstehe nicht genau, was der Konstruktor macht. Der erstellt doch bloß einen Wurzelknoten, an dem der linke und rechte Teilbaum dann hängen oder?

Also wie es da jetzt gerade alles steht ist alles mit dem Prof abgesprochen und der möchte es genauso haben.

Glaube der nimmt es mit dem immutabel ziemlich ernst
Es soll nach jeder Aktion am Baum ein neuer Wurzelknoten mit allen Kindknoten zurückgegeben werden.
Is ja auch in der insert- Methode so implementiert.

Edit:
Er meinte dann auch noch zu mir, dass ich alle variablen auf final setzen solle, um die immutabilität sicher zustellen

 

[Katharsas]

Also wie es da jetzt gerade alles steht ist alles mit dem Prof abgesprochen und der möchte es genauso haben.

Glaube der nimmt es mit dem immutabel ziemlich ernst
Es soll nach jeder Aktion am Baum ein neuer Wurzelknoten mit allen Kindknoten zurückgegeben werden.
Is ja auch in der insert- Methode so implementiert.

Edit:
Er meinte dann auch noch zu mir, dass ich alle variablen auf final setzen solle, um die immutabilität sicher zustellen

Okay, also das ist zwar vollkommen bescheuert aber wenn dein Prof das so will :bahnhof:

Hast du denn die inser-Methode prüfen lassen von dem Prof?
Wenn ich die richtig verstanden habe, müsste die nämlich sehr falsch sein.

Wenn du mit einem immutable Tree arbeitest, heißt das, du kannst den Baum nicht verändern. Also du könntest z.B. auf Ebene 6 keinen Knoten einfügen, weil auf Ebene 5 der Elternknoten nicht veränderbar ist.
D. h., bei einem immutable Baum kannst du nicht einfügen, das geht nicht. Dementsprechend weiß ich nicht was deine insert-Methode sinnvolles machen soll. Die einzoge Möglichkeit für Einfügen wäre, dass du rekursiv den ganzen Baum neu erzeugst. Das heißt du musst JEDEN einzelnen Knoten im Baum neu erzeugen uns zusammensetzten wie beim alten Baum, nur beim Elternknoten auf Ebene 5 müsstest du den Knoten so abändern, dass er auf das neue eingefügte Element zeigt.

Also entweder ich bin völlig auf der falschen Spur oder deine insert-Methode macht nichts Sinnvolles.
Aber mit einem immutable Baum rekursiv sinnvoll zu arbeiten ist soweiso eine extrem unnötiger Aufwand. Viel sinnvoller wäre es, den Baum nicht immutable zu machen, sondern ihn vor jeder Operation zu kopieren (weider rekusriv Knoten für Knoten) und dann die Operation auf dem kopierten Baum auszuführen.

 

[HazlNut]

Also definitiv mit dem Prof abgeglichen hab ich folgende Zeilen:

if (key < this.key) {
            AVLNode rechts = this.right;
            if (this.left == null) {
                AVLNode links = new AVLNode(key);
                return new AVLNode(this.key, this.value, rechts, links);
            }

Hab jetz mal nur den Fall für die Linke Seite reingeschrieben. Da bin ich mir zu 100% sicher, dass es richtig ist.

Beim else:

else {
                return new AVLNode(this.key, this.value, rechts, this.left.insert(key));
            }

Hat er mir net konkret gesagt, dass es so geht, weil ers einfach mal für mich offen gelassen hat, dass ich mir nen Kopf mache

Hatte damit aber auch schon einige Bäume erstellt die dann im Endeffekt auch richtig erstellt wurden.
Rekursion wird da ja Angewendet. Und eins tiefer Prüft er ja wieder genau dasselbe!?

 

[Katharsas]

Hatte damit aber auch schon einige Bäume erstellt die dann im Endeffekt auch richtig erstellt wurden.
Rekursion wird da ja Angewendet. Und eins tiefer Prüft er ja wieder genau dasselbe!?

Ahh ja klar sorry ich hab das insert irgendwie übersehn -__-
Okay du baust also wirklich den gesamten Baum Knoten für Knoten neu.

Nagut, beim Drehen musst du das dann ähnlich machen. Im Prinzip würde ich so vorgehen:
Den Dreh-Algorithmus in Teile zerlegen, die rekursiv aufrufbar sind. Für jeden Teilalgorithmus schreibst du eine rekursive Methode, die jeweils bei einer bestimmten Abbruchbedingung die nächste Teilmethode aufruft.

Der erst Teil wäre es, den Knoten zu finden, dessen Kindknoten wiederum den Kindknoten als zu drehenden Knoten besitzt. Also quasi den obersten Knoten finden, an dessen Nachfolgern du etwas ändern musst.

Schreib also dafür eine Methode, die, wie immer rekursiv durch die Knoten sucht. Wenn sie den Knoten gefunden hat, überlegst du dir, was der Knoten den du grad hast alles machen kann und was alles gemacht werden muss.
Dementsprechend rufst du dann auf die Teilbäume andere rekursive Methoden auf, die im entsprechenden Zweig das richtige machen. Du kannst so auch bestimmte Teilbäume die du zwischenspeichern musst übergeben.

Ich hoffe das ist einigermaßen verständlich. Wäre so viel einfacher, wenn der nicht immutable wäre^^

 

[HazlNut]

Hab jetzt gerade mal mit nem Kommilitonen gesprochen. Der hat mir mal seinen Schnipsel geschickt.

private AVLNode rotateLeft() {
        assert this.right == null : ("Rechter Knoten ist nicht leer!");
        AVLNode tempNode = new AVLNode(this.key, this.value, this.right.left, this.left);
        return new AVLNode(this.right.key, this.right.value, tempNode, this.right.right);
    }

Werd das gleich mal mit dem durchgehen und bei mir reinbringen.

 

[Katharsas]

Hab jetzt gerade mal mit nem Kommilitonen gesprochen. Der hat mir mal seinen Schnipsel geschickt.

private AVLNode rotateLeft() {
        assert this.right == null : ("Rechter Knoten ist nicht leer!");
        AVLNode tempNode = new AVLNode(this.key, this.value, this.right.left, this.left);
        return new AVLNode(this.right.key, this.right.value, tempNode, this.right.right);
    }

Werd das gleich mal mit dem durchgehen und bei mir reinbringen.

Das müsste dann ja die Einfachrotation auf den Knoten sein, der nach unten rutscht (also auf den Kindknoten des obersten Knotens, dessen Referenzen sich ändern).

Dann musst du denke ich noch das Suchen nach diesem Knoten implementieren (wie in meinem letzten Post angedeutet), und wenn du Knoten mit dem richtigen Kind gefunden hast, hängst du stattdessen das Kind ran, was die rotateX()-Methode zurückgibt.

Dann fehlt allerdings noch die Doppelrotation (falls ihr die in der gleichen Methode machen sollt).
Bist du dir sicher, dass der Key den du bekommst der Key von dem Knoten ist, der nach oben rutschen soll? ODer ist das der Key für den Knoten, der bei der Rotation nach unten rutscht?

Edit: Ich stell mir das ungefähr so vor (wenn der Key für den absteigenden Knoten ist):

private AVLNode rotateLeft(AVLNode avlNode){
    if(this.right.key == avlNode.key) {
            return new AVLNode(this.key, this.value, this.left, this.right.rotateLeft());
    }
    else if(this.left.key == avlNode.key) {
            return new AVLNode(this.key, this.value, this.left.rotateLeft(), this.right);
    }
    else {
            return new AVLNode(this.key, this.value, this.left.rotateLeft(avlNode), this.right.rotateLeft(avlNode));
    }
}

private AVLNode rotateLeft() {
    assert this.right == null : ("Rechter Knoten ist nicht leer!");
    AVLNode tempNode = new AVLNode(this.key, this.value, this.right.left, this.left);
    return new AVLNode(this.right.key, this.right.value, tempNode, this.right.right);
}

Nullchecks fehlen noch.

 

[HazlNut]

Soooo.. habe mich jetz nochmal dran gesetzt und hab die Lösung :applaus:... Glaube ich :lol:

Hab es auf jeden Fall mit ein paar Fällen getestet und lief soweit

Hier das insert:

	public AVLNode insert(int key) {
		
		// Case gleich
		if (key == this.key) {
			AVLNode root = new AVLNode(this.key, this.value, this.right, this.left);
			return root.checkBalance();
		}
		
		// Case links
		if (key < this.key) {
			if (this.left == null) {
				 return new AVLNode(this.key, this.value, this.right, new AVLNode(key)).checkBalance();
			} else {
				return new AVLNode(this.key, this.value, this.right, this.left.insert(key)).checkBalance();
			}
		}
		
		// Case rechts
		if (key > this.key) {
			AVLNode links = this.left;
			if (this.right == null) {
				AVLNode rechts = new AVLNode(key);
				return new AVLNode(this.key, this.value, rechts, links).checkBalance();
			} else {
				return new AVLNode(this.key, this.value, this.right.insert(key), links).checkBalance();
			}
		}
		return null;
	}

Hier checkBalance:

	public AVLNode checkBalance(){	
		AVLNode root = null;
        switch (this.balanceFactor) {
        case (2):
            if (this.left.balanceFactor == -1 && this.left != null) {
               root = this.rotateLeft();
            } else if(root == null){
            	return this.rotateRight();
            }else{
            	return root.rotateRight();
            }
        return root.rotateRight();
        case (-2):
            if (this.right.balanceFactor == 1 && this.right != null) {
                root = this.rotateRight();
            }else if(root == null){
            	return this.rotateLeft();
            }else{
            	return this.rotateLeft();
            }
        return root.rotateLeft();
        default:
            return this;
        }
	}

Und hier die rechts- Rotation:

public AVLNode rotateRight() {
        assert this.left != null : ("Linker Knoten ist nicht leer!");
        AVLNode tempNode = new AVLNode(this.key, this.value, this.right, this.left.right);
        return new AVLNode(this.left.key, this.left.value, tempNode, this.left.left);
    }

Das einzige, was mir gerade beim rauskopieren aufgefallen ist, bei checkBalance is das letzte else laut eclipse "Dead Code"

Edit:
Vielen vielen dank für deine Hilfe Katharsas :toll: