i-kleinstes Element in Suchbäumen finden

[Yannik0103]

Hi, ich bin leider ziemlicher Anfänger im Programmieren und habe Probleme mit einer Aufgabe. Ich soll eine Methode implementieren, die den Teilbaum eines Suchbaums zurückgibt, dessen Wurzel das i-kleinste Element im Suchbaum ist. Die Aufgabenstellung verlangt, dass wir die Aufgabe mit der Information, wie viele Kinder jeder Knoten x besitzt, lösen. Ich habe also für jeden Knoten x einen Integer x.size implementiert, der der Anzahl der Kinder von x entspricht. Nun weiß ich allerdings nicht, wie ich mit dieser Information einen Algorithmus entwerfen und diesen dann implementieren soll. Mein Plan ist es an der Wurzel vom Suchbaum T anzufangen und zu überprüfen, ob die Wurzel kleiner oder größer als das i-kleinste Element ist und dann mit dem linken bzw rechten Teilbaum weiterzumachen, aber ich finde keine Möglichkeit wie man für einen allgemeinen Knoten x bestimmen kann, der wie vielt kleinste er ist. Hat jemand eine Idee?

 

[kneitzel]

Also ein Knoten soll bei Dir folgend Dinge "wissen":
- einen Wert
- einen linken und einen rechten Knoten, wobei der eine Teilbaum nur kleinere und der andere Teilbaum nur größere Werte hat.
- Wie viele Kinder der Knoten besitzt.

Nun mal dir einfach einmal einen solchen Baum auf und überleg, wie du zu einem vorgegebenen Element (z.B. 3. kleinster Wert) kommen kannst.

Du kannst Dir dabei überlegen:
Du schaust Dir einen Knoten an und kennst dann die Anzahl der Kinder des Knotens. Und da Du die Child-Knoten kennst, kennst Du auch die Anzahl deren Kinder.

Du kannst das einmal durchspielen und zwar mit mehreren Bäumen:
a) einem Ausbalanzierten Baum.
b) einem Baum der nur nach rechts geht.
c) einem Baum, der nur nach links geht.

(b + c erstellst Du, indem Du aufsteigende / absteigende Zahlenfolgen einfügst)


=> Schau dir einfach einmal selbst an, welches z.B. der 3. kleinste Wert ist und dann schau, ob Du irgendwelche Regeln erkennen kannst für die Entscheidungen:
a) Ja, dieser Node enthält den dritt-Kleinste Wert.
b) wieso musste ich bei den Nodes von diesem Node bis zur Wurzel jeweils den entsprechenden Child-Node wählen?

 

[mihe7]

wie man für einen allgemeinen Knoten x bestimmen kann, der wie vielt kleinste er ist. Hat jemand eine Idee?

Noch als zusätzlichen Schuber: der linke Teilbaum enthält die Knoten, deren Werte kleiner als der von x sind.

 

[Yannik0103]

public class {// Hier muessen Sie den Klassennamen anpassen.
    /*
    *
    Beginn der Definition der Unterklasse "Suchbaum"
    *
    */
    static class Suchbaum {
         /*
            In dieser Klasse sollten Sie an drei Stellen Aenderungen vornehmen:
            2) Die Methode "select" fuellen.
            3) Dafuer die Definition der Klasse "Knoten" anpassen.
            4) Und die Methode "insert" anpassen.
            */
      private Knoten wurzel;
      private Suchbaum left;
      private Suchbaum right;

      private class Knoten{
          public int key;
          public int size;

          public Knoten(int x){
            key = x;
            size = 0;
          }
      }

       public Suchbaum select(int i){
       //Diese Prozedur sollen Sie fuellen. Dafuer sollte zudem die Definition von Knoten um den parameter "size" erweitert werden und die Methode "insert" angepasst werden.
           if (left.wurzel.size + 2 == i) return T;
           else {
               if (left.wurzel.size + 2 < i) return right.select(i - left.wurzel.size - 2);
               if (left.wurzel.size + 2 > i) return left.select(i);
           }
       }

      public void insert(int x){
        //x in Baum einfuegen
        if (wurzel==null) {
          wurzel = new Knoten(x);
          left = new Suchbaum();
          right = new Suchbaum();
        }
        else {
          if (wurzel.key > x){
              left.insert(x);
              wurzel.size++;
          }
          if (wurzel.key < x){
              right.insert(x);
              wurzel.size++;
          }
        }
      }

Das ist mein bisheriger Ansatz, das meiste war mit ein paar anderen Methoden zur Implementierung von Suchbäumen schon vorgegeben, ich habe size und select implementiert, allerdings wird mir bei select angezeigt, dass die Methode keinen Suchbaum zurückgibt, aber ich gebe doch den Baum mit der Wurzel, die ich gerade betrachte zurück oder nicht?

 

[mrBrown]

Hier gibst du "T" zurück, was auch immer "T" ist:
if (left.wurzel.size + 2 == i) return T;


Außerdem gibst du nur innerhalb eines ifs etwas zurück, du musst aber auch im Fall, dass keins der if's wahr ist, was zurückgeben.

 

[Yannik0103]

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Arrays;



public class Suchbaeume {
static class Suchbaum {

private Knoten wurzel;
private Suchbaum left;
private Suchbaum right;

private class Knoten{
public int key;
public int size;

public Knoten(int x){
key = x;
size = 0;
}
}

public Suchbaum select(int i){

if (left.wurzel.size + 2 == i) return T;
else {
if (left.wurzel.size + 2 < i) return right.select(i - left.wurzel.size - 2);
if (left.wurzel.size + 2 > i) return left.select(i);
}
}

public void insert(int x){

if (wurzel==null) {
wurzel = new Knoten(x);
left = new Suchbaum();
right = new Suchbaum();
}
else {
if (wurzel.key > x){
left.insert(x);
wurzel.size++;
}
if (wurzel.key < x){
right.insert(x);
wurzel.size++;
}
}
}

public Suchbaum(){
wurzel = null;
left = null;
right = null;
}

public String toString()
return toStringRec(0);
}

private String toStringRec(int i){
char[] spaces = new char[i];
Arrays.fill(spaces,'\t');
String platz = new String(spaces);
if (wurzel==null) return platz+"[]";
else return right.toStringRec(i+1)+"\n"+platz+"["+Integer.toString(wurzel.key)+"]"+"\n"
+left.toStringRec(i+1);
}
}

static Suchbaum T;
static int i;
public static void main(String[] args) {
String vorname1, nachname1, matrikelnr1, vorname2, nachname2, matrikelnr2, vorname3, nachname3, matrikelnr3;


vorname1 = "";
nachname1 = "";
matrikelnr1 = "";
vorname2 = "";
nachname2 = "";
matrikelnr2 = "";
vorname3 = "";
nachname3 = "";
matrikelnr3 = "";

file_name = args[0];
T = new Suchbaum();
i = 0;
inputEinlesen();

System.out.println("Baum nach Eingabe aller Zahlen:");
System.out.println(T.toString());
System.out.println("Der Baum, dessen Wurzel das "+i+"-te Element ist:");
System.out.println(T.select(i).toString());

System.out.println(vorname1+" "+nachname1+";"+matrikelnr1+";"+vorname2+" "+nachname2+";"+matrikelnr2+";"+vorname3+" "+nachname3+";"+matrikelnr3);
}

static String file_name;

static void inputEinlesen(){
Scanner input;
String zeile;

// Initialisierung:
input = null;
zeile = "";

// Datei input.txt einlesen:
try
{
input = new Scanner(new File(file_name));
}
catch(FileNotFoundException e)
{
System.out.println("Input-Datei nicht gefunden.");
return;
}

if(input.hasNextLine())
zeile = input.nextLine();
String[] zahlenliste = zeile.split(" ");
for (String str : zahlenliste)
{
try
{
T.insert(Integer.parseInt(str));
}
catch (NumberFormatException e)
{
System.out.println("Erste Zeile enthaelt nicht nur Zahlen.");
return;
}
}

if(input.hasNextLine())
zeile = input.nextLine();
try
{
i = Integer.parseInt(zeile);
}
catch (NumberFormatException e)
{
System.out.println("Zweite Zeile enthaelt nicht nur eine Zahl.");
return;
}
}



}

Das ist der komplette Code, T ist der Suchbaum der eingelesen wurde auf den ich select anwende, bei den darauf folgenden Aufrufen von select würde dann doch der linke bzw rechte Teilbaum auf den ich select anwende zurückgegeben werden oder?
Ok, es fehlen noch die Fälle in denen kein linker bzw rechter Teilbaum existiert oder?[/I][/code]

 

[mrBrown]

Bitte Code-Tags benutzen ([code=java]//code...[/code]) und den Code wenn möglich sinnvoll einrücken

 

[mrBrown]

Du solltest in dem gesamten Code keine statischen Variablen benutzen, die brauchst du dort nicht und die machen es nur komplizierter.

Der Grund für den Fehler steht weiter oben schon

 

[Yannik0103]

Der Code ist schon von der Aufgabenstellung vorgegeben und wir dürfen nur select implementieren, size für jeden Knoten definieren und in insert size verändern, wie könnte ich dieses Problem umgehen, wenn ich nichts anderes verändern darf?

 

[mrBrown]

In select keine statischen Variablen nutzen.


Der Fehler ist aber wie gesagt:

Außerdem gibst du nur innerhalb eines ifs etwas zurück, du musst aber auch im Fall, dass keins der if's wahr ist, was zurückgeben.

 

[Yannik0103]

Wenn mein Ansatz richtig ist müsste select bei Gleichheit den Suchbaum auf den select momentan angewandt wird. Aber wie kann ich diesen zurückgeben? Der erste Aufruf von select erfolgt doch mit T.select(i) und diese Variable ist doch statisch
Ich hab die Fälle < = und > also fehlen doch nur noch die Fälle, dass kein linker Teilbaum vorhanden ist und mein Teilbaum den ich gerade betrachte der richtige ist oder dass i größer als die Anzahl der Elemente im Baum ist oder? Das sind die einzigen 5 Fälle, die mir einfallen

 

[mrBrown]

Wenn mein Ansatz richtig ist müsste select bei Gleichheit den Suchbaum auf den select momentan angewandt wird. Aber wie kann ich diesen zurückgeben? Der erste Aufruf von select erfolgt doch mit T.select(i) und diese Variable ist doch statisch

Kennst du this?

Ich hab die Fälle < = und > also fehlen doch nur noch die Fälle, dass kein linker Teilbaum vorhanden ist und mein Teilbaum den ich gerade betrachte der richtige ist oder dass i größer als die Anzahl der Elemente im Baum ist oder? Das sind die einzigen 5 Fälle, die mir einfallen

Ja, aber in jedem Fall wirst du einen Zweig ohne Bedingung brauchen, damit der Compiler sicherstellen kann, dass immer etwas zurückgegeben wird.

 

[Yannik0103]

Also anstatt return T return this?
Ok ich muss also die Fälle <, =, >, i>Anzahl der Elemente in T, es existiert kein linker Teilbaum und mein Element ist das richtige, es existiert kein linker Teilbaum und mein Element ist im rechten Teilbaum und einen Fall ohne Bedingung implementieren?

 

[Yannik0103]

(

public Suchbaum select(int i){
       //Diese Prozedur sollen Sie fuellen. Dafuer sollte zudem die Definition von Knoten um den parameter "size" erweitert werden und die Methode "insert" angepasst werden.
           if (left.wurzel.size + 2 == i) return this;
           else {
               if (left.wurzel.size + 2 < i) return this.right.select(i - this.left.wurzel.size - 2);
               if (left.wurzel.size + 2 > i) return this.left.select(i);
               if (this.left.wurzel == null && i == 1) return this;
               if (this.left.wurzel == null && i > 1) return this.right.select(i - 1);
                
           }
        return new Suchbaum();
       }

)
Das wäre meine Idee

 

[mrBrown]

Hast du das ganze irgendwann schon mal gestartet?

 

[Yannik0103]

Nein, ich habe leider auch keine Ahnung wie man das macht