Sortiertet Baum in Java

[MaToBe]

Hallo,

vorweg: ich weiß, dass es hier verpönt ist, Aufgaben / Übungen zu posten und dann auf Lösungen zu hoffen, jedoch komme ich bei dieser Übung echt nicht weiter (liegt auch zum Teil daran, dass unser Prof denkt, dass wir deutlich mehr Programmierkenntnisse in Java haben, als wir vom Java-Prof bisher vermittelt bekommen haben.)
Ich fände es nett, wenn mir jemand bei der Lösung helfen könnte, oder mir vielleicht eine Art "Pseudo-Code" geben könnte.
Wenn hingegen mein Topic garnicht wilkommen ist, bitte ich um Entschuldigung und um Löschung..

Aufgabe: Vervollständigen Sie die gegebene Methode insert(key, value) der Klasse SortedTreeNode. (Klassen des Programms und "Erklärungsbild" sind im Anhang).

[fkerber]

Hi,

wo hängt es denn konkret?


LG, Frederic

[geskill]

Habe mir das gerade mal angesehen, aber paar Worte deinerseits damit man sich nicht in alles reindenken muss wäre hilfreich.

Code:

public void insert(Integer key, String value){
      if(key<this.key)
         this.key = key;
      
      int index = this.search(key);
      
      if(isLeafLevel){
         //insert into leaf
         //TODO: complete code
         insert(index, new SortedTreeLeaf(key, value));
      }
      else{
         //insert into node
         //TODO: complete code
         SortedTreeNode node = new SortedTreeNode(this.isLeafLevel);
         node.key = key;
          //// hier noch irgendwie Value setzten ???
         insert(index, node); //// eigentlich erst prüfen ob voll ? 
         //split if needed
         if(node.isFull()){
            //TODO: complete code
         }
      }
   }

[MaToBe]

Code:

 if(isLeafLevel){
         //insert into leaf
         //TODO: complete code
         insert(index, new SortedTreeLeaf(key, value));
      }

Damit wird ein neues Blatt mit Key und Value erstellt und an dem Index eingefügt. Aber welche insert-Methode rufst du hier auf? Die 2te Methode verlangt doch einen SortedTree und kein SortedTreeLeaf oder?

Code:

insert(index, node);

Das selbe hier, wo ist den die Insert-Methode, der ich eine node mitgeben kann?
Keine Kritik, ich verstehs nur nicht.

Des weiteren habe ich dies noch in der Aufgabe gefunden, denke das ist für das Splitten wichtig:

Zitat:

Knoten verweisen auf Kind‐Knoten/Blätter in einem bestimmten Wertebereich und haben einen maximalen Füllgrad (Anzahl Kind-Knoten)

Mein Vorschlag sieht so aus:

Code:

public void insert(Integer key, String value){
      if(key<this.key)
         this.key = key;
      
      int index = this.search(key);
      
      if(isLeafLevel){
         //insert into leaf
         //TODO: complete code
         insert(index, new SortedTreeLeaf(key, value));
      }
      else{
         //insert into node
         //TODO: complete code
         SortedTreeNode node = new SortedTreeNode(this.isLeafLevel);
         node.key = key;
         index = this.search(node.key);
         insert(index, new SortedTreeLeaf(key, value);
         //split if needed
         if(node.isFull()){
            //TODO: complete code
         }
      }
   }

[geskill]

Hi,
es gibt 2 insert-Methoden (die andere steht über der, die ergänzt werden muss). Wir müssen also nicht wirklich was neues hinzufügen, sondern nur eine Vorauswahl treffen, sprich müssen schauen, ist es nun ein Blatt oder ist es ein Knoten (und bei zu vielen Knoten irgendwie teilen ???).

Die Klasse SortedTreeLeaf (innerhalb SortedTreeLeaf.java) erbt von SortedTree, deshalb kann man auch Objekte davon nutzen (genauso wie SortedTreeNode). Außerdem ist SortedTree nur eine abstrakte Klasse, wird schwer davon ein Objekt zu erzeugen ;)

Wenn es kein Knoten ist braucht man eigentlich auch nicht den Value Wert, sprich man kann SortedTreeNode benutzen. Also mein Ansatz scheint in die richtige Richtung zu weisen. Letztendlich fehlt noch die Sache mit dem Split, also ich hab den Teil noch nicht so durchdrungen...

PS: Dein Ansatz macht für mich kein Sinn, im Teil, wo es um die Knoten geht wird erst ein SortedTreeNode erstellt und dann noch ein SortedTreeLeaf welcher dann hinzugefügt wird. Also mit dem erzeugten SortedTreeNode wird nichts gemacht. Sieht für mich so aus als hättest du in der Vorlesung mehr geschlafen als zugehört ;)

Grüße

[MaToBe]

Ja, soweit ist es klar. Ich habe die Aufgabe aber so verstanden, dass in den Knoten nur die "key"s stehen (also keine Daten, richtig) und diese dann wiederherum auf die Blätter verweisen, die die Daten enthalten.

Also müsste man doch bei dem else-Fall erst einen Knoten erstellen, diesen an den Baum hängen und dann für diesen Knoten noch ein Blatt erstellen.

Code:

SortedTreeNode node = new SortedTreeNode(this.isLeafLevel);
         node.key = key;
         //hänge Knoten hier irgendwie an Baum, Code fehlt hier noch?!
         index = this.search(node.key);
         //hier wird dann das Blatt erstellt mit den Daten am neu erstellten Knoten
         insert(index, new SortedTreeLeaf(key, value);

Denkfehler?

[geskill]

Zitat:

Zitat von MaToBe (Beitrag 1097934)

Code:

//hänge Knoten hier irgendwie an Baum, Code fehlt hier noch?!
index = this.search(node.key);

Das wird doch oben schon gemacht.

Zitat:

Zitat von MaToBe (Beitrag 1097934)

Code:

//hier wird dann das Blatt erstellt mit den Daten am neu erstellten Knoten
insert(index, new SortedTreeLeaf(key, value);

Ja ein Blatt, aber wir wollen doch hier Knoten erstellen ^^ ... sprich Blätter sind fertig!


Bevor wir jetzt aber mit "insert" einen Knoten hinzufügen, müssen wir doch prüfen ob es schon voll ist oder erst danach ?

[MaToBe]

Ersteres stimmt ja.

Zitat:

Zitat von geskill (Beitrag 1097936)

Zitat:

Zitat von MaToBe (Beitrag 1097934)

Code:

//hier wird dann das Blatt erstellt mit den Daten am neu erstellten Knoten
insert(index, new SortedTreeLeaf(key, value);

Ja ein Blatt, aber wir wollen doch hier Knoten erstellen ^^ ... sprich Blätter sind fertig!

Knoten erstellen klar, aber wir müssen doch auch noch irgendwo die Daten berücksichtigen. Wo sind die Blätter fertig? Wenn wir bei der if-Anweisung ins else gehen, dann erstellen wir nur einen Knoten, keine Blätter und keine Daten somit ?!

Zitat:

Zitat von geskill (Beitrag 1097936)

Bevor wir jetzt aber mit "insert" einen Knoten hinzufügen, müssen wir doch prüfen ob es schon voll ist oder erst danach ?

Laut Übung, soll nach dem Einfügen auf "full" getestet werden, sprich man fügt zu 3 Knoten einen 4ten an, prüft dann und merkt das die

Code:

public static int MAX_SIZE = 3;

3 beträgt und splittet nachträglich Knoten [1,2,3,4] in [1,2] und [3,4]. So zeigt es jedenfalls das Schaubild.