Syntaxbaumtiefe

Worum geht es?

Ein vollständiger binärer Baum der Tiefe d besitzt bis zu 2^d − 1 Knoten und damit höchstens 2^d − 1 Blattpositionen. Umgekehrt heißt das: Um b Blätter unterzubringen, braucht ein binärer Syntaxbaum mindestens die Tiefe

MinTiefe = ⌈log₂(b + 1)⌉.

Diese Untergrenze ist der bestmögliche Fall — etwa bei einem ausbalancierten Ausdrucksbaum. Reale Syntaxbäume sind oft tiefer, weil Operator-Assoziativität und Präzedenz die Form vorgeben. Die Formel liefert dennoch eine harte untere Schranke, die für Speicheranalysen und für die Auslegung eines Stack-basierten Auswerters (max. Stackgröße ≈ Baumtiefe) ausreicht.

Die Formel

MinTiefe = ⌈log₂(Blaetter + 1)⌉

Umstellung:
    Blaetter = 2^MinTiefe - 1

Die Variablen

Minimal-Beispiel

Ein AST mit 7 Blättern:

MinTiefe = ⌈log₂(7 + 1)⌉
         = ⌈log₂(8)⌉
         = 3

Praxis-Beispiele

Beispiel 1 — Ausdrucksbaum

Ein binärer Ausdrucksbaum für a + b * c - d / e hat 5 Operanden-Blätter:

MinTiefe = ⌈log₂(6)⌉
         = ⌈2,58⌉
         = 3

Beispiel 2 — Stack-Größe abschätzen

AST eines größeren Statements mit 1 000 Blättern:

MinTiefe = ⌈log₂(1001)⌉
         = 10

→ Auswerter-Stack mindestens 10 Frames.

Beispiel 3 — Blätterkapazität bei fester Tiefe

Eine eingebettete Auswertung erlaubt maximal Tiefe 8:

Blaetter = 2^8 - 1
         = 255