(binär-)bäume

StarCraftFeuerteufel

also ich möchte mir gerne eine intelligente gut durchdachte/strukturierte objekthierarchie programmieren, die mittels vererbung so ziemlich alle möglichen bäume abhandeln kann (suchbaum, rot-schwarzbäume, AVL-bäume, etc.).
also die einzelnen baumarten hab ich teilweise schon separat programmiert, aber da ist halt viel code der im prinzip doppelt ist, was ich durch vererbung etc. wegbekommen möchte. das problem ist soweit ich es sehe, das jede baumart so ihre eigenen speziellen knoten hat, die mit mehr oder weniger zusätzlichen daten ausgestattet sind im vergleich zu einem ganz einfachen baumknoten, wo nur der elternknoten und die kinderknoten gespeichert werden.
nun wollte ich gern wissen ob, und wenn wie, es möglich ist das möglichst effizient zu lösen ohne viel doppelten code zu haben.
z.B. hat jede baumart die methode get_root(), die die wurzel liefert, allerdings ist der rückgabetyp bei jeder baumart halt der jeweilige knotentyp.
ich hatte mir ja gedacht das vllt sowas wie templates möglich sind, aber wie genau weiß ich noch nicht.
also die knoten kann ich kann ich voneinander ableiten, aber wie ich das dann effizient in eine ableitungsstruktur von bäumen einbauen kann, ist mir noch nicht so recht eingefallen.
also falls wer eine intelligente lösung hat immer raus damit. vielen dank schonmal im voraus.

Th

Also wenn du Vererbung einsetzen willst, dann solltest du dir ersteinmal einen Anwendungsfall definieren, um dann eine geeignete Schnittstelle (Interface) zu definieren (dies könnte dann eine virtuelle Basisklasse sein).
Dann evtl. noch entsprechende Iteratoren zum Traversieren etc.

Bei einer Template-Implementierung könntest du dich ja an die STL (bzw. C++ Standard Bibliothek) halten, z.b. die Klasse std::map.

Welche Lösung du wählst hat vor allem damit zu tun, ob du Änderungen (des internen Baumtyps) zur Laufzeit zulassen willst oder nicht.

Wenn es dir jedoch mehr um die Umstrukturierung deines Source-Codes geht, dann solltest du evtl. einfach geeignete Hilfsklassen bzw. -funktionen definieren.

StarCraftFeuerteufel

ok, damit ist aber immernoch nicht mein problem gelöst, das jeder baum verschiedene knotentypen hat oder ich versteh deinen vorschlag nicht ganz.

hustbaer

Ich würde garnicht vererbung verwenden, sondern nur templates.
Mit templates kannst du ja "duck typing" machen, d.h. ob die Knoten etc. nun verwandt sind oder nicht ist egal, solange sie alle nötigen Methoden implementieren (Name+Signatur muss passen, das reicht).

StarCraftFeuerteufel

was soll denn "duck typing" sein, hab ich noch nie gehört.

junge.... Wie wärs wenn du mal deinen Kopf zum Nachdenken benutzt und nciht nur fragen stellst auf die du selber antworten finden kannst?

otze

vorallem, wenn die antwort noch in derselben Zeile steht.

mal ein Beispiel:

struct A
{
    int foo;
};

struct B
{
    int foo;
};

template<class T>
class Bar
{
    T foobar;

    public:
    void function()
    {
        foobar.foo=5;//funktioniert, solange T ein member foo hat.
    }
};

//im code;
Bar<A> a;
Bar<B> b;
a.function();
b.function();

Und sowas lässt sich halt in diesem Fall ziemlich gut anwenden.

StarCraftFeuerteufel

ok, dann werd ich es mal so probieren.

hustbaer

"if it walks like a duck, and quacks like a duck, it must be a duck"

http://en.wikipedia.org/wiki/Duck_typing

BTW: das "hustbär" Posting ist nicht von mir.

StarCraftFeuerteufel

mir ist jetz noch ein anderes problem mit den knoten aufgefallen. und zwar hat ja jeder knoten eltern- und kinderknoten vom gleichen typ wie der knoten. dh wie mache ich denn das wenn ich die knoten voneinander ableite, aber trotzdem bei den funktionen get_parent() und get_child() der entsprechende typ zurückgegeben wird?

class A
{
  private:
    A* parent;
//...
  public:
    A* get_parent();
};

class B : public A
{
};

class C : public B
{
};

also ich möchte das jede klasse quasi nur zeiger ihres eigenen typs hat, d.h. in B sollte parent vom typ B* sein und nicht vom typ A*. kann man das irgendwie hinbekommen, ohne in jeder klasse parent neu zu definieren?

hustbaer

@FreakyBKA :

get_parent() in der Basisklasse zu haben macht IMHO nur Sinn wenn get_parent() auch "virtual" ist (). In dem Fall kannst du es überschreiben. Wenn der override dann ein Derived statt einem Base* zurückliefert nennt man das einen "covariant return type" (ein Derived ist ja auch ein Base, daher ist das Überschreiben erlaubt) Wird allerdings nicht von allen Compilern unterstützt.

(*): "virtual" ist in dem Fall aber doof, da es u.U. deutlich langsamer sein wird. Ohne virtual könnte der Compiler sehr schön inlinen und u.U. manche Teile ganz wegoptimieren.

Ich weiss auch nicht was da bei verschiedenen Baumarten viel an Gemeinsamkeiten vorhanden sein soll wo man Code mehrfach verwenden könnte... gerademal dass jeder Knoten ein Parent hat, aber das war's dann auch schon. Gibt ja Bäume wo jeder Knoten gleich ist (=auch innere Knoten haben Werte), und Bäume wo es unterschiedliche Knoten gibt. Und sogar Bäume wo ein Knoten mehr als nur einen Wert haben kann. Und die Algorithmen (Einfügen, Löschen, nächsten Wert finden etc.) sind auch ziemlich anders, zumindest anders genug als dass man kaum mal bei 2 oder 3 Bäumen 1:1 den gleichen Code verwenden könnte...

StarCraftFeuerteufel

ja da hast du wahrscheinlich nicht ganz unrecht, naja, dann muss ich wohl doch alles einzeln lassen

hustbaer

Naja, wenn du erstmal alles implementiert hast, siehst du eh wo Code dupliziert ist. Den kannst du dann ja in irgendwelche Basisklassen und/oder Templates packen