Basisfall

E

Easyik

Mitglied
Hey zusammen,

ich sitze nun schon seit einer weile an einem Baum.

Soweit komme ich mittlerweile ganz gut klar damit.

innerhalb der Insert-Methode komme ich leider auf keinen Basisfall um die Rekusion abzubrechen.

Vllt. kann mir jemand einen Tipp geben :
Java: 
public int korrekturDerReihenfolge(int n){
    if(n%2==0){
        n=n/2;
    }else{
    n=(n-1)/2;
    }
    return n;
}

public void insert(String eingabe,int status){
 
    if(links==null&& status%2==0){
        links=new Knoten(eingabe,status);
    }else if(rechts==null && status%2 !=0){
        rechts=new Knoten(eingabe,status);
    }else{

    int temp=korrekturDerReihenfolge(status);
   
    if(temp==links.status){
        links.insert(eingabe, status);

    }else if(temp==rechts.status){
        rechts.insert(eingabe, status);
    } else{
        temp=korrekturDerReihenfolge(status);
        insert(eingabe,temp);
    }
    
}
}

und wie immer gilt bin für jeden Ratschlag und Tipp, offen und Dankbar
 
K

kneitzel

Gast
Also ich habe im Augenblick Probleme, hier das Vorgehen zu verstehen. Kannst Du einmal erläutern, was genau beim Einfügen passieren soll? Oder geht es hier um das, was wir prinzipiell schon hatten und wo ich dir das mit Rechts / Links einfügen gesagt hatte? Aber da bin ich mir jetzt unsicher, dass wir da noch das gleiche Verständnis hatten.

Wenn status sozusagen die Zahl ist, die die Position angibt, dann hast Du doch generell den Vorgang:

a) mit %2 konntest Du heraus kriegen: rechts oder links.
b) mit /2 hast Du die folgende Zahl bekommen.
c) Wenn die folgende Zahl 1 ist, dann bist Du mit dem Ergebnis aus a direkt am Ziel.

Also Platz 1 ist die Wurzel, dann kommen links 2, rechts 3. An 2 sind dann 4 und 5.

Ablauf ist also z.B. bei status = 5:
Du bist in der Wurzel 5%2 = 1, d.h. Du gehst nach links. Folgende Zahl 5/2 = 2, ist nicht 1, daher rekursiver Aufruf.
Du bist in dem Knoten "2", status = 2, 2%2 = 0, d.h. rechts ist dran. 2/2 = 1, d.h. der rechte Knoten ist der Zielknoten!

Jetzt kann es zu Fehlersituationen kommen:
- Wurzel ist null. Dann kannst Du nur mit status 1 einfügen.
- Du musst in einen Child-Knoten, der null ist -> Du hast erst einen Knoten eingefügt (wurzel) und nun willst Du mit status=5 was einfügen, obwohl es den Knoten 2 nicht gibt.
- Du kommst an die Stelle, wo der Knoten eingefügt werden soll und da ist schon ein Knoten.

Da musst Du dir natürlich was überlegen und die Behandlung entsprechend bauen. Aber das wäre so ein Vorgang, der denkbar ist.

Das wäre so meine Sicht auf den Algorithmus - so ich den noch richtig im Kopf hatte. Da evtl. halt mehr Details geben, wenn ich das falsch in Erinnerung habe oder etwas verwechsle.

Ein paar weitere Hinweise habe ich aber noch:

a) Bezeichner - hier sollte man immer etwas wählen, was mehr Sinn macht. status ist da evtl. falsch. Das ist eher der Platz im Baum. Wobei da die Frage ist, in wie weit das in dem Knoten des Baumes eine Rolle spielt, d.h. ob die Information gespeichert werden muss. Zumal ja jeder zweig eine Wurzel eines neuen Teilbaumes ist. Und durch die Halbierung wirst Du da auch nicht wirklich sinnvolle Dinge abspeichern fürchte ich.

b) Zu der Methode koorekturDerReihenfolge habe ich einen kleinen Hinweis:
Java: 
public int korrekturDerReihenfolge(int n){
    if(n%2==0){
        n=n/2;
    }else{
    n=(n-1)/2;
    }
    return n;
}

n ist ein Integer. Daher wird bei der Division durch 2 weiterhin ein Integer raus kommen.
Du musst also gar nicht prüfen, ob die Zahl gerade oder ungerade ist um dann ggf. 1 abzuziehen:

Bei 6 rechnest Du 6/2 = 3.
Bei 7 Rechnest Du (7-1)/2 = 3. Wenn Du das -1 weg lässt, dann kommt aber auch wieder 3 dabei raus, denn Nachkommastellen gibt es bei int ja nicht. Aus dem 3,5 wird somit einfach eine 3.

Somit sollte hier schon ausreichen:
Java: 
public int korrekturDerReihenfolge(int n){
    return n/2;
}
 
E

Easyik

Mitglied
kneitzel hat gesagt.:
Also ich habe im Augenblick Probleme, hier das Vorgehen zu verstehen. Kannst Du einmal erläutern, was genau beim Einfügen passieren soll? Oder geht es hier um das, was wir prinzipiell schon hatten und wo ich dir das mit Rechts / Links einfügen gesagt hatte? Aber da bin ich mir jetzt unsicher, dass wir da noch das gleiche Verständnis hatten.

Wenn status sozusagen die Zahl ist, die die Position angibt, dann hast Du doch generell den Vorgang:

a) mit %2 konntest Du heraus kriegen: rechts oder links.
b) mit /2 hast Du die folgende Zahl bekommen.
c) Wenn die folgende Zahl 1 ist, dann bist Du mit dem Ergebnis aus a direkt am Ziel.

Also Platz 1 ist die Wurzel, dann kommen links 2, rechts 3. An 2 sind dann 4 und 5.

Ablauf ist also z.B. bei status = 5:
Du bist in der Wurzel 5%2 = 1, d.h. Du gehst nach links. Folgende Zahl 5/2 = 2, ist nicht 1, daher rekursiver Aufruf.
Du bist in dem Knoten "2", status = 2, 2%2 = 0, d.h. rechts ist dran. 2/2 = 1, d.h. der rechte Knoten ist der Zielknoten!

Jetzt kann es zu Fehlersituationen kommen:
- Wurzel ist null. Dann kannst Du nur mit status 1 einfügen.
- Du musst in einen Child-Knoten, der null ist -> Du hast erst einen Knoten eingefügt (wurzel) und nun willst Du mit status=5 was einfügen, obwohl es den Knoten 2 nicht gibt.
- Du kommst an die Stelle, wo der Knoten eingefügt werden soll und da ist schon ein Knoten.

Da musst Du dir natürlich was überlegen und die Behandlung entsprechend bauen. Aber das wäre so ein Vorgang, der denkbar ist.

Das wäre so meine Sicht auf den Algorithmus - so ich den noch richtig im Kopf hatte. Da evtl. halt mehr Details geben, wenn ich das falsch in Erinnerung habe oder etwas verwechsle.

Ein paar weitere Hinweise habe ich aber noch:

a) Bezeichner - hier sollte man immer etwas wählen, was mehr Sinn macht. status ist da evtl. falsch. Das ist eher der Platz im Baum. Wobei da die Frage ist, in wie weit das in dem Knoten des Baumes eine Rolle spielt, d.h. ob die Information gespeichert werden muss. Zumal ja jeder zweig eine Wurzel eines neuen Teilbaumes ist. Und durch die Halbierung wirst Du da auch nicht wirklich sinnvolle Dinge abspeichern fürchte ich.

b) Zu der Methode koorekturDerReihenfolge habe ich einen kleinen Hinweis:
Java: 
public int korrekturDerReihenfolge(int n){
    if(n%2==0){
        n=n/2;
    }else{
    n=(n-1)/2;
    }
    return n;
}

n ist ein Integer. Daher wird bei der Division durch 2 weiterhin ein Integer raus kommen.
Du musst also gar nicht prüfen, ob die Zahl gerade oder ungerade ist um dann ggf. 1 abzuziehen:

Bei 6 rechnest Du 6/2 = 3.
Bei 7 Rechnest Du (7-1)/2 = 3. Wenn Du das -1 weg lässt, dann kommt aber auch wieder 3 dabei raus, denn Nachkommastellen gibt es bei int ja nicht. Aus dem 3,5 wird somit einfach eine 3.

Somit sollte hier schon ausreichen:
Java: 
public int korrekturDerReihenfolge(int n){
    return n/2;
}
Zum Vergrößern anklicken....
Ziel war es ja wie schon geschildert:
root=1
2 links
3 rechts
4 an links
5 an links
6 an rechts
7 an rechts
soweit klappt es ja aber wenn ich die 8 an die 4 einfügen möchte, habe ich einen Logik Fehler da zwar gerade links soll aber dieser kann ja auch zuerst rechts entlang gehen und danach links -.-

ich finde keinen passenden Ansatz
 
K

kneitzel

Gast
Dann schau Dir doch einfach die Beschreibung des Algorithmus an, wie ich diesen beschrieben habe. Ich blicke Durch Deine Fälle schlicht nicht durch und bei dem verdrehten Code blicke ich schlicht nicht durch.

Das Wichtigste überhaupt ist und bleibt lesbarer Code. Mit Deinen Bezeichnern und Operationen ist der Code schlicht nicht lesbar und damit ist es für außenstehende extrem schwer, da einen Fehler zu finden. Den Algorithmus konnte ich aber aufzeigen denke ich mal. Das ggf. noch etwas sinnvoll aufgeteilt und schon ist alles einfach lesbar.

Aber den Sinn in dem Baum sehe ich so auch noch noch wirklich muss ich gestehen. Du hast ja eigentlich keinen Baum sondern ein Array, sprich: Du willst per index zugreifen können. Da wären dann Arrays deutlich besser z.B. in Form der ArrayList.

Wenn man das aber als Baum haben will (Weil man ggf. viele unterschiedliche Werte hat und eben nicht von 1...n auffüllt sondern halt mit Lücken auffüllt, dann kann sowas als Suchbaum Sinn machen - aber dann ist der index halt das Suchfeld des typischen Binary Search Tree. Und den kann man dann auch noch ausbalanzieren (Ich kenne das mit höhen, die man mit pflegt aber das geht wohl auch über Farben mit dem rot/schwarz Baum).

Als reine Übung ist das zwar interessant, aber ansonsten sehe ich gerade nicht einmal einen Anwendungsfall.
 
E

Easyik

Mitglied
kneitzel hat gesagt.:
Dann schau Dir doch einfach die Beschreibung des Algorithmus an, wie ich diesen beschrieben habe. Ich blicke Durch Deine Fälle schlicht nicht durch und bei dem verdrehten Code blicke ich schlicht nicht durch.

Das Wichtigste überhaupt ist und bleibt lesbarer Code. Mit Deinen Bezeichnern und Operationen ist der Code schlicht nicht lesbar und damit ist es für außenstehende extrem schwer, da einen Fehler zu finden. Den Algorithmus konnte ich aber aufzeigen denke ich mal. Das ggf. noch etwas sinnvoll aufgeteilt und schon ist alles einfach lesbar.

Aber den Sinn in dem Baum sehe ich so auch noch noch wirklich muss ich gestehen. Du hast ja eigentlich keinen Baum sondern ein Array, sprich: Du willst per index zugreifen können. Da wären dann Arrays deutlich besser z.B. in Form der ArrayList.

Wenn man das aber als Baum haben will (Weil man ggf. viele unterschiedliche Werte hat und eben nicht von 1...n auffüllt sondern halt mit Lücken auffüllt, dann kann sowas als Suchbaum Sinn machen - aber dann ist der index halt das Suchfeld des typischen Binary Search Tree. Und den kann man dann auch noch ausbalanzieren (Ich kenne das mit höhen, die man mit pflegt aber das geht wohl auch über Farben mit dem rot/schwarz Baum).

Als reine Übung ist das zwar interessant, aber ansonsten sehe ich gerade nicht einmal einen Anwendungsfall.
Zum Vergrößern anklicken....
Das dient lediglich der Übung, sprich ich verfolge damit kein bestimmtes Ziel.

Ich hatte eine Idee und wollte das umsetzen ohne Kompromisse einzugehen.
An der Lesbarkeit meines Codes muss ich noch arbeiten XD

vielen dank für die ganze Hilfestellung
 

Aktuelle Jobs

Neue Themen


Oben