NOTE

EXTERNAL INTERNAL NODES IN

DIGITAL SEARCH TREES

VIA MELLIN TRANSFORMS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

January 13, 1992

Knuth [4; ex.6.3.29] posed it as an open problem (ranked M46) to compute (asymptotically) l_{N}, the average number of external internal nodes in a random digital search tree built by N data.

This problem was settled by Flajolet and Sedgewick [2] by a very convenient technique, called Rice’s method. This method has some advantages over the Mellin transform technique that Knuth used heavily in his famous book. (In passing it will be mentioned that the variance was treated by P. Kirschenhofer and the author [3].)

In this note we show that Knuth could have given a solution himself, because in the present approach we follow his ideas that he used in a similar (although easier) problem (cf. [4; p.497]).

For a complete description of the problem and digital search trees we must refer to [4] and [2] in order to keep this note short. For the use of the Mellin transform technique we cite [1].

The problem is to compute

l_{N} = N − ∑_{k=2}^{N} \binom{N}{k}(−1)^{k}R_{k−2}

with

R_{N} = Q_{N} ∑_{k=0}^{N} \frac{1}{Q_{k}}

Typeset by AMS-TEX

and

Q_{k} = (1 − \frac{1}{2}) (1 − \frac{1}{4}) … (1 − \frac{1}{2^{k}} ) for k ≥ 1 and Q_{0} = 1.

It follows from [2] and [3] that

R_{N} = N + 1 − α + R^{∗}(N)

with

α = ∑_{k≥1} \frac{1}{2^{k} − 1} = 1.606695 …

and

R^{∗}(z) = \frac{1}{Q_{∞}} ∑_{j≥1} a_{j} \frac{z + j}{2^{z+j} − 1}.

The quantities in the last equation are

Q_{∞} = lim_{k→∞} Q_{k} = 2.88788 …

and

a_{j} = (−1)^{j−1}2^{−\binom{j}{2}}/Q_{j−1}.

We mention for later use that

R^{∗}(−1) = \frac{1}{Q_{∞}} [\frac{1}{log 2} + ∑_{j≥2} a_{j} \frac{j − 1}{2^{j−1} − 1}] = 2.2346464 …

(a very fast converging series!).

Therefore

l_{N} ∼ N(α + 1) − Σ

with

Σ = \frac{1}{Q_{∞}} ∑_{j≥1} a_{j} ∑_{k=2}^{N} \binom{N}{k}(−1)^{k} \frac{k − 2 + j}{2^{k−2+j} − 1},

and this sum Σ will be attacked in the style of Knuth: Expanding the geometric series we get

Σ = \frac{1}{Q_{∞}} ∑_{j≥1} a_{j} ∑_{m≥1} ∑_{k=2}^{N} \binom{N}{k}(−1)^{k}(k − 2 + j)2^{−m(k−2+j)}

\begin{aligned}= \frac{1}{Q_{∞}} ∑_{j≥1} a_{j} ∑_{m≥1} & [−N2^{−m(j−1)} [(1 − 2^{−m})^{N−1} − 1] \\ & +(j − 2)2^{−m(j−2)} [(1 − 2^{−m})^{N} − 1 + \frac{N}{2^{m}} ]] . \end{aligned}

NOTE EXTERNAL INTERNAL NODES IN DIGITAL SEARCH TREES VIA MELLIN TRANSFORMS3

The last step was by the binomial theorem. Now let

ψ_{1}(x) = e^{−x} − 1  and  ψ_{2}(x) = e^{−x} − 1 + x.

Then the sum Σ may be approximated by

\begin{aligned}Σ & ∼ \frac{1}{Q_{∞}} ∑_{j≥1} a_{j} ∑_{m≥1} [−\frac{N}{2^{m(j−1)}} ψ_{1} (\frac{N}{2^{m}} ) + \frac{j − 2}{2^{m(j−2)}} ψ_{2} (\frac{N}{2^{m}} )] \\ & =: Σ_{1} + Σ_{2}. \end{aligned}

This is achieved by the exponential approximation (1−a)^{N} ≈ e^{−aN}; see e.g. [4; p.131]. Let us start with Σ_{1}:

Σ_{1} = −\frac{N}{Q_{∞}} · f_{1}(N)

with

f_{1}(x) = ∑_{j≥1} a_{j} ∑_{m≥1} 2^{−m(j−1)}ψ_{1} (\frac{x}{2^{m}} ) .

It’s Mellin transform is for −1 < ℜs < 0

\begin{aligned}f_{1}^{∗}(s) & = ∑_{j≥1} a_{j} ∑_{m≥1} 2^{−m(j−1)}2^{ms}Γ(s) \\ & = Γ(s) · ∑_{j≥1} a_{j} \frac{1}{2^{j−1−s} − 1}. \end{aligned}

The Mellin inversion formula

f(x) = \frac{1}{2πi} ∫ f^{∗}(s)x^{−s}ds

(where the integration is along a vertical line inside the so called fundamental strip) allows to go back to the original function. To evaluate it asymptotically, we have to consider the negative residues of the integrand right of the fundamental strip (i.e. here at s = 0). We don’t discuss the other residues which lead to smaller order terms resp. periodic fluctuations of small amplitude, but this can be done as easily as the main term.

The term j = 1 must be treated separately, as it contains a second order pole. The residue computation is standard and gives a contribution

−\frac{N}{Q_{∞}} (− log_{2} N + \frac{1}{2} − \frac{γ}{log 2})

to Σ_{1}. For j ≥ 2 there is only a simple pole, yielding a contribution

−\frac{N}{Q_{∞}} [− ∑_{j≥2} a_{j} \frac{1}{2^{j−1} − 1}] .

Now we turn to Σ_{2}:

Σ_{2} = \frac{1}{Q_{∞}} f_{2}(N)

with

f_{2}(x) = ∑_{j≥1} a_{j}(j − 2) ∑_{m≥1} 2^{−m(j−2)}ψ_{2} (\frac{x}{2^{m}} ) .

We transform f_{2}(x): (for −2 < ℜs < −1)

f_{2}^{∗}(s) = Γ(s) · ∑_{j≥1} a_{j}(j − 2)\frac{1}{2^{j−2−s} − 1}.

The pole of interest is this time s = −1.

Again, j = 1 must be treated separately, yielding a contribution

\frac{N}{Q_{∞}} (− log_{2} N + \frac{1}{2} + \frac{1}{log 2} − \frac{γ}{log 2})

to Σ_{2}. For j ≥ 2 the contribution to Σ_{2} is

\frac{N}{Q_{∞}} ∑_{j≥2} a_{j}(j − 2)\frac{1}{2^{j−1} − 1}.

Hence we have

\begin{aligned}Σ_{1} + Σ_{2} & ∼ \frac{N}{Q_{∞}} (\frac{1}{log 2} + ∑_{j≥2} a_{j}(j − 1)\frac{1}{2^{j−1} − 1}) \\ & = NR^{∗}(−1). \end{aligned}

Therefore we obtain the final result

l_{N} ∼ N(α + 1 − R^{∗}(−1)) = 0.37204 . . . · N,

where, again, the ubiquitous fluctuating term of order N was not mentioned for brevity.

References

1. P.Flajolet, M.Régnier and R.Sedgewick, Combinatorics on Words, Springer NATO ASI Series F, Vol. 12, Berlin, 1985.

2. P.Flajolet and R.Sedgewick, Digital Search Trees Revisited, SIAM J. Computing 15 (1986), 748–767.

3. P.Kirschenhofer and H.Prodinger, Einige Anwendungen der Modulfunktionen in der Informatik, Sitzungsberichte der Österreichischen Akademie der Wissenschaften 197 (1988), 339–366.

4. D.E.Knuth, The Art of Computer Programming, Vol.3, Addison Wesley, Reading, Mass., 1973.

TU Vienna Wiedner Hauptstraße 8-10 A-1040 Vienna Austria