Probleme mit Template-Bibliothek

[Sven Rautenberg]

Hallo Sven,

Wenn du sowohl schnelle Einfügezeiten als auch schnelle Suchzeiten haben
willst, dann bieten sich Bäume als Speicherstruktur an.

*seufz* Danke.
Da sieht man mal wieder, wie Betriebsblindheit sich auswirken kann... vor
allem, weil sortierte Felder im Grunde nichts anderes als Baeume sind (darauf
basiert Binary Search ja), ich also im Grunde diese Idee schon verfolgt habe
und nur eine andere Darstellungsform waehlen muss...

Tja, im Bretter vom Kopf abreißen bin ich ganz groß - bei anderen. ;)

Typisches IF-Konstrukt:
IF (ausdruck) THEN (then-anweisung) ELSE (else-anweisung)

Ein "passender" Baum:
  Knoten 3 (Typ IF)
     /         \   (ausdruck)  THEN
              /   \ (then-anweisung) (else-anweisung)

Wie gesagt, es ging mir nicht um die Darstellung des True- bzw. False-Zweiges,
sondern um die Darstellung von 'ausdruck'. Wie stelle ich AND, OR, XOR dar,
wie werte ich die komplette Bedingung aus?

Du brauchst (und hast hoffentlich schon) einen Knoten-Typ zum Rechnen. Wie sonst sollte dein Beispiel SET sonst gehen?

Ein ganz altes Beispiel in Turbo-Pascal für einen Funktionsplotter (um beliebige Funktionen wie z.B. f(x)=x^2+sin(x/3)+e^x aufgrund Usereingabe zu plotten) hat mal ein heftiges Baumkonstrukt mit varianten Records gebastelt - je nach Funktion. Und der Ausdruck wurde dann geparst und als Baum aufgebaut, wodurch dann gleich die Berechnungsvorschrift entstand: Erst den einen Teilbaum berechnen, dann den anderen Teilbaum berechnen, und dann die Berechnungsvorschrift des aktuellen Knotens auf beide Subergebnisse anwenden.

Die Formel von oben würde sich ungefähr so "aufbäumen":

f(x)
                   |
         -------(  +  )-------
         |                   |
   ---(  ^  )---       ---(  +  )---
   |           |       |           |
  (x)         (2)  --(sin)--   --( ^ )--
                   |           |       |
               --( / )--      (e)     (x)
               |       |
              (x)     (3)

Die Klammern zeigen immer ein Knotenelement - entweder eine Konstante, eine Variable, oder eine Rechenoperation. Gemäß irgendwelcher Gesetzmäßigkeiten arbeiten mathematische Funktionen in der Regel mit maximal zwei Operanden (alles andere läßt sich als Verkettung von jeweils zwei Operationen darstellen). Das zu Evaluieren funktioniert, wie oben dargestellt.

Es ist jetzt "nur noch" deine Aufgabe, die Knoten entsprechend zu behandeln und z.B. Knotentypen und Knotenauswertelogik für AND, OR, XOR, ==, !=, <, > etc. herzustellen.

Ist doch "ganz einfach"[tm]. ;)

- Sven Rautenberg