ABZÄHLPROBLEME BEI BÄUMEN

HELMUT PRODINGER (WIEN)

Es sei B die Familie der binären Bäume. B kann durch eine formale Gleichung beschrieben werden:

B  B + B =

Dies besagt, daß ein binärer Baum entweder ein Blatt (externer Knoten) ist, oder eine Wurzel zusammen mit einem linken und einem rechten Teilbaum, welche selbst binäre Bäume sind. Diese formale Gleichung kann übersetzt werden in eine Gleichung für die erzeugende Funktion B(z):

B(z) = 1 + zB^{2}(z);

B(z) = \frac{1 − \sqrt{1 − 4z}}{2z} = ∑_{n≥0} \frac{1}{n + 1} \binom{2n}{n}z^{n}.

Binäre Bäume können verwendet werden, um arithmetische Ausdrücke darzustellen:

[figure: ×; +; 3; 7; 4; ⟷; 3 × ( 7 + 4 )]

Die Auswertung kann mit Hilfe von Registern erfolgen; diese werden verwendet, um Zwischenergebnisse zu speichern.

Die Registerfunktion Reg(t) ist definiert als die minimale Anzahl von Registern zur Auswertung des Baumes t unter Verwendung der optimalen Strategie.

Es gilt:

Reg(□) = 0

t_{1}  t_{2}^{Reg(}  ) = { 1 + Reg(t_{1}) falls Reg(t_{1}) = Reg(t_{2}) max{Reg(t_{1}), Reg(t_{2})} sonst

Es sei R_{p} (S_{p}) die Familie der Bäume mit Registerfunktion = p (≥ p); R_{p}(z) und S_{p}(z) seien die entsprechenden erzeugenden Funktionen. Man sieht unmittelbar:

[figure: R_{p−1}; R_{p−1}; R_{p}; =; +; +; ∑_{j<p} R_{j}; ∑_{j<p} R_{j}; R_{p}; R_{p}]

[figure: S_{p−1}; S_{p−1}; S_{p}; =; +; +; B \ S_{p−1}; B \ S_{p−1}; S_{p}; S_{p}]

Daher gilt:

R_{p} = zR_{p−1}^{2} + 2zR_{p} ∑_{j<p} R_{j}, R_{0} = 1 ,

S_{p} = zS_{p−1}^{2} + 2zS_{p}(B − S_{p−1}), S_{0} = B ;

S_{p} = \frac{zS_{p−1}^{2}}{1 − 2zB + 2zS_{p−1}} .

Wir setzen ε := \sqrt{1 − 4z} = 1 − 2zB :

\frac{1}{S_{p}} = \frac{ε}{z} \frac{1}{S_{p−1}^{2}} + 2\frac{1}{S_{p−1}} .

Wir multiplizieren mit ε/z und substituieren U_{p} := ε/zS_{p}:

U_{p} = U_{p−1}^{2} + 2U_{p−1} ⇒ U_{p} + 1 = (U_{p−1} + 1)^{2} ⇒

U_{p} = −1 + (U_{0} + 1)^{2^{p}}; U_{0} = \frac{ε}{zB} ⇒

S_{p} = \frac{ε}{z} · \frac{1}{−1 + (\frac{1+ε}{1−ε})^{2^{p}}} .

Es ist günstig, z = u/(1 + u)^{2} zu setzen:

S_{p} = \frac{1 − u^{2}}{u} · \frac{u^{2^{p}}}{1 − u^{2^{p}}}

R_{p} = S_{p} − S_{p+1} = \frac{1 − u^{2}}{u} · \frac{u^{2^{p}}}{1 − u^{2^{p+1}}} .

Sei nun M_{n} die mittlere Registerfunktion eines binären Baumes mit n Knoten. Es gilt:

M_{n} = \frac{∑_{p≥0} p · [z^{n}]R_{p}(z)}{[z^{n}]B(z)} = \frac{[z^{n}] ∑_{p≥1} S_{p}(z)}{[z^{n}]B(z)} .

Wir studieren den Zähler:

E(z) = ∑_{p≥1} S_{p}(z) = \frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{2^{p}}}{1 − u^{2^{p}}}

= \frac{1 − u^{2}}{u} ∑_{{p≥1 \atop λ≥1}} u^{2^{p}λ}

= \frac{1 − u^{2}}{u} ∑_{k≥1} v_{2}(k)u^{k}

mit v_{2}(k) = ∑_{{k=2^{p}λ, \atop p,λ≥1}} 1 . (Beachte v_{2}(2n) = 1 + v_{2}(n), v_{2}(2n + 1) = 0.)

Um den Koeffizienten von z^{n} in E(z) zu finden, bedienen wir uns einer analytischen Methode. Das Verhalten der Koeffizienten wird nämlich weitgehend beschrieben durch das Verhalten der erzeugenden Funktion in der Nähe der Singularitäten am Konvergenzkreis. Es liegt eine Singularität bei u = 1 vor.

Mit Hilfe der Mellin–Transformation findet man für t → 0:

∑_{k≥1} v_{2}(k)e^{−tk} ∼ ∑_{s} Res (\frac{Γ(s)ζ(s)}{2^{s} − 1}t^{−s})

und insgesamt (z → 1/4)

E(z) ∼ 2ε log_{2} ε + 2 (\frac{3}{2} − log_{2} 2π + \frac{γ}{log 2}) + 4 ∑_{k≠0} ε^{1−χ_{k}} mit χ_{k} = \frac{2kπi}{log 2}

Beachtet man noch, daß

[z^{n}]B(z) ∼ \frac{4^{n}}{\sqrt{π}} n^{−3/2}

ist, folgt nun

M_{n} ∼ log_{4} n − \frac{1}{2} − \frac{γ}{2 log 2} − \frac{1}{log 2} + log_{2} 2π + \frac{1}{log 2} ∑_{k≠0} ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1)^{n^{χ_{k}/2}}.

Es gilt n^{χ_{k}/2} = e^{2kπi·log_{4} n}, und somit M_{n} ∼ log_{4} n + D(log_{4} n). Hier ist D(x) eine periodische Funktion mit Periode 1.

4 ABZÄHLPROBLEME BEI BÄUMEN

Die Fourierreihenentwicklung D(x) = ∑_{k} d_{k} e^{2kπix} ist:

d_{0} = −\frac{1}{2} − \frac{γ}{2 log 2} − \frac{1}{log 2} + log_{2} 2π,
d_{k} = \frac{1}{log 2} ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1), k ≠ 0, χ_{k} = \frac{2kπi}{log 2}.

Man kann auch Motzkinbäume betrachten:

[figure: M; M; M; +; □ +; M =]

M kann aus B durch Substitution gewonnen werden:

[figure: (; ^{)∗}]

[figure: (; ^{)∗}]

Daher:

M(z) = \frac{1}{1 − z} B (\frac{z}{(1 − z)^{2}} ) .

Die Registerfunktion von Bäumen aus M wird durch die folgende Erweiterung gewonnen:

t^{Reg(}  ) = Reg(t)

Es gilt auch

R_{p}^{(M)}(z) = \frac{1}{1 − z} R_{p} (\frac{z}{(1 − z)^{2}} ) usw.

Deshalb ist die mittlere Registerfunktion jetzt gegeben durch

\frac{[z^{n}]\frac{1}{1−z} E(\frac{z}{(1−z)^{2}} )}{[z^{n}]\frac{1}{1−z} B(\frac{z}{(1−z)^{2}} )} .

Ähnlich wie vorher erhält man

∼ log_{4} n + D̄(log_{4} n).

[figure: F = c_{0}·; + c_{1}·; + c_{2}·; F; F; F]

Die Situation kann noch verallgemeinert werden durch Gewichte:

In einem binären Baum bezeichnen wir einen Knoten t als kritisch, falls die Registerfunktion des linken und rechten Unterbaumes gleich sind. Nach längerer Rechnung erhält man: die mittlere Anzahl der kritischen Knoten eines binären Baumes mit n Knoten ist

\frac{[z^{n}]V (z)}{[z^{n}]B(z)} ,

wo

V (z) = \frac{u(1 + u)}{1 − u} − 2 · \frac{1 − u^{2}}{u} ∑_{k≥1} ω(k)u^{k} ; ω(k) = i falls k = 2^{m}(1 + 2i).

Durch ähnliche Methoden wie vorher erhält man:

“ungefähr \frac{n}{3} Knoten sind kritisch”

Man kann auch explizit errechnen, daß

[z^{n}]V (z) = \binom{2n}{n − 1} − 2 ∑_{k≥1} ω(k) [\binom{2n}{n + 1 − k} − 2\binom{2n}{n − k} + \binom{2n}{n − 1 − k}] .

Durch partielle Summation (zweimal durchzuführen) und Information über

∑_{n<N} ∑_{k≤n} ω(k)

kann man das asymptotische Verhalten auch relativ “elementar” (dafür mühsam) errechnen.

Auf eine ungelöste Frage im Zusammenhang mit der Registerfunktion binärer Bäume soll noch eingegangen werden: Die erzeugende Funktion der binären Bäume mit Registerfunktion < p ist

B(z) − S_{p}(z) = \frac{F_{2^{p}−1}(z)}{F_{2^{p}}(z)} ,

mit

F_{n}(z) = ∑_{j} \binom{n − 1 − j}{j}(−z)^{j} (Fibonaccipolynom).

Die linksseitige Höhe h eines binären Baumes ist definiert durch

h(□) = 0

h(  ) = max{1 + h(t_{1}), h(t_{2})} t_{1} t_{2}

Die erzeugende Funktion der Bäume mit h(t) < h ist

\frac{F_{h}(z)}{F_{h+1}(z)}

Somit ist die Anzahl der binären Bäume mit n Knoten und Registerfunktion < p gleich der Anzahl der binären Bäume mit n Knoten und linksseitiger Höhe < 2^{p} − 1. Gesucht ist eine geeignete Bijektion dieser Objekte.

Literatur

(1) N.G.de Bruijn, D.E.Knuth, S.O.Rice: The average height of planted plane trees, in: Graph Theory and Computing (R.C.Read, Ed.), 15-22, Academic Press, 1972.

(2) P.Flajolet: Analyse d’algorithmes de manipulation d’arbres et de fichiers, Thèse Paris-Sud-Orsay, 1979.

(3) P.Flajolet, A.Odlyzko: The average height of binary trees and other simple trees, JCSS 25(1982), 171-213.

(4) P.Flajolet, H.Prodinger: The number of registers to evaluate unary-binary trees, SIAM J. Computing 15(1986), 629-640.

(5) P.Flajolet, J.C.Raoult, J.Vuillemin: The number of registers required for evaluating arithmetical expressions, TCS 9(1979), 99-125.

(6) R.Kemp: The average number of registers to evaluate a binary tree optimally, Acta Inf. 11(1979), 313-372.

(7) H.Prodinger: Some recent results on the register function of a binary tree, Annals of Discrete Math. 33(1987), 241-260.

(8) H.Prodinger, R.F.Tichy: Über ein zahlentheoretisches Problem aus der Informatik, Sitzungsberichte der Österreichischen Akademie der Wissenschaften, Abt. II, 192(1983), 385-396.