Baumklasse

Walli

Ich hänge auch schon eine ganze Zeit an dem Problem, dass es keine gescheiten Baumklassen gibt, bzw. dass die meist unter Lizenzen wie der GPL stehen und demnach wertlos für mich sind, da ich gerne auf der Arbeit mit den gleichen Sachen arbeite wie zu Hause. Habe angefangen selber was zu basteln, aber wirklich universell einsetzbar ist das Ding leider nicht geworden.
Es gibt da boost::graph, das finde ich aber irgendwie für manche Dinge nur eingeschränkt geeignet, da die Lib vom Aufbau her sehr stark auf Graph-Algorithmen wie Dijkstra, TSP etc. ausgelegt ist.
Manchmal will man aber einfach auch mal z.B. eine verzweigte Struktur (Verzeichnis, Stammbaum, ...) speichern, möglichst einfach bearbeiten und mit einem Pre/PostOrder/BreathFirst-Iterator o.ä. drüberwandern. Wäre eigentlich auch ein Fall für boost. Habe irgendwann mal in der mailing list gelesen, das diese tree-Klasse relizensiert und bei boost aufgenommen werden sollte. Was daraus geworden ist, keine Ahnung... zumindest ist sie noch nicht in der boost-lib aufgetaucht.
Naja, bin jedenfalls sehr gespannt ob sich im weiteren Verlauf dieses Threads die ultimative Lösung bietet .

PS: Wie wäre es so ein Ding mit mehreren Leuten aus dem Forum zu entwickeln und unter eine vernünftige Lizenz zu stellen, die den Einsatz in Projekten aller Art erlaubt? Kann mir nicht vorstellen, dass nur 2 Leute an so einer Klasse Interesse hätten.

EDIT 1-3: Deutsche Sprache schwere Sprache .

Eine Liste ist doch kein Knoten.

DrGreenthumb

node schrieb:

Eine Liste ist doch kein Knoten.

hm, ja, mit der namensgebung war ich mir auch unsicher.

vorschläge sind willkommen

Helium

Wieso kann eine Liste kein Knoten im Baum sein?

Aber irgendwie gefällt mir der Aufbau auch nicht so recht.
Vielleicht ein boost::variant<Item, List> als interneStruktur verwenden?

Walli

Die Idee mit Variant ist echt nicht schlecht. Wie wäre es mit so etwas in der Art?

template<typename T>
class Tree
{
  typedef typename boost::make_recursive_variant<
   T, std::vector<boost::recursive_variant_>
   >::type NodeT;

  std::vector<NodeT> nodes;
};

Aber dann hat ja ein Node keinen Wert, wenn er Kinder hat. Auch irgendwie nicht so optimal.

DrGreenthumb

Danke, mit variant hab ich jetzt was gebaut. Genaugenommen habe ich nur das int-tree-boost-Beispiel, was es da schon gab, genommen und in eine Klasse gelegt

MaSTaH schrieb:

Aber dann hat ja ein Node keinen Wert, wenn er Kinder hat. Auch irgendwie nicht so optimal.

Nee, das soll ja auch so sein.
Sonst würde ich ja einfach struct Node { list subnodes; T value }; machen.

Falls es jemanden interessiert, hier jetzt mal die gesammte Klasse. Auf den ersten Blick schonmal wesentlich hübscher...

template<class T>
struct tree
{
    typedef typename boost::make_recursive_variant
        <
          T,
          std::list<boost::recursive_variant_>
        >::type node;

    typedef std::list<node> list;

    struct node_dump : public boost::static_visitor<>
    {
        std::ostream& out;
        node_dump(std::ostream& out) : out(out) {}
        void operator()(const T& val);
        void operator()(const list& val);
    };

    // muss hier lieder statisch rein, weil sich nicht auf tree<T>::list überladen lässt :-(
    static std::ostream& dump(std::ostream& out, const list& l)
    {
        node_dump d(out);
        out<<"(";
        for(typename list::const_iterator i=l.begin(); i!=l.end();) {
            boost::apply_visitor(d, *i);
            if(++i != l.end())
                out<<' ';
        }
        out<<")";
        return out;
    }
};

template<class T>
void tree<T>::node_dump::operator()(const T& val) {
    out<<val;
}

template<class T>
void tree<T>::node_dump::operator()(const list& l) {
    dump(out, l);
}

int main()
{
    tree<int>::list top, sub;

    sub.push_back(2);
    sub.push_back(3);

    top.push_back(1);
    top.push_back(sub);
    top.push_back(4);

    tree<int>::dump(std::cout, top);
}

ness

Nun will ich aber auch mal eine Frage loswerden, auch wenn ich nicht alles gelesen habe: warum macht ihr das ganze so kompliziert? Soweit ich das sehe, wollt ihr in jedem Baum nur einen Datentyp, aber eine unbestimmte Menge an Verzweigngen pro knoten zulassen?

template<class T,bool multiple_entries>
class baum
{
private:
    struct node_a
    {
        std::vector<node*> next;
        T the_worth;
    };
    struct node_b
    {
        std::vector<node*> next;
        std::vector<T> the_worth;
    };
    typedef typename Loki::Select<multiple_entries,node_b,node_a>::Result node;
    node* base;
public:
    //der Rest halt
};

spjoe

Frage:

Weil wir garde beim thema baum sind gibt es einen dynamischen ausbalancierten mehrwegbaum der das verhältnis höhe und element pro knoten so hält das der baum immer den kleinst möglichen worst case hat?!

Wenn ja bitte einen link zum source

Walli

ness schrieb:

Nun will ich aber auch mal eine Frage loswerden, auch wenn ich nicht alles gelesen habe: warum macht ihr das ganze so kompliziert?

Was ist denn daran kompliziert, bzw. in deiner Version einfacher?

Walli

spjoe schrieb:

Wenn ja bitte einen link zum source

http://www.google.de/search?hl=de&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=B+Tree+C%2B%2B&btnG=Suche&meta=

ness

MaSTaH schrieb:

ness schrieb:

Nun will ich aber auch mal eine Frage loswerden, auch wenn ich nicht alles gelesen habe: warum macht ihr das ganze so kompliziert?

Was ist denn daran kompliziert, bzw. in deiner Version einfacher?

Wie gesagt, ich hab net alles gelesen. Aber bei dem brauch ich weder dynamic_cast oder boost::variant, sondern nur stinknormalen code.

spjoe

thx für link
Aber ich suche keinen Bayerbaum suorce (Balanced multiway tree) den hab ich schon
Ich will etwas bessers als einen B-Baum
nämlich das die unter und obergrenze der elementanzahl pro knoten dynamisch ist
Ich weiss gar nicht ob das geht aber es wäre zumindest sehr

DrGreenthumb

ness schrieb:

Aber bei dem brauch ich weder dynamic_cast oder boost::variant, sondern nur stinknormalen code.

ness schrieb:

typedef typename Loki::Select<multiple_entries,node_b,node_a>::Result node;

hm, naja...

der zuletzt von mir gepostete code ist ja auch nur so groß, wegen dem ausgabe-kram.
Da ist die eigentliche tree-Klasse sogar kürzer