Baumklasse

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