PureBoard

Verfasst: **04.12.2009 17:27**

Josef Sniatecki hat geschrieben:
DarkDragon hat geschrieben: Aber da würde der AVL Baum die Prioritäten der Operationen durcheinanderbringen und eventuell wären dann Operatoren plötzlich Blattknoten was nicht sein kann bei Infix. Immerhin geht der Parser/Interpreter dann durch den Baum durch und Rechnet bei einem "+" Knoten dann LinkerTeilbaum + RechterTeilbaum.
OK, ehrlich gesagt verstehe ich jetzt immer noch nicht den Unterschied zwischen einem AVL-Baum und dem
Syntaxbaum, den ich verwendet habe. Die Operatoren sind in meinem Fall Knoten, die maximal zwei weitere
Unterknoten besitzen können, die genau eine Ebene darunter liegen...

Der Syntaxbaum wird nicht balanciert. Wenn du einen neuen Knoten in den AVL Baum einfügst, dann prüfst du bis zur Wurzel ob ein Knoten unbalanciert ist. Wenn ja rotiere ihn damit der Knoten wieder balanciert ist. D.h. angenommen du hast einen Syntaxbaum der so aussieht:

Code: Alles auswählen

      +
   a     *
        c  d

Und du willst nun auf d noch e addieren vor dem multiplizieren mit c, dann entsteht folgender Syntaxbaum:

Code: Alles auswählen

Doch der ist unbalanciert und würde als AVL Baum dann so rotiert werden:

Code: Alles auswählen

       *
   +       +
 a   c    d   e

Dann wäre der Ausdruck nichtmehr a + c * (d + e) sondern (a + c) * (d + e) und entspräche etwas ganz anderem.

Ein Ausdrucksbaum ist auch nicht nur in Binärbaum. Nehmen wir einmal an du hast einen Funktionsaufruf in deinem Ausdruck, dann hast du einen Baum mit mehr als 2 Nachfolgern:
testfkt(a, b, c, d)

Code: Alles auswählen

          testfkt
   a      b      c      d

Verfasst: **04.12.2009 23:07**

Jetzt hats bei mir "Klick" gemacht

Danke für die ausführliche Erklärung. Jetzt verstehe ich auch, wieso ein AVL-Baum so viel Arbeit bedeutet.

Nur so am Rande: Das mit den mehreren Parametern für Funktionsaufrufe löst man gerne durch einen Stack, der duch aufeinanderfolgende "Push"-Nodes (Ein Knoten mit einem Unterknoten (der Parameter)) gefüllt wird. D.h. zur Ausführung braucht man im Prinzip wirklich nur maximal zwei child nodes.

Verfasst: **05.12.2009 13:00**

Josef Sniatecki hat geschrieben:Nur so am Rande: Das mit den mehreren Parametern für Funktionsaufrufe löst man gerne durch einen Stack, der duch aufeinanderfolgende "Push"-Nodes (Ein Knoten mit einem Unterknoten (der Parameter)) gefüllt wird. D.h. zur Ausführung braucht man im Prinzip wirklich nur maximal zwei child nodes.

Das löst dann aber der Kompiler. Ein Ausdrucksbaum wird aber davor benötigt. Der Baum wird dann optimiert vom Compiler und jeder Knoten hat sozusagen eine Methode "compile" dann wird der Code generiert (von einem bestimmten Knoten inklusive seiner Kinder). Vielleicht übersetze ich meinen Matheparser mal, das könnte man leicht verändern und man hätte schon einen richtigen Kompiler für eine Programmiersprache.

PureBoard

AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum