Binärer Baum und partielle Summe



  • Hallo,

    ich auf dieses Forum aufmerksam geworden, weil ich einen binären Baum konstruieren möchte und mittels google den Artikel des Users Ben04 gefunden hatte.

    Ich möchte den binären Baum allerdings auf eine andere Art und Weise verwenden.

    Bei mir geht es darum n Elemente x_1,x_2,...,xnx\_1 , x\_2 , ... , x_n an der Basis eines Baumes zu speichern.
    Als nächstes soll in der Zeile darüber die Partialsumme von aus je zwei darunterliegenden Elementen x_i+x_(i+1)x\_i + x\_(i+1) gebildet werden.

    Dieses Prozedere soll so lange durchgeführt werden, bis die Wurzel schließlich die Summe aus allen Elementen darstellt: sum\limits_{i=1}^{n} x_i .

    Wenn ich mir den Artikel ansehe, dann benötige ich scheinbar einen perfekt balancierten Baum, der allerdings 'von unten nach oben' erstellt wird?

    Könnt ihr mir da weiterhelfen?

    Gruß,
    Klaus.



  • Bis jetzt seh ich nicht, warum der Baum perfekt balanziert sein muss. Bau 'nen Baum, bilde die Summen, sei glücklich. Wo ist das Problem?



  • In deinem Beispiel balanciert sich der Baum doch von selbst. Jeder Vater hat zwei Kinder. Das ist also ein voll besetzter Binärbaum.
    Es gibt da also eigentlich kein Problem.



  • Hi,

    SG1 schrieb:

    Wo ist das Problem?

    Hier

    SG1 schrieb:

    Bau 'nen Baum

    Mir ist konzeptionell nicht klar, wie ich solch einen Baum aufziehen soll.

    Ein binärer Baum wird von der Wurzel beginnend gefüllt, während die Blätter entlang immer die größer / kleiner / gleich Abfrage läuft, um das neue Element richtig einzusortieren.

    Das benötige ich gar nicht. Ich sehe momentan das Problem darin eine leere Stelle zu finden, also einen Knoten, dessen Pointer rechts oder links noch auf 0 zeigt.
    Nur wenn ich oben starte, dann habe ich erstmal gar kein Kriterium dafür, wo eine Stelle frei ist.

    Aber nochmal, es geht darum, dass die Elemente alle in der letzten Zeile liegen.
    D.h. wenn ich zwei Elemente einfüge, dann hat die Wurzel rechts und links ein Kind.
    Wenn ich jetzt ein drittes Element einfüge, dann muss eine neue Zeile angelegt werden mit vier Knoten. Die ersten beiden Knoten werden mit den bisherigen Elementen gefüllt, der dritte Knoten mit dem neuen Element und der vierte Knoten bleibt erstmal frei.

    Jetzt kann ich ein weiteres Element in den vierten Knoten setzen.

    Ab dem fünften Element, muss ich wieder von vorne beginnen, sprich neue Zeile anlegen, Elemente kopieren, usw.

    Und was ich bisher vergessen habe, natürlich noch die Partialsummen bilden. Ist das nicht ein wenig umständlich?

    Ich arbeite jetzt seit ca. 1,5 Jahren mit C++. Aus dem Grund hadere ich noch daran, wie ich daran gehen soll. Soll ich Arrays bauen und darin die Adressen speichern? Da das ganze ein wenig dynamisch sein soll, wäre ein Vektor wahrscheinlich die bessere Wahl.
    Oder soll ich mit list aus STL arbeiten? Ich könnte dann jede Zeile als (doppelt) verkettete Liste anlegen, aber brauche ich das? Eigentlich benötige ich doch die Information von oben nach unten.

    Mir fehlt noch das Know How, um bei solch einem Vorhaben einschätzen zu können, mit welchen Mitteln ich arbeite.

    Gruß,
    Klaus.


  • Mod

    Wie wäre es mit einem set, wenn man einen Baum möchte?



  • SeppJ schrieb:

    Wie wäre es mit einem set, wenn man einen Baum möchte?

    Wie meinen?

    Ich speichere die Elemente in dem set. Set hat glaube ich den Vorteil, dass sie gleich sortiert sind.

    Und wo speichere ich dann die Partialsummen von je zwei Elementen? Und wo die Partialsummen von je zwei Elemente von je zwei Elementen...?

    Auch in dem set oder soll ich dann ein neues anlegen?

    Ich bin verwirrt. 😕

    Gruß,
    Klaus.


  • Mod

    Klaus82 schrieb:

    SeppJ schrieb:

    Wie wäre es mit einem set, wenn man einen Baum möchte?

    Wie meinen?

    Ich speichere die Elemente in dem set. Set hat glaube ich den Vorteil, dass sie gleich sortiert sind.

    Und wo speichere ich dann die Partialsummen von je zwei Elementen? Und wo die Partialsummen von je zwei Elemente von je zwei Elementen...?

    Auch in dem set oder soll ich dann ein neues anlegen?

    Ich bin verwirrt. 😕

    Gruß,
    Klaus.

    Ahh, ok. Anderer Vorschlag: Wieso willst du hier überhaupt einen Baum? Pack doch deien Zahlen in einen Vector. Dann machste einen zweiten vector, halb so groß, jedes Element ist die Summe zweier Elemente aus dem ersten Vector. Fortfahren bis Größe 1 erreicht ist. Dann hast du all die Werte die du berechnen wolltest ohne jeden Overhead.



  • SeppJ schrieb:

    Ahh, ok. Anderer Vorschlag: Wieso willst du hier überhaupt einen Baum? Pack doch deien Zahlen in einen Vector. Dann machste einen zweiten vector, halb so groß, jedes Element ist die Summe zweier Elemente aus dem ersten Vector. Fortfahren bis Größe 1 erreicht ist. Dann hast du all die Werte die du berechnen wolltest ohne jeden Overhead.

    Jap,
    an soetwas dachte ich auch schon.

    Ich muss nur später noch eine Suchfunktion definieren, die wie folgt aussieht:
    Die Wurzel ist die Summe aus allen Elemnten, nennen wir sie SUM. Das ganze soll in einen Monte Carlo Code eingebettet werden, d.h. ich erzeuge eine Zufallszahl u\in [0,1] und berechne damit u*SUM und nennen es SUCH = u * SUM
    Jetzt soll die Suchfunktion wie folgt vorgehen:

    Ist SUCH kleiner als der Wert im linken Kind, so wird auf diesen Knoten übergewechselt. Ist SUCH größer als der Wert im linken Kind, wird auf das rechte Kind übergegangen und SUCH wir neu deklariert mittels SUCH = SUCH - Wert im linken Kind.

    So lange, bis ich bei einem ursprünglich eingefügten Element angelangt bin. Also irgendwie muss ich die einzelnen Knoten mit darüber und den Kindern darunter verknpüfen. Ich denke, wenn ich Vektoren nehme, dann kann ich das irgendwie über die Indizes regeln.

    Zusätzlich sollen noch neue Elemente eingefügt werden können.

    Gruß,
    Klaus.



  • Vielleicht besser, nur einen vector zu nehmen. Der hat dann struct{int summe,int wert} drin. Und wie einen Heap aufbauen. http://de.wikipedia.org/wiki/Kekulé-Nummer
    root=1
    leftChild(x)=x2
    rightChild(x)=x
    2+1
    parent(x)=x/2
    0 wird einfach nicht verwendet, damit die Rechnung einfacher ist.



  • Hi,

    volkard schrieb:

    Vielleicht besser, nur einen vector zu nehmen. Der hat dann struct{int summe,int wert} drin. Und wie einen Heap aufbauen.

    An soetwas hatte ich auch schon gedacht.

    Also ich dachte an einen Vektor, der mit Pointern gefüllt ist, die wiederum auf Vektoren zeigen.

    Gruß,
    Klaus.



  • Klaus82 schrieb:

    volkard schrieb:

    Vielleicht besser, nur einen vector zu nehmen. Der hat dann struct{int summe,int wert} drin. Und wie einen Heap aufbauen.

    An soetwas hatte ich auch schon gedacht.

    Uups, habe struct ja gar nicht gelöscht.
    struct ist nicht nötig. Nur die ints. Die unterste Ebene sind Werte. Alle oberen Ebenen sind Summen.

    //nur so als idee
    void increaseValue(size_t index,int diff){
       do{
          vec[index]+=neuWert;
          index/=2;
       }while(index>=1);
    }
    void pushNewValue(int value){
       isPowerOfTwo(size){
          vector<int>(2*size) ov;
          swap(vec,ov);
          for(size_t i=0;i!=size;++i)
             increaseValue(i,ov[i]);
       }
       increaseValue(size,value);
       ++size;
    }
    

    fühlt sich doch ganz kuschelig an.



  • Hi,

    tut mir leid, dass ich mich so lange nicht gemeldet hatte.

    Ich habe zu diesem Vorschlag ein paar Fragen

    void increaseValue(size_t index,int diff){
    

    Hier verstehe ich nicht die Deklaration von diff, da es in der Methode nicht mehr verwendet wird.

    vec[index]+=neuWert;
    

    neuWert wurde vorher nicht initialisiert?

    index/=2;
    

    Diese Notation verstehe ich auch nicht. Meinst du vielleicht != ?

    isPowerOfTwo(size){
    

    Size wurde auch nicht initialisiert?

    swap(vec,ov);
    

    Muss dann vec nicht an die Methode übergeben werden und somit als weiteres Argument an pushNewValue übergeben werden?

    Bitte nicht falsch verstehen, ich möchte nicht meckern. Das ganze in ein vollständiges Programm zu implementieren ist meine Arbeit. Nur wundere ich mich eben, ob ich manche Sachen nicht verstehe, weil sie zu kurz gehalten sind und ich sie eben sinnvoll ergänzen muss oder doch etwas unvollständig ist.

    Gruß,
    Klaus.



  • Klaus82 schrieb:

    Ich habe zu diesem Vorschlag ein paar Fragen

    void increaseValue(size_t index,int diff){
    

    Hier verstehe ich nicht die Deklaration von diff, da es in der Methode nicht mehr verwendet wird.

    War erst neuWert, habe in diff umgenannt. Und im Code aus versehen neuWert stehen lassen.

    Klaus82 schrieb:

    vec[index]+=neuWert;
    

    neuWert wurde vorher nicht initialisiert?

    Ja, soll ja auch diff heißen.

    Klaus82 schrieb:

    index/=2;
    

    Diese Notation verstehe ich auch nicht. Meinst du vielleicht != ?

    Aber einen Absatz höher das += verstehst Du? So geht auch /=.

    Klaus82 schrieb:

    isPowerOfTwo(size){
    

    Size wurde auch nicht initialisiert?

    Ist wohl ein Attribut der Klasse, die ich mir dabei dachte. Oder eigentlich vec.size().

    Klaus82 schrieb:

    swap(vec,ov);
    

    Muss dann vec nicht an die Methode übergeben werden und somit als weiteres Argument an pushNewValue übergeben werden?

    Ist wohl ein Attribut der Klasse, die ich mir dabei dachte.

    Klaus82 schrieb:

    Nur wundere ich mich eben, ob ich manche Sachen nicht verstehe, weil sie zu kurz gehalten sind und ich sie eben sinnvoll ergänzen muss oder doch etwas unvollständig ist.

    Mein Code ist total unvollständig. Der sollte nur die Idee illustrieren, mehr nicht.



  • Hi,

    index/=2;
    

    Aber einen Absatz höher das += verstehst Du? So geht auch /=.

    Also

    vec[index]+=neuWert;
    

    bedeutet 'ausgeschrieben' so viel wie:

    vec[index] = vec[index] + neuWert;
    

    Bedeutet die Notation mit dem Slash dann analog:

    vec[index] = vec[index] / neuWert;
    

    Den Wert im Vektor an der Stelle index durch neuWert teilen und dann wiederum an der Stelle index im Vektor speichern.

    Gruß,
    Klaus.



  • Hi,

    also ich habe weiterhin über die Technik nachgedacht, dabei fiel mir eine Sache noch auf.
    Diese ganzen Werte sind Eigenschaften einer Klasse. Das bedeutet, wenn ich diesen Heap aufgebaut hätte und von oben nach unten den Baum durchgelaufen wäre, dann muss ich von dem gefunden Wert zurück zu der Klasse von der er stammt. Also müsste ich irgendwie noch den zugehörigen Zeiger speichern?

    Ich denke dieser Baum ist einfach eine Technik um folgendes zu erreichen.

    Ich nehme von den verschiedenen Objekten (Klassen) einen Wert w_i und summiere alle auf W=sum w_i .
    Dann nehme ich eine Zufallszahl u zwischen Null und Eins und wende sie auf W an: u*W.Damit erreiche ich eines der obigen w_i .

    Dieses würde ich gerne finde und dann auf die zugehörige Klasse zugreifen.

    Gruß,
    Klaus.



  • Also es wird wohl als
    rejection-free "residence-time" procedure bezeichnet oder BKL algorithm oder "n-fold way" algorithm.

    Das kann ich auch alles in google eingeben und finde jede Menge Paper, doch keine C++ Codes. 😞

    Das Suchwort code oder sourcecode bringt es auch nicht.

    Gibt es spezielle Seiten, wo Sourcecodes o.ä. angeboten werden?

    Kann doch nicht sein, dass ich da das Rad neu erfinden muss, wenn das Ding seit 1975 eine Standard Methode sein soll. 😮

    Gruß,
    Klaus.



  • Hi,

    was lange währt wird endlich gut. Tatsächlich habe ich solch ein Paket gefunden, das unter anderem einen BKL Algorithmus anbietet, nämlich hier aka SPPARKS.

    Das ganze ist auch recht schnell heruntergeladen, entpackt und tatsächlich finden sich im Verzeichnis /src zwei Dateien, welche diesen binären Baum darstellen:

    solve_tree.h
    

    und

    solve_tree.cpp
    

    .

    Jetzt frage ich mich als Laie natürlich nur, wie ich das ganze verwende. Also solve_tree.cpp verweist wieder zurück auf die Headerdatei solve_tree.h, die wiederum auf solve.h verweist, wo scheinbar grundlegend die Klasse definiert wird.

    Leider finde ich im Verzeichnis /examples keine Beispiele, in denen diese Routinen verwendet werden. Entweder ist mein find-fu zu schlecht oder es ist nicht möglich in den kompilierten Dateien zu suchen 😕

    Die Dokumentation aka Manual.pdf in /doc gibt leider auch nicht viel mehr her, als das es lediglich die einzelnen Dateien ein wenig in ihrem Tun erklärt. 😞

    Finde sich vielleicht jemand, der mit mehr Erfahrung das ganze sicherlich schnell erfassen und überblicken kann, der mir ein wenig Anleitung gibt wie ich diese Routinen zusammenbauen kann? Muss ich dazu SPPARKS als Bibliothek einbinden? Ich habe das Gefühl es reicht, wenn ich solve_tree.cpp mittels #include einbinde, nur dann muss ich den Syntax verstehen.

    Ein Minimalbeispiel wäre ja einfach nur die Erstellung von sagen wir 10 Zahlen, die dann in diesem Baum gespeichert werden und von denen ich mittel der Erzeugung einer Zufallszahl wieder eine finde.

    Heißen Dank für jegliche Hilfe im Voraus.

    Viele Grüße,
    Klaus.


Log in to reply