Umsortierung von Binären Bäumen



  • Hallo, ich suche nach einer Idee für eine gute Sortiermöglichkeit. Ich versuchs mal zu formulieren 😃

    Es wird ein Binärer Baum erzeugt. Anschließend wird eine Zeichenkette bzw. eine Textdatei eingelesen. Die einzelnen Zeichen werden dann im Baum aufgenommen. Nun wird es vorkommen, dass ein Zeichen doppelt vorkommt und sich die Anzahl erhöht. Im Klartext muss also mit einem struct(Zeichen und Anzahl) gearbeitet werden. Nachdem die Anzahl erhöht wurde, soll der Buchstabe jedes Mal neu nach der Anzahl einsortiert werden. Das heißt, dass der innere Knoten bzw. das Blatt umgehängt wird.

    Das Umhängen stellt noch ein paar Schwierigkeiten dar...

    Meine Vorschläge:

    1. Es wird jedes Mal der Knoten als Wurzel genommen, wenn er größer als die Wurzel selber ist. Ist der Knoten kleiner so wird er eingeordnet. Links, wenn die Anzahl kleiner als der Knoten am rechten Zweig ist bzw. andersrum.

    Ich brauche keine Musterlösung oder Code. Das kann ich selber 😃

    Ich brauche lediglich einen Vorschlag :p



  • Mir ist noch nicht ganz klar, was die Datenstruktur leisten soll. Wie sieht denn die Schnittstelle aus?



  • Das klingt nach Heapsort.



  • 1. Es gibt ein Struct für Key für Zeichen und Anzahl.
    2. Es gibt ein Struct für den Baum mit Key und link, rechts(Teilbaum).

    Es soll nach der Anzahl geordnet werden. Normalerweise ordnete ich es mit Preorder (Wurzel-linker Teilbaum-rechter Teilbaum) ein. Das soll weiterhin auch geschehen, aber wenn nun ein Buchstabe mehrfach vorkommt, so soll er auch oben im Baum liegen und nicht irgendwo verstreut sprich sortiert. Hoffe es hilft ein wenig.



  • ich war eigentlich nur erst mal an der Schnittstelle interessiert. Du willst gewisse Operationen durchführen und dahinter steckt dann irgend eine Datenstruktur (eventuell ein Baum, muss aber nicht). Ich wollte nur wissen, was für Operationen das sein sollen. OK, Du schiebst da irgendwie Buchstaben rein und mehrfaches Auftreten wird mitgezählt. Und dann? Was willst Du damit machen? Da muss ja jetzt noch irgendwas kommen, denn sonst könntest Du auch einfach eine map<char,int> nehmen.



  • Es wird ein Binärer Baum erzeugt. Anschließend wird eine Zeichenkette bzw. eine Textdatei eingelesen. Die einzelnen Zeichen werden dann im Baum aufgenommen. Nun wird es vorkommen, dass ein Zeichen doppelt vorkommt und sich die Anzahl erhöht. Im Klartext muss also mit einem struct(Zeichen und Anzahl) gearbeitet werden. Nachdem die Anzahl erhöht wurde, soll der Buchstabe jedes Mal neu nach der Anzahl einsortiert werden. Das heißt, dass der innere Knoten bzw. das Blatt umgehängt wird.

    Schnittstelle

    Und dann? Was willst Du damit machen?

    Einen Baum im Heap haben, der die Buchstaben aus einer beliebigen Quelle ( Eingabe o. Textdatei) verwaltet und sie Absteigend nach der Häufigkeit im Baum auflistet.



  • 🙄
    Ich geb's auf.



  • Wenn ich dich richtig verstehe ist dein erster Vorschlag doch genau das, was du suchst, oder nicht?
    Knoten rausnehmen. um 1 erhöhen. Knoten wieder einsortieren.



  • @ DerBaer: 100% in das Schwarze. Es soll ein Knoten bzw. ein Blatt nachdem es rausgenommen wurde erhöht und wieder einsortiert werden. Genau das liegt das Problem. Wie soll ich die Knoten, die an dem rausgenommenen Element hingen bzw. hängen wieder korrekt an den Baum hängen? Ich kann doch nicht alles raushängen und wieder reinhängen. Das wäre bei Verwaltungen zum Beispiel glatter PC Mord.



  • Versuch mal genauer zu beschreiben, was Du eigentlich machen willst. Ich kann das aus den Bruchstücken an Infos, die hier verstreut sind, nicht zusammen setzen.

    1. Es gibt ein Struct für Key für Zeichen und Anzahl.
    2. Es gibt ein Struct für den Baum mit Key und link, rechts(Teilbaum).

    Es soll nach der Anzahl geordnet werden.

    Wie findest Du denn dann überhaupt den richtigen Knoten für ein bestimmtes Zeichen wenn Du nach der Anzahl sortierst ?

    Normalerweise ordnete ich es mit Preorder (Wurzel-linker Teilbaum-rechter Teilbaum) ein.

    "Preorder" ist keine Ordnung eines Baums, sondern beschreibt typischerweise in welcher Reihenfolge Elemente des Baums "behandelt" werden (zB behandeln = Ausgabe). Kommt bei Dir denn noch ein richtiger Suchbaum heraus?

    Ich habe den Eindruck, dass Du Dir selbst noch nicht im Klaren darüber bist, was Du eigentlich für eine Datenstruktor haben willst. Deswegen fragte ich ja ständig nach der Schnittstelle. Du willst die Datenstruktur ja nicht nur einfach so erstellen, sondern, weil Du damit etwas machen willst. Was Du damit wachen willst, ist noch nicht klar geworden. Mit "Schnittstelle" meine ich nicht, wie die Datenstruktor aussieht. Ich meinte damit das, was die Datenstruktor für Operationen bietet. ZB:

    SuperDuperDatenstruktur ds;  
      const char* s = "Dies ist ein Text";
      while (*s) ds.add(*s++);
      // Datenstruktur merkt sich, wie oft bestimmte Zeichen vorgekommen sind.
      // Was nun?
    

    Wenn Du nur hinterher die vorgekommenen Buchstaben der Haufigkeit nach ausgeben willst, kann man das so machen:

    #include <algorithm>
    #include <iostream>
    #include <map>
    #include <utility>
    #include <vector>
    
    using namespace std;
    
    struct pair2ndGreater
    {
      template<class T, class U>
      bool operator()(pair<T,U> const& a, pair<T,U> const& b) const
      { return a.second > b.second; }
    };
    
    int main()
    {
      map<char,int> histogramm;
      const char* s = "Dies ist ein Text";
      while (*s) ++histogramm[*s++];
      vector<pair<char,int> > vec (histogramm.begin(),histogramm.end());
      sort(vec.begin(),vec.end(),pair2ndGreater());
      for (int i=0, e=vec.size(); i<e; ++i) {
        pair<char,int> const& p = vec.at(i);
        cout << '"' << p.first << "\" --> " << p.second << '\n';
      }
    }
    

    Wenn Du ständig eine nach Haufigkeit sortierte Liste zur Verfügung haben willst, könntest Du einen Suchbaum mit einer Liste kombinieren. Jeder Knoten hätte dann noch einen next-Zeiger. Der Baum "sortiert" nach dem Zeichen, die Liste ist ständig sortiert nach Häufigkeit. Nach dem Erhöhen eines Haufigkeitswerts, muss der Knoten in der Liste eventuell verschoben werden (Bubble-Sort-mässig). Die "Baumzeiger" muss man dann aber nicht anfassen. Der Knoten bleibt im Baum an derselben Stelle.

    struct ding
    {
      char c;
      int hfk;
    };
    
    class SuperDuper
    {
      list<ding> list_;
      map<char,list<ding>::iterator> map_;
      ...
    };
    

    kk



  • jetzt weiß ich wo dein Problem liegt xD

    angenommen links sind die kleineren Zahlen und rechts die größeren. Dann nimmst du deinen Knoten raus. Danach suchst du dir den Knoten, der im rechten Teilbaum ganz links unten ist und hängst ihn dort ein, wo dein alter Knoten war.
    Dieser neue Knoten ist der kleinste, der größer als dein alter war(somit sind die Knoten die danach rechts sind größer) und die, die links sind, sind garantiert kleiner.

    Bsp.:

    13
              7                              17
      3             9                    14    19
                 8     11    
                     10  12
    

    (weil man das nicht so gut sieht nochmal die Verbinungen:
    13->7, 13->17, 17->14, 17->19, 7->3, 7->9, 9->8, 9->11, 11->10, 11->12)
    Wenn du die 7 rausnehmen willst, gehtst du in de nrechten Teilbaum(abb der 9) und suchst das ganz linke element(hier 8). dann ersetzt du die 7 durch die 8 und fertig



  • @krümelkacker Das soll nicht böse gemeint sein, aber ich sagte doch, dass Code nicht wesentlich ist 😃

    @DerBaer Das ist eine gute Überlegung. Immerhin hat man wenig mit Wiedereinsortierung zu kämpfen sondern tauscht nur. Hast du vlt. auch einen Vorschlag, wie man dann ohne es in eine Datei abzuspeichern und zu sortieren einfach den Baum auswiegt ( Oh je was ist das für ein Satz 😮 ). Ich habe eben überlegt und festgestellt, dass man es ähnlich wie bei dem Quicksort macht, sozusagen einen Pivot festlegt als Wurzel und die anderen so einsortiert bekommt, sodass der Baum ausgewogen im Modell aussehen würde.



  • 3dprogger schrieb:

    @krümelkacker Das soll nicht böse gemeint sein, aber ich sagte doch, dass Code nicht wesentlich ist 😃

    Das hast Du gesagt, ja. Die Idee war es, "C++ Code" unterstützend zu Deutsch zu verwenden, weil es so aussieht, als ob Du meine vorherigen Beiträge nicht verstanden hast. Meine Fragen bleiben übrigens immer noch unbeantwortet. Ich würde Dir ja gern helfen, dann musst Du Dir aber auch helfen lassen.



  • Ich denke du meinst das hier, oder?
    http://de.wikipedia.org/wiki/AVL-Baum#Rebalancierung

    Vielleicht gibt es in deinem Fall(da du Knoten immer um genau eins erhöhst) aber auch eine einfachere Methode, dass du nicht immer das Element entfernen, einfügen und neu balancieren musst(fällt mir nur gerade ein, weiß nicht ob es geht)



  • AVL-Bäume, keine Ahnung! 😃

    Hier mal die Aufgabe:

    http://www.myimg.de/?img=aufgabebinaerbaum3b427.jpg

    Das baut alles aufeinander auf.



  • 3dprogger schrieb:

    Hier mal die Aufgabe:
    http://www.myimg.de/?img=aufgabebinaerbaum3b427.jpg

    Wow. Was für eine beschissene Aufgabe. Die ist ja genauso vage formuliert wie das, was Du bisher so wiedergegeben hast. Sorry, das klingt echt so, als ob da jemand nicht zu Ende gedacht hätte. Wer stellt denn solche Aufgaben?



  • Mit "anschaulich" ist hoffentlich "balanciert" gemeint^^

    Dann solltest du dir den Artikel durchlesen(ein AVL Baum ist einfach ein ausgewogener Baum). Wichtig für dich sind v.a.
    1. Einfügen und Löschen von Elementen(ist im prinzip das, was ich oben geschreiben hab in etwas länger)
    2. Rebalancieren
    dabei schaut man sich an, wo 2 Teilbäume mehr als 1 höhenunterschied haben. Diese werden als "unschön" angesehen und deshalb wird rotiert, d.h. man verschiebt ein paar knoten um einen ausgewogenen Baum zu erhalten. Wie das genau geht steht in dem Artikel


Log in to reply