DIGITAL SEARCH TREES AGAIN REVISITED:

THE INTERNAL PATH LENGTH PERSPECTIVE

Peter Kirschenhofer†, Helmut Prodinger†, and Wojciech Szpankowski*

†Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria and *Department of Computer Science, Purdue University West Lafayette,U.S.A.

Abstract. This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree. The problem was open up to now. We prove that for the binary digital search tree the variance is asymptotically equal to 0.26600 . . . · N + Nδ(log_{2} N) where N is the number of stored records and δ(x) is a periodic function of mean zero and a very small amplitude. This result implies that the internal path length becomes asymptotically N · log_{2} N with probability one (i.e. almost surely). In our previous work we have argued that the variance of the internal (external) path length is a good indicator how well the digital trees are balanced. We shall show that the digital search tree is the best balanced digital tree in the sense that a random shape of this tree strongly resembles a shape of a complete tree. Therefore, we conclude that a symmetric digital tree is a good candidate for a dictionary structure, and a typical search time is asymptotically equal to the optimal one for these type of structures. Finally, in order to prove our result we had to solve a number of nontrivial problems concerning analytic continuations and some others of numerical nature. In fact, our results and techniques are motivated by the methodology introduced in an influential paper by Flajolet and Sedgewick.

1. INTRODUCTION

Digital trees [2], [7], [14] experience a new wave of interest due to a number of novel applications in computer science and telecommunications. For example, recent developments in the context of large external files and ideas derived from the dynamic hashing (virtual hashing, dynamic hashing, extendible hashing) lead to the

†This research was supported by Fonds zur Förderung der Wissenschaftlichen Forschung Projekt No. P7497-TEC *This research was primary supported by NSF Cooperative Grant INT-8912631. Additional funding was available from AFOSR grant 90-0107, NSF grant CCR-8900305, and grant R01

LM05118  from  the  National  Library  of  Medicine

Typeset by AMS-TEX

2 PETER KIRSCHENHOFER†, HELMUT PRODINGER†, AND WOJCIECH SZPANKOWSKI*

analysis of digital trees [6], [8], [9], [11], [12], [19], [22], [23], [24]. In telecommunications, recent developments in conflict resolution algorithms [16] have also brought a new interest in digital trees. Some other applications are: radix exchange sort, polynomial factorizations, simulation, Huffman’s algorithm, etc., [2], [7], [14].

The three primary digital tree search methods are: digital search trees (DST), radix search tries (shortly: tries), and Patricia tries [2], [7], [14]. In all cases, a digital tree is built over a V-ary alphabet A = {ω_{1}, …, ω_{V} }. Records stored in a tree, say n of them, consist of (possibly infinite) strings (keys) from A. A digital search tree [2], [4] is a data structure that leads to much improved worst case performance, by making use of the digital properties of the key. The idea is to build a structure consisting of nodes such that each node has a record containing a key and V links which point to subtrees. The branching policy on a level, say k, is based on the k-th digit (element) of a key. For example, if the k-th element of the key is ω_{1}, then we go to the leftmost subtree; if it is ω_{2}, we move to the next of the leftmost subtree, etc. However, if keys are very long, then comparisons of keys at each level of the tree might be quite costly. To avoid this, in the radix search trie we do not store keys in the tree nodes (internal nodes), but rather store all the keys in the external nodes of the tree. However, such a radix trie has an annoying flaw: there is ”one-way branching” which leads to the creation of extra nodes in this tree. D.R.Morrison discovered a way to avoid this problem in a data structure which he named the Patricia trie. In such a tree, all nodes have branching degree greater than or equal to two. This is achieved by collapsing one-way branches on internal nodes, that is, by avoiding unary nodes (cf. [14] and [24]). Note that the number of internal nodes in the digital search tree and the Patricia trie are equal to N and N − V + 1, respectively. This does not hold for radix search tries. It can be proved that the average number of internal nodes is larger than N, namely asymptotically N/H, where H is the entropy of the alphabet.

DIGITAL SEARCH TREES AGAIN REVISITED: THE INTERNAL PATH LENGTH PERSPECTIVE3

In 1979, Fagin et al. [5] proposed extendible hashing as a fast access method for dynamic files. In the original version of this method, radix search trees have been used to access digital keys (records). In addition, another procedure was used to balance the tree in order to achieve good worst case performance. This restructuring generally changes the entire tree and is rather an expensive operation (compare binary search trees and AVL trees). So one may ask whether we need such a rebalancing procedure. To answer this question we must analyze a (random) shape of digital trees, and decide whether this shape resembles the shape of a complete tree [2] (the ultimate balanced tree). This problem led us to investigate the depth of a node (search time) and the (external or internal) path length in digital trees. The average depth of a node for digital trees has been studied in [6], [14], [22], [23], [24], the variance in [9], [22], [23], [24] and limiting distributions in [8], [18], [19]. The average value of the (external or internal) path length is closely related to the average depth of a node, but not the variance. The first attempt to compute the variance was reported in [9], however, it turned out that the variance of the depth was estimated, not the variance of the path length. This was rectified by Kirschenhofer, Prodinger and Szpankowski in [11], [12] who obtained the correct value for the variance in the symmetric regular tries and Patricia tries, respectively (for asymmetric extensions of these results see [8]). In this paper, we propose to evaluate the appropriate variance for the digital search trees, which was an open problem up to now. It has to be stressed that the variance of the internal path length in a digital search tree is the most difficult to estimate. This was already seen in the paper by Flajolet and Sedgewick [6] who establish an analytical methodology to analyze digital search trees (e.g., the average depth of a node). In our paper in the process of establishing the asymptotics of the internal path length we had to obtain some new analytic continuations of functions, which are mainly based on the famous Euler’s product identities. As in [9] and [10], to derive the final results, namely to show the cancellation of the higher order asymptotics, we had to appeal to the theory of modular functions (cf. Section 3). In addition, this problem possesses nontrivial numerical challenge. A very preliminary version of this paper was presented at the IFIP Congress [13].

This paper is organized as follows. In the next section, we define our model, establish the general methodology to attack the problem and present our main results. In particular, we show that the variance of the internal path length for the binary symmetric digital search tree is 0.26600 . . . · N + Nδ(log_{2} N) where N is the number of records and δ(x) is a periodic function with a very small amplitude. This implies that the internal path length converges almost surely to N log_{2} N. Finally, Section 3 contains proofs of our main results.

2. MAIN RESULTS

Let D_{N} be the family of digital search trees built from N records with keys from a random stream of bits. A key consists of 0’s and 1’s with equal probability of appearance. Let L_{N} denote the random variable ”internal path length” of trees in D_{N} and F_{N}(z) the corresponding probability generating functions, i.e., the coefficient [z^{k}]F_{N}(z) of z^{k} in F_{N}(z) is the probability that a tree in D_{N} has internal path length equal to k. Then the following recursion holds which is a direct consequence of the definition:

F_{N+1} = z^{N} ∑_{k=0}^{N} 2^{−N} \binom{N}{k}F_{k}(z)F_{N−k}(z),  F_{0}(z) = 1.  (2.1)

The expectation l_{N} is given by l_{N} = F′_{N}(1) and fulfills for N ≥ 0

l_{N+1} = N + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}l_{k},  l_{0} = 0  (2.2)

This recursion may be solved explicitely by the use of exponential generating functions. With L(z) = ∑_{N≥0} l_{N} \frac{z^{N}}{N!} , (2.2) translates into the following functional differential equation

L′(z) = ze^{z} + 2e^{z/2}L(z/2).

By the substitution L̂(z) = e^{z}L(−z) we have the easier equation

L̂(z) − L̂′(z) = −z + 2L̂(z/2).

With L̂(z) = ∑_{N≥0} l̂_{N} \frac{z^{N}}{N!} we find for N ≥ 2

l̂_{N} = Q_{N−2},  l̂_{0} = l̂_{1} = 0

with the finite product

Q_{N} = (1 − \frac{1}{2}) (1 − \frac{1}{4}) … (1 − \frac{1}{2^{N}} ) ,  (2.3)

so that finally

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

The reader should note that an asymptotic evaluation of (2.4) is non elementary due to the fact that terms of almost equal magnitude occur with alternating signs. For this reason sophisticated methods from complex analysis are needed to find the correct order of growth. An essential step is the application of the following lemma from the calculus of finite differences.

Lemma 1. (cf. [14, p.138], [17]). Let C be a path surrounding the points j, j + 1, …, N and f(z) be analytic inside C and continuous on C. Then

∑_{k≥j} \binom{N}{k}(−1)^{k}f(k) = −\frac{1}{2πi} ∫_{C}[N; z]f(z)dz  (2.5)

with [N; z] = \frac{(−1)^{N−1}N!}{z(z−1)...(z−N)}.

In our application f(z) is a meromorphic function that continues a sequence f(k), e.g., j = 2 and f(k) = Q_{k−2} in (2.4). Moving the contour of integration, one can obtain the asymptotic expansion of the alternating sum by Cauchy’s residue theorem, that is, for any real c (2.5) becomes ∑_{k≥j} \binom{N}{k}(−1)^{k}f(k) = ∑_{z_{i}∈P_{c}} Res([N; z_{i}]f(z_{i}))+ O(N^{c}), where the sum is taken over the set of poles P_{c} different from j, j +1, …, N with real part larger than c.

We note that the function f(k) = Q_{k−2} possesses the analytic continuation Q_{z} = Q_{∞}/Q(2^{−z}) where Q(t) = ∏_{i≥1}(1 − t/2^{i}) [6]. Then, applying a refinement of the technique of Flajolet and Sedgewick, we can easily prove the following theorem (cf. Section 3).

Theorem 2. The expectation l_{N} of the internal path length of digital search trees built from N records fulfills

l_{N} = N log_{2} N + N[\frac{γ − 1}{log 2} + \frac{1}{2} − α + δ_{1}(log_{2} N)] + log_{2} N

+ \frac{2γ − 1}{2 log 2} + \frac{5}{2} − α + δ_{2}(log_{2} N) + O(log N/N)

(2.6) with γ = 0.57721 … (Euler’s constant) and α = ∑_{n≥1} 1/(2^{n} − 1) = 1.60669 …, δ_{1}(x) and δ_{2}(x) are continuous periodic functions of period 1, mean 0 and very small amplitude (< 10^{−6}). For later use we mention the Fourier expansion of δ_{1}(x)

δ_{1}(x) = \frac{1}{log 2} ∑_{k≠0} Γ (−1 − \frac{2kπi}{log 2}) e^{2kπix}.  (2.7)

where Γ(x) is the gamma function [1].

We mention in passing that the O(1)-term in (2.6) is slightly incorrect in [14].

Now we turn to the analysis of the variance which is given by VarL_{N} = s_{N} + l_{N} − l_{N}^{2} with s_{N} = F′′_{N}(1). From (2.1) we get the recurrence relation (for N ≥ 0; s_{0} = 0)

\begin{aligned}s_{N+1} & = N2^{2−N} ∑_{k=0}^{N} \binom{N}{k}l_{k} + N(N − 1) \\ & + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}l_{k}l_{N−k} + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}s_{k}. \end{aligned}  (2.8)

In order to find an explicit solution to this recurrence, we split it into 3 parts: s_{N} = u_{N} + v_{N} + w_{N}, where

u_{N+1} = 2N(l_{N+1} − N) + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}u_{k}, N ≥ 0, u_{0} = 0,  (2.9a)

v_{N+1} = N(N − 1) + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}v_{k}, N ≥ 0, v_{0} = 0,  (2.9b)

w_{N+1} = 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}l_{k}l_{N−k} + 2^{1−N} ∑_{k=0}^{N} \binom{N}{k}w_{k}, N ≥ 0, w_{0} = 0. (2.9c)

All of the above recurrences, as well as the one for the average internal path length (2.2), fall into the following general recurrence studied in [23]. Let (x_{n}) be a sequence of numbers satisfying the following

x_{n+1} = a_{n+1} + 2^{1−n} ∑_{k=0}^{n} \binom{n}{k}x_{k},  n ≥ 2,  (2.10)

where (a_{n}) is any sequence of numbers. The solution of (2.10) depends on the so called binomial inverse relations that are defined as follows

â_{n} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}a_{k} and a_{n} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}â_{k}.

The second equation justifies the name binomial inverse relations. For more details, see Riordan [20]. A similar treatment as in the case of (2.2) leads to the following explicit solution (for details see [23]).

Lemma 3. Let x_{0} = x_{1} = 0. Then the recurrence (2.10) possesses the following solution

x_{n} = x_{0} + n(x_{1} − x_{0}) − ∑_{k=2}^{n}(−1)^{k}\binom{n}{k}x̂_{k−2}  (2.11a)

where

x̂_{n} = Q_{n} ∑_{i=1}^{n+1}[â_{i} − â_{i+1} − a_{1}]/Q_{i−1}  (2.11b)

and Q_{n} is defined in (2.3).

Using Lemma 3 we immediately solve our recurrences (2.9a) to (2.9c). In particular, one proves

û_{k} = 2Q_{k−2} \{4 + ∑_{j=1}^{k−2} \frac{1}{2^{j} − 1} − ∑_{j=1}^{k−2} \frac{j}{2^{j} − 1} − \frac{2k}{2^{k−2} − 1}\} ,

for k ≥ 3,  û_{0} = û_{1} = û_{2} = 0  (2.12a)

v̂_{k} = −4Q_{k−2},  for k ≥ 3,  v̂_{0} = v̂_{1} = v̂_{2} = 0  (2.12b)

and

ŵ_{k} = Q_{k−2} ∑_{j=4}^{k−1} \frac{2^{1−j}}{Q_{j−1}} ∑_{i=2}^{j−2} \binom{j}{i}Q_{j−2}Q_{j−i−2},

for k ≥ 5,  ŵ_{0} = ⋯ = ŵ_{4} = 0  (2.12c)

Of course, the ”unhatted” solutions u_{N}, v_{N} and w_{N} follow from the binomial relations, as shown in (2.11a). It is also worth to mention that the recurrence for v_{N} is easy, and after simple algebra one proves

v_{N} = 4\binom{N}{2} − 4l_{N},  (2.12d)

so that the treatment of u_{N} and w_{N} remains to be done.

In principle u_{N} and w_{N} may be analyzed by making use of Lemma 1 and 3. However, it turns out to be a highly non trivial problem to find an analytical continuation of ŵ_{k}. After lengthy and difficult computations the residue calculus leads us to the following main result of this paper, which is proved in the next section.

Theorem 4. The variance of the internal path length of digital search trees built from N records becomes

Var L_{N} = N · {C + δ(log_{2} N)} + O(log^{2} N/N)

where C is a constant that can be expressed as

\begin{aligned}C & = −\frac{28}{3L} − \frac{39}{4} − 2β_{1} + \frac{2α}{L} + \frac{π^{2}}{2L^{2}} + \frac{2}{L^{2}} \\ & − \frac{2}{L} ∑_{k≥3} \frac{(−1)^{k+1}(k − 5)}{(k + 1)k(k − 1)(2^{k} − 1)} \\ & + \frac{2}{L} ∑_{r≥1} b_{r+1} (\frac{L(1 − 2^{−r+1})/2 − 1}{1 − 2^{−r}} − ∑_{k≥2} \frac{(−1)^{k+1}}{k(k − 1)(2^{r+k} − 1)}) \\ & + \frac{2}{L}ŵ′(3) − 2[δ_{1}δ_{2}]_{0} − [δ_{1}^{2}]_{0} \end{aligned}  (2.13)

with L = log 2, α = ∑_{n≥1} \frac{1}{2^{n}−1}, β_{1} = ∑_{j≥1} \frac{j2^{j}}{(2^{j}−1)^{2}} , b_{r+1} = (−1)^{r}2^{−\binom{r+1}{2}}. The fluctu-

ating function δ(x) is continuous with period 1, mean zero and |δ(x)| ≤ 10^{−6}, and |[δ_{1}^{2}]_{0}| ≤ 10^{−10}, |[δ_{1}δ_{2}]_{0}| ≤ 10^{−10}. Finally, ŵ(z) is a function defined as

\begin{aligned}ŵ(z + 1)/Q_{z−1} & = −2Q_{∞}z + \frac{ξ(z + 2)}{2^{z}Q_{z}} + \frac{ξ(z + 3)}{2^{z+1}Q_{z+1}} \\ & + ∑_{j≥2} (\frac{ξ(z + j + 2)}{2^{z+j}Q_{z+j}} − \frac{ξ(j + 2)}{2^{j}Q_{j}}) \end{aligned}  (2.14)

with Q_{z} = Q_{∞}/Q(2^{−z}), where Q(t) = ∏_{i≥1}(1 − t/2^{i}), Q_{∞} = Q(1), and

\begin{aligned}ξ(z + 1) = ∑_{r≥0} \frac{b_{r+1}}{Q_{r}} & · \frac{Q_{∞}}{Q(2^{3−z−r})} · \{2^{z} − \frac{2}{1 − 2^{1−z−r}} − \frac{2z}{1 − 2^{2−z−r}} \\ & + 2 ∑_{k≥2} \binom{z}{k}\frac{1}{2^{r+k−1} − 1}\}. \end{aligned}  (2.15)

Numerical evaluation of the constant C reveals that C = 0.26600 … and all five digits after the decimal point are significant. We should point out that in order to achieve the same accuracy in C one needs to run the recurrence equations (2.9a)– (2.9c) for N ∼ 10^{6}.

In the following lemma we present an explicit formula for ŵ′(3) that is convenient for numerical evaluations.

Lemma 5. The following identity holds

\begin{aligned}\frac{2ŵ′(3)}{L} & = −\frac{2Q_{∞}}{L} + ∑_{j≥2} \frac{1}{2^{j}Q_{j}} ∑_{r≥0} a_{r+1}Q_{r+j−2}· \\ & · \{− ∑_{n≥1} \frac{1}{2^{n+r+j+2} − 1} · (2^{j+1} − 2j − 4 \\ & + 2 ∑_{k=2}^{j−1} \binom{j + 1}{k}\frac{1}{2^{r+k−1} − 1}) \\ + & \frac{2}{(1 − 2^{−j−r})^{2}} + \frac{2j + 2}{(1 − 2^{1−j−r})^{2}} − \frac{2}{L} \frac{1}{1 − 2^{1−j−r}} \\ & − 2 ∑_{k=2}^{j+1} \binom{j + 1}{k}\frac{1}{2^{r+k−1} − 1} + \frac{2}{L} ∑_{k=1}^{j+1} \binom{j + 1}{k}\frac{1}{2^{r+k} − 1} \\ & + \frac{2}{L} ∑_{k=0}^{j+1} \binom{j + 1}{k} ∑_{i≥1} \frac{(−1)^{i}}{(i + 1)(2^{r+k+i} − 1)}\} \\ & + ∑_{j≥3} \frac{ξ(j + 2)}{2^{j}Q_{j}} ∑_{k≥j+1} \frac{1}{2^{k} − 1} \end{aligned}  (2.16)

where

a_{r+1} = \frac{b_{r+1}}{Q_{r}} = (−1)^{r}2^{−\binom{r+1}{2}}/Q_{r},  (2.17)

and

ξ(j + 2) = ∑_{k=2}^{j−1} \binom{j + 1}{k}Q_{k−2}Q_{j−k−1}  (2.18)

with Q_{k} defined in Theorem 4.

Before we proceed to the proof of our results, we first offer some remarks and extensions.

Remark 2.19. The covariance analysis. Theorem 4 and our previous result [9] and [23] provide asymptotics for the covariance between two different nodes in a digital search tree (DST). Let D_{N} be a depth of a (randomly selected) node and let D_{N}^{(i)} be the length of a path from the root to the i-th node. Note that the internal path length L_{N} is defined in terms of D_{N}^{(i)} as L_{N} = ∑_{i=1}^{N} D_{N}^{(i)}. Then

Var L_{N} = E {[∑_{i=1}^{N} D_{N}^{(i)}]^{2}} − {E ∑_{i=1}^{N} D_{N}^{(i)}}^{2}

and this implies

Var L_{N} = NVar D_{N} + 2 ∑_{i≠j} Cov {D_{N}^{(i)}, D_{N}^{(j)}} .

The variance of the depth Var D_{N} for the symmetric DST was analyzed in [9], and for the asymmetric one in [23]. In particular, it was proved that for the binary symmetric Patricia Var D_{N} = 2.844 · · ·. Using Theorem 4 and the above we find

2 ∑_{i≠j} Cov {D_{N}^{(i)}, D_{N}^{(j)}} = −2.67 . . . · N.

This also implies that the average value of

Cov{D_{N}^{(i)}, D_{N}^{(j)}} is ∼ −2.67 … /N.

Note that the equivalent quantity for regular tries is approximately equal to +0.84 … /N

[11] and for Patricia = −.63 ⋯ /N [12].

Remark 2.20 The path length L_{N} converges almost surely to E_{N}! Applying Theorem 4 it is not difficult to prove that L_{N}/EL_{N} tends to one almost surely (i.e., with probability one) as N → ∞. Indeed, by Chebyshev’s inequality one obtains

Pr \{|L_{N}/EL_{N} − 1| ≥ ϵ\} ≤ \frac{Var L_{N}}{ϵ^{2}(EL_{N})^{2}} .

But, by Theorem 4

Pr \{|L_{N}/EL_{N} − 1| ≥ ϵ\} ≤ \frac{A}{ϵ^{2}N log_{2}^{2} N} → 0.

This shows that L_{N}/EL_{N} → 1 in probability as N → ∞ [21]. To prove a stronger result, namely, that L_{N}/EL_{N} → 1 with probability one (i.e., almost surely) we apply the above and the Borel-Cantelli lemma [21], and then show

∑_{N=1}^{∞} Pr \{|L_{N}/EL_{N} − 1| ≥ ϵ\} ≤ \frac{0.266 ⋯}{ϵ^{2}} ∑_{N=1}^{∞} \frac{1}{N log_{2}^{2} N} < ∞,

so, by the Borel-Cantelli lemma L_{N} ∼ EL_{N} ∼ N log_{2} N with probability one.

Remark 2.21. Comparison of digital trees. In order to select the best digital tree one needs to compare different characteristics of digital trees, namely regular tries, Patricia tries and Digital Search Trees (DST). The table below contains four important parameters that are often used to predict a random shape of these trees (cf. [6], [9], [11], [12], [14], [15], [22], [23], [24]).

EL_{N}  Var L_{N} Var D_{N} Cov(D_{N}^{i}, D_{N}^{j})
DST  N(log_{2} N − 1.71) N · 0.26 2.844 − 2.67/N
TRIES  N(log_{2} N + 1.33) N · 4.35 3.507 + 0.84/N
PATRICIA N(log_{2} N + 0.33) N · 0.37 1.000 − 0.63/N

It can be seen from the table that the average external (internal) path length is approximately the same for all three digital trees. However, the variance of the depths and internal (external) path lengths differ significantly. We also notice that the variance of the internal for DST is smaller than the variance of the external path length for Patricia, but the reverse holds true for the variance of the depth. Therefore, in order to answer the question which digital tree is the best (balanced) one needs to decide which parameter (depth or path length) carry more useful information. This is discussed below.

Remark 2.22. Which digital tree is balanced the best? A complete binary tree [2] is the ultimately best balanced tree. Therefore, any tree with a good balance property should have the average depth (external path length) equal to log_{2} N + O(1) (resp. N log_{2} N + O(N)), and a small variance. Such a property is highly desired since then one can expect that a typical search time for a key is approximately equal to the average depth. This was already said in Remark 2.17, nevertheless we might be interested in a relative comparison between different trees that satisfy the above vague criterion. One may ask which digital tree is balanced the best. To solve this problem we must determine which parameter from the table above is the most suited for such an analysis. We first notice that the covariance Cov {D_{N}^{(i)}, D_{N}^{(j)}} for Patricia and digital search tree is negatively correlated. This

means, that D_{N}^{(i)} < ED_{N} and D_{N}^{(i)} > ED_{N} also tend to occur together. Thus, for negatively correlated random variables D_{N}^{(i)} and D_{N}^{(j)}, if one is large, the other is likely to be small. This indicates a good balance property for a tree. Note, that in the regular tries Cov {D_{N}^{(i)}, D_{N}^{(j)}} ∼ 0.84/N > 0 and D_{N}^{(i)} and D_{N}^{(j)} in that case are

positively correlated. This means that D_{N}^{(i)} is large, then D_{N}^{(j)} is likely to be large, too.

So finally the problem under consideration boils down to a choice between the variance of the depth or the variance of the internal (external) path length. In [12] we have argued that for tries (regular or Patricia) the external path length is a better measure of the balance property for a tree. This argument can be made even more convincing for digital search trees. Consider a DST that is completely balanced. Then, since keys are stored in internal nodes the variance of the depth is positive no matter how balanced the tree is. But, the variance of the internal path length is zero for such an instance. This leads to an obvious conclusion that the variance of the path length should be considered as a criterion for the balance property. Then, one finds out from the table above that digital search trees are the best balanced digital trees.

3. ANALYSIS

As we have already pointed out in Section 2, it is a nontrivial problem to find appropriate analytic continuations for the sequences of values f(k) that occur in alternating sums (2.5). In order to illustrate our approach, we start with the easiest case, namely the evaluation of the expectation l_{N}. From (2.4) we know

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

As in [6] we may rewrite f(k) = Q_{k−2} as

Q_{k−2} = \frac{Q_{∞}}{Q(2^{2−k})},

where

Q(x) = ∏_{i≥1} (1 − \frac{x}{2^{i}} )  and  Q_{∞} = Q(1).  (3.1)

Therefore we have the analytic continuation

f(z) = \frac{Q_{∞}}{Q(2^{2−z})}.  (3.2)

The main contribution to l_{N} is given by Res([N; z]f(z); z = 1). We have with u = z − 1 → 0

[N; z] ∼ \frac{N}{u} (1 + u(H_{N−1} − 1))

and

\frac{Q_{∞}}{Q(2^{2−z})} ∼ \frac{1}{Lu} (1 + Lu(\frac{1}{2} − α))

(remember L = log 2), since

α = (\frac{Q_{∞}}{Q(x)})′|_{x=1} .  (3.3)

Therefore

Res([N; z]f(z); z = 1) = \frac{N}{L} (H_{N−1} − 1 + L(\frac{1}{2} − α)).

Using the well known asymptotics for the harmonic numbers H_{N−1} we get the contribution (from z = 1)

N log_{2} N + N (\frac{γ}{L} − \frac{1}{L} + \frac{1}{2} − α) − \frac{1}{2L} + O (\frac{1}{N} ) .  (3.4)

Besides z = 1 we have with the same real part 1 the simple poles z_{k} = 1 + \frac{2kπi}{L}, k ∈ Z, k ≠ 0 with

Res([N; z]f(z); z = z_{k}) = [N; z_{k}] · \frac{1}{L},

so that we get the contribution

\frac{N^{z_{k}}}{L} Γ(−z_{k}) − \frac{(z_{k} − 1)z_{k}N^{z_{k}−1}Γ(−z_{k})}{2L} + O(N^{z_{k}−2}).  (3.5)

The reader should take notice of the fact that the first term in (3.5) gives the Fourier coefficients of δ_{1}(x) in Theorem 1.

The next relevant pole is z = 0 and yields a contribution of

log_{2} N + \frac{γ}{L} + \frac{5}{2} − α.  (3.6)

The poles z = z_{k} − 1 yield a periodic contribution of order N^{0} and so on.

Collecting all contributions gives the expansion (2.6) in Theorem 2.

Next we focus our attention on the asymptotics of u_{N}. In order to find an appropriate analytic continuation of û_{k} we rewrite the sums appearing in (2.12a) as follows:

∑_{j=1}^{k−2} \frac{1}{2^{j} − 1} = α − ∑_{j≥1} \frac{1}{2^{k−2+j} − 1},

∑_{j=1}^{k−2} \frac{j}{2^{j} − 1} = ∑_{j≥1} \frac{j}{2^{j} − 1} − ∑_{j≥1} \frac{k − 2 + j}{2^{k−2+j} − 1}.

Thus we may continue û_{k} via the function

\begin{aligned}û(z) & = \frac{2Q_{∞}}{Q(2^{2−z})}[4 + α − ∑_{j≥1} \frac{1}{2^{z−2+j} − 1} \\ & − ∑_{j≥1} \frac{j}{2^{j} − 1} + ∑_{j≥1} \frac{z − 2 + j}{2^{z−2+j} − 1} − \frac{2z}{2^{z−2} − 1}]. \end{aligned}  (3.7)

Now the main contribution to u_{N} in Lemma 1 originates from a second order pole of [N; z]û(z) in z = 2. Further contributions that are necessary for the evaluation of the variance come from first order poles in z = 2 + \frac{2kπi}{L}, k ≠ 0, a third order pole in z = 1 as well as second order poles in z = 1 + \frac{2kπi}{L}, k ≠ 0. Collecting all the above mentioned contributions we end up with the following expansion of u_{N} (δ_{i}(x) stands in all following formulas for a continuous periodic function of period 1 and mean zero).

Lemma 6.

u_{N} ∼ 4N^{2} log_{2} N

+ N^{2} (\frac{4(γ − 1)}{L} − 6 − 4α + δ_{3}(log_{2} N))

− N log_{2}^{2} N + 2N log_{2} N · (\frac{2 − γ}{L} + 8 + α + δ_{4}(log_{2} N))

+ N(−\frac{γ^{2}}{L^{2}} + \frac{4γ}{L^{2}} + \frac{12γ}{L} + \frac{2αγ}{L} − \frac{π^{2}}{6L^{2}} − \frac{4}{L^{2}} − \frac{10}{L} − \frac{2α}{L}

− α^{2} + β − 11α − 2β_{1} + \frac{133}{6} + δ_{5}(log_{2} N)) + O(log^{2} N)

DIGITAL SEARCH TREES AGAIN REVISITED: THE INTERNAL PATH LENGTH PERSPECTIVE 13

with β = ∑_{k≥1} \frac{1}{(2^{k}−1)^{2}} , L, α, β_{1} as in Theorem 4.

As already mentioned in Section 2,

v_{N} = 4\binom{N}{2} − 4l_{N},

so that the asymptotics of v_{N} are given by

v_{N} ∼ 2N^{2} − 4N log_{2} N

+ 4N (−1 + α − \frac{γ}{L} + \frac{1}{L} − δ_{1}(log_{2} N)) + O(log N). (3.8)

The most challenging task is to find an appropriate analytic continuation of ŵ(z). From (2.12c) we have

ŵ_{k+1} = −Q_{k−1} ∑_{j=4}^{k} \frac{ξ(j + 1)}{2^{j−1}Q_{j−1}}  (3.9)

with

ξ(j + 1) = ∑_{i=2}^{j−2} \binom{j}{i}Q_{i−2}Q_{j−2−i}.  (3.10)

For the following the reader should note that ξ(j + 1) ∼ Q_{∞}^{2}2^{j}. We start by rewriting (3.9) in the following manner:

With η(j + 1) = ξ(j + 1) − Q_{∞}^{2}2^{j} we have

\begin{aligned}−\frac{ŵ_{k+1}}{Q_{k−1}} & = ∑_{j=4}^{k} \frac{η(j + 1) + Q_{∞}^{2}2^{j}}{2^{j−1}Q_{j−1}} \\ & = ∑_{j≥4} \frac{η(j + 1)}{2^{j−1}Q_{j−1}} − ∑_{j≥k+1} \frac{η(j + 1)}{2^{j−1}Q_{j−1}} \\ & + 2Q_{∞}^{2} (∑_{j≥4} (\frac{1}{Q_{j−1}} − \frac{1}{Q_{∞}} ) − ∑_{j≥k+1} (\frac{1}{Q_{j−1}} − \frac{1}{Q_{∞}} )) \\ & + 2Q_{∞}(k − 3). \end{aligned}  (3.11)

Therefore

\begin{aligned}ŵ_{k+1} = Q_{k−1}[ & − 2Q_{∞}(k − 3) + ∑_{j≥0} \frac{η(j + k + 2)}{2^{j+k}Q_{j+k}} − ∑_{j≥3} \frac{η(j + 2)}{2^{j}Q_{j}} \\ & + 2Q_{∞}^{2}(∑_{j≥0} (\frac{1}{Q_{j+k}} − \frac{1}{Q_{∞}} ) − ∑_{j≥3} (\frac{1}{Q_{j}} − \frac{1}{Q_{∞}} ))]. \end{aligned}

Since all involved series are now absolutely convergent, we may add them term by term and get

\begin{aligned}ŵ_{k+1} = Q_{k−1}[ & − 2Q_{∞}k + \frac{ξ(k + 2)}{2^{k}Q_{k}} + \frac{ξ(k + 3)}{2^{k+1}Q_{k+1}} \\ & + ∑_{j≥2} (\frac{ξ(k + j + 2)}{2^{k+j}Q_{k+j}} − \frac{ξ(j + 2)}{2^{j}Q_{j}})]. \end{aligned}

From this, the representation for ŵ(z + 1) as in (2.14) is immediate, provided we have an appropriate interpretation for ξ(z + 1). This will be our next goal. The following well-known partition identities of Euler are our basic tool:

\frac{1}{Q(t)} = ∏_{n≥1} \frac{1}{(1 − t2^{−n})} = ∑_{n≥0} \frac{t^{n}}{2^{n}Q_{n}}  (3.12)

and

Q(t) = ∏_{n≥1} (1 − \frac{t}{2^{n}} ) = ∑_{n≥0} a_{n+1}t^{n}  (3.13)

with

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

Using (3.2) and (3.12) we have

\begin{aligned}ξ(N + 1) & = ∑_{k=2}^{N} \binom{N}{k}\frac{Q_{∞}}{Q(2^{2−k})} \frac{Q_{∞}}{Q(2^{2+k−N})} \\ & = Q_{∞}^{2} ∑_{i,j≥0} \frac{2^{i+j}}{Q_{i}Q_{j}} ∑_{k=2}^{N−2} \binom{N}{k}(2^{−i})^{k}(2^{−j})^{N−k}, \end{aligned}

where the innermost sum is now

(2^{−i} + 2^{−j})^{N} − 2^{−iN} − 2^{−jN} − N2^{−i(N−1)−j} − N2^{−i−j(N−1)}.

The last expression for ξ(N +1) is symmetric in i and j. However, it turns out that for the purpose of finding an analytic continuation ∑_{i,j≥0} should be rewritten as − ∑_{j=i} +2 ∑_{j≥i≥0}. Writing j = i + h in the second sum we get

\begin{aligned}ξ(N + 1) & = −(2^{N} − 2 − 2N) ∑_{i≥0} \frac{Q_{∞}^{2}}{Q_{i}^{2}} 2^{i(2−N)} \\ & + 2 ∑_{i,h≥0} \frac{Q_{∞}^{2}}{Q_{i}Q_{i+h}} 2^{i(2−N)}2^{h}[(1 + 2^{−h})^{N} − 1 − N2^{−h}] \\ & − 2 ∑_{i,h≥0} \frac{Q_{∞}^{2}}{Q_{i}Q_{i+h}} 2^{i(2−N)}2^{h(1−N)} \\ & − 2N ∑_{i,h≥0} \frac{Q_{∞}^{2}}{Q_{i}Q_{i+h}} 2^{i(2−N)}2^{h(2−N)} \end{aligned}  (3.14)

In expression (3.14) N can be replaced by z, yielding a meromorphic function, since all series converge uniformly. However, we are able to simplify ξ(z + 1) in the following way. Consider for example the last term in (3.14):

2z ∑_{i,h≥0} \frac{Q_{∞}^{2}}{Q_{i}Q_{i+h}} 2^{(i+h)(2−z)} = 2z ∑_{i,h≥0} \frac{Q_{∞}Q(2^{−i−h})}{Q_{i}}2^{(i+h)(2−z)}

which is by Euler’s identity (3.13)

= 2z ∑_{r≥0} a_{r+1} ∑_{i≥0} \frac{Q_{∞}}{Q_{i}} (2^{−r+2−z})^{i} ∑_{h≥0}(2^{−r+2−z})^{h}

and by Euler’s identity (3.12)

= 2z ∑_{r≥0} a_{r+1} \frac{Q_{∞}}{Q(2^{3−z−r})} · \frac{1}{1 − 2^{2−z−r}} .

Rewriting the other terms from (3.14) in a similar way, especially using

(1 + 2^{−h})^{z} − 1 − z2^{−h} = ∑_{k≥2} \binom{z}{k}2^{−hk}

for the second term, we finally get (2.15).

Our next task is to investigate the poles of [N; z]ŵ(z) different from z = 5, 6, …, N.

From (3.11) we see that ŵ(4) = ŵ(3) = 0 (observe that ξ(4) = 0), so that the first poles occur with real part 2. In order to determine the residues of [N; z]ŵ(z) in z = 2 resp. z = 1 we need the local behaviour of ŵ(z). Because of (2.14) this behaviour will depend on the behaviour of σ(z) := ξ(z)/2^{z−2}Q_{z−2} near z = 2, 3, … . From (2.15) we see that ξ(z) has second order poles for z = 2 and z = 3 and is analytic for z = 4, 5, · · ·. Since [N; z]Q_{z−2} has already a second order pole for z = 1, it will be necessary to expand σ(z) near z = 2, 3, … up to the linear terms. In particular, the reader should note that all the derivatives σ′(z) for z = 4, 5, … will occur in Res([N; z]ŵ(z); z = 1). This is the main reason that the constant C in the final result is rather a complicated one.

We start with the expansion of σ(z) about z = 3. Let u = z − 3; then we find

16 PETER KIRSCHENHOFER†, HELMUT PRODINGER†, AND WOJCIECH SZPANKOWSKI*

from (2.15) after laborious computations:

\begin{aligned}σ & (3 + u) ∼ −\frac{4}{L^{2}u^{2}} + \frac{1}{u} (\frac{6}{L} − \frac{2}{L^{2}} ) \\ & + u^{0} (\frac{16}{3} + \frac{5}{L} + \frac{2β_{2}}{L} + 2 ∑_{r≥2} \frac{b_{r+1}}{1 − 2^{−r}} (1 − \frac{2}{1 − 2^{−r}} )) \\ & + u^{1}(−\frac{223}{18}L − \frac{23}{6} − 3C_{1} + \frac{C_{2}}{L} − 2C_{3} \\ & + 2 ∑_{r≥2} \frac{b_{r+1}}{1 − 2^{−r}} \{1 − 3L + L ∑_{i=2}^{r−1} \frac{1}{2^{i} − 1} + \frac{2^{−1−r}L}{(1 − 2^{−1−r})^{2}} \\ & + \frac{2L − 1}{1 − 2^{−r}} − \frac{2L}{1 − 2^{−r}} ∑_{i=2}^{r−1} \frac{1}{2^{i} − 1} + \frac{2^{1−r}L}{(1 − 2^{−r})^{2}} + D_{r,1}\}) \end{aligned}  (3.15)

where

β_{2} = 2 ∑_{k≥2} \frac{(−1)^{k}}{(k + 1)k(k − 1)(2^{k} − 1)},

C_{1} = ∑_{h≥0} 2^{h}[(1 + 2^{−h})^{2} log(1 + 2^{−h}) − 2^{−h}],

C_{2} = ∑_{h≥0} 2^{h}(1 + 2^{−h})^{2} log^{2}(1 + 2^{−h}),

C_{3} = ∑_{h≥0}[(1 + 2^{−h})^{2} log(1 + 2^{−h}) − 2^{−h}],

D_{r,1} = ∑_{h≥0} 2^{h(1−r)}[(1 + 2^{−h})^{2} log(1 + 2^{−h}) − 2^{−h}].

The constant in the u^{0}-term can be simplified according to the remarkable identity

∑_{r≥1} \frac{b_{r+1}}{1 − 2^{−r}} (1 − \frac{2}{1 − 2^{−r}} ) = ∑_{j≥1} \frac{2^{j}}{(2^{j} − 1)^{2}} = α + β.  (3.16)

For the proof of (3.16) we observe that the left-hand side equals

∑_{r≥1} a_{r+1}Q_{r−1} − 2 ∑_{r≥1} a_{r+1} \frac{Q_{r−1}}{1 − 2^{−r}} .

Using (3.12) and (3.13) this expression becomes

∑_{i≥0} Q(2^{−i}) (Q(2^{−i}) − 1) − 2 ∑_{i,k≥0} Q(2^{−i}) (Q(2^{−i−k}) − 1)

= −(∑_{i≥0} (Q(2^{−i}) − 1))^{2} − ∑_{j≥0}(2j + 1) (Q(2^{−j}) − 1)

= −E_{1}^{2} − 2E_{2} − E_{1},

where E_{1} = ∑_{r≥1} \frac{a_{r+1}}{1 − 2^{−r}} and E_{2} = ∑_{r≥1} a_{r+1} \frac{2^{−r}}{(1 − 2^{−r})^{2}} .

Now we observe

E_{1} = lim_{t→2} [\frac{Q_{∞}}{Q(t)} − \frac{1}{1 − t/2}] = − (\frac{Q_{∞}}{Q(t)})′|_{t=1} = −α

and

\begin{aligned}E_{2} & = 2 lim_{t→2} [(\frac{Q_{∞}}{Q(t)})′ − \frac{1/2}{(1 − t/2)^{2}} ] \\ & = −\frac{1}{2} (\frac{Q_{∞}}{Q(t)})′′ |_{t=1} = −\frac{α^{2} + β}{2} \end{aligned}

and get the right-hand side of (3.16).

The expansion of σ(z) about z = 2 reads with u = z − 2:

\begin{aligned}σ & (2 + u) ∼ \frac{4}{L^{2}u^{2}} + \frac{1}{u} (\frac{2}{L} + \frac{2}{L^{2}} ) \\ & + u^{0} (−\frac{16}{3} − \frac{6}{L} − \frac{2}{L}(C_{4} + C_{6}) + 2E_{3}) \\ & + u^{1}(\frac{L}{6} − \frac{55}{6} − 3C_{4} − \frac{C_{5}}{L} + C_{6} − \frac{C_{7}}{L} \\ & + 2 ∑_{r≥2} \frac{b_{r+1}}{(1 − 2^{1−r})(1 − 2^{−r})}\{D_{r,2} + 1 − 2L \\ & + L ∑_{i=1}^{r−2} \frac{1}{2^{i} − 1} + \frac{L − 1}{1 − 2^{1−r}} \\ & + L(\frac{1}{(1 − 2^{−r})^{2}} − \frac{1}{1 − 2^{−r}} ∑_{i=1}^{r−2} \frac{1}{2^{i} − 1} \\ & + \frac{2^{1−r}}{(1 − 2^{1−r})^{2}} − \frac{1}{1 − 2^{1−r}} ∑_{i=1}^{r−2} \frac{1}{2^{i} − 1})\}) \end{aligned}  (3.17)

where

C_{4} = ∑_{h≥0} 2^{h} [(1 + 2^{−h}) log(1 + 2^{−h}) − 2^{−h}] ,

C_{5} = ∑_{h≥0} 2^{h}(1 + 2^{−h}) log^{2}(1 + 2^{−h}),

C_{6} = ∑_{h≥0} [(1 + 2^{−h}) log(1 + 2^{−h}) − 2^{−h}] ,

C_{7} = ∑_{h≥0}(1 + 2^{−h}) log^{2}(1 + 2^{−h}),

D_{r,2} = ∑_{h≥0} 2^{h(1−r)} [(1 + 2^{−h}) log(1 + 2^{−h}) − 2^{−h}] ,

E_{3} = ∑_{r≥2} \frac{b_{r+1}}{(1 − 2^{1−r})(1 − 2^{−r})} (1 − \frac{1}{1 − 2^{−r}} − \frac{1}{1 − 2^{1−r}} ) .

For later simplifications we note that

−\frac{2}{L} (C_{4} + C_{6}) = −8 + \frac{3}{L} − \frac{2β_{2}}{L}  (3.18)

and

E_{3} = 2 − α − β,  (3.19)

where (3.18) follows from the expansion of the logarithm and (3.19) by partial fraction decomposition and rearrangements of the sums.

We finally note that

C_{5} + C_{7} = C_{2}.  (3.20)

Next we discuss σ(z) for z close to j = 4, 5, · · ·.

\begin{aligned}σ(j + u) & ∼ σ(j) \\ & + \frac{u}{2^{j−2}Q_{j−2}} (ξ′(j) − Lξ(j) + Lξ(j) ∑_{k≥1} \frac{1}{2^{k+j−2} − 1}) . \end{aligned}  (3.21)

From (3.21)

\begin{matrix}∑_{j≥4} & (σ(j + u) − σ(j)) \\ ∼ u(∑_{j≥4} \frac{ξ′(j) − Lξ(j)}{2^{j−2}Q_{j−2}} \\ L ∑_{j≥4} \frac{ξ(j)}{2^{j−2}Q_{j−2}} ∑_{k≥1} \frac{1}{2^{k+j−2} − 1}). \end{matrix}  (3.22a)

From (2.14) we find that the last expression equals

u(2ŵ′(3) + 2Q_{∞})  (3.22b)

where ŵ′(3) may be computed from (2.15) to get the constant from Lemma 5.

Regarding (3.15), (3.17) and (3.22a) we find that [N; z]ŵ(z) has third order poles in z = 2 and z = 1, and second order poles in z_{k} = 2 + \frac{2kπi}{L}, k ∈ Z, z ≠ 0, as well as in z_{k} − 1.

Our local expansions allow (after some lengthy but straightforward computations) to find the following asymptotic behaviour of w_{N}:

Lemma 7.

w_{N} = N^{2} log_{2}^{2} N + N^{2} log_{2} N · (−3 − \frac{2}{L} + \frac{2γ}{L} − 2α + δ_{6}(log_{2} N))

+ N^{2}(\frac{1}{3} + α^{2} + 3α + \frac{2α}{L} − \frac{3γ}{L} − \frac{2αγ}{L} − \frac{β_{2}}{L}

+ \frac{2}{L} + \frac{2}{L^{2}} + \frac{γ^{2}}{L^{2}} + \frac{π^{2}}{6L^{2}} − \frac{2γ}{L^{2}} + δ_{7}(log_{2} N))

+ 3N log_{2}^{2} N + N log_{2} N · (−\frac{7}{L} − 3 − 6α − \frac{10γ}{L} + δ_{8}(log_{2} N))

+ N(−22 − \frac{41}{6L} + \frac{β_{2}}{L} − \frac{3γ}{L} − \frac{7γ}{L^{2}}

+ 2α − β + \frac{7α}{L} + 3α^{2} − \frac{6αγ}{L} + \frac{3γ^{2}}{L^{2}}

+ \frac{π^{2}}{2L^{2}} + \frac{6}{L^{2}} − \frac{2}{L} ∑_{k≥3} \frac{(−1)^{k+1}(k − 5)}{(k + 1)k(k − 1)(2^{k} − 1)}

+ \frac{2}{L} ∑_{r≥1} b_{r+1} (\frac{L(1 − 2^{−r+1})/2 − 1}{1 − 2^{−r}} − ∑_{k≥2} \frac{(−1)^{k+1}}{k(k − 1)(2^{r+k} − 1)})

+ \frac{2}{L}ŵ′(3) + δ_{9}(log_{2} N)) + O (\frac{log^{2} N}{N} )

with L, α, β, b_{r+1} as in Theorem 4 resp. Lemma 6 and β_{2} from (3.15).

It remains to combine the previous results to get an asymptotic expansion for

Var L_{N} = u_{N} + v_{N} + w_{N} + l_{N} − l_{N}^{2}.  (3.23)

We start with an important observation concerning leading terms formed by periodic fluctuations of mean zero.

Let us assume that, at any stage, we are able to prove

Var L_{N} = δ_{10}(log_{2} N) · N^{μ} log^{ν} N + R_{N}  (3.24)

where δ_{10}(x) is continuous and periodic with period 1 and mean zero and R_{N} = o(N^{μ} log^{ν} N). We claim that δ_{10}(x) must vanish identically under these conditions:

Let us assume δ_{10}(x) ≢ 0. Then, since δ_{10}(x) is continuous with mean 0, there esists an ϵ > 0 and an interval, say [a, b] ⊆ [0, 1], such that δ_{10}(x) < −ϵ for x ∈ [a, b]. Since log_{2} N is dense modulo 1, Var L_{N} would be negative for an infinity of values, an obvious contradiction.

In other words: From (3.24) we may deduce that

Var L_{N} ∼ R_{N},  N → ∞,  (3.25)

so that, in order to prove that Var L_{N} = O(N) we need not collect explicitely the fluctuating contributions of mean zero.

Observing these comments we easily find that all terms of order N^{2} log^{2} N, N^{2} log N, N log^{2} N and N log N in Var L_{N} cancel. The coefficient of N^{2} is of a more delicate nature. The reader should note carefully that the coefficient of N^{2} in l_{N}^{2} will contain the square δ_{1}^{2} of the periodic fluctuation δ_{1} from Theorem 2 and that the mean [δ_{1}^{2}]_{0} of δ_{1}^{2} will not be zero. Therefore we have to extract this term to end up with a fluctuation of mean zero and get for the coefficient of N^{2} in Var L_{N} the expression

\frac{1}{L^{2}} + \frac{π^{2}}{6L^{2}} − \frac{1}{L} − \frac{β_{2}}{L} − \frac{47}{12} − [δ_{1}^{2}]_{0} + δ_{11}(log_{2} N).  (3.26)

The following Lemma is crucial now:

Lemma 8.

\begin{aligned}[δ_{1}^{2}]_{0} & = \frac{1}{L^{2}} ∑_{k≠0} |Γ (−1 − \frac{2kπi}{log 2})|^{2} \\ & = \frac{1}{L^{2}} + \frac{π^{2}}{6L^{2}} − \frac{1}{L} − \frac{β_{2}}{L} − \frac{47}{12}. \end{aligned}

Sketch of Proof^{1}. The proof heavily relies on the following two series transformation results due to Ramanujan. The first one is

\begin{aligned}α^{−N} & (\frac{1}{2}ζ(2N + 1) + ∑_{k≥1} \frac{k^{−2N−1}}{e^{2αk} − 1}) \\ & = (−β)^{−N} (\frac{1}{2}ζ(2N + 1) + ∑_{k≥1} \frac{k^{−2N−1}}{e^{2βk} − 1}) \\ & − 2^{2N} ∑_{k=0}^{N+1} (−1)^{k} \frac{B_{2k}}{(2k)!} \frac{B_{2N+2−2k}}{(2N + 2 − 2k)!}α^{N+1−k}β^{k} \end{aligned}  (3.27)

Here and in the next identity, α and β have to be positive numbers with αβ = π^{2}, ζ(s) is the Riemann ζ–function; N has to be a positive integer and B_{n} indicates the n-th Bernoulli number defined by

\frac{z}{e^{z} − 1} = ∑_{n≥0} B_{n} \frac{z^{n}}{n!} .

The second identity used in the proof is

\begin{aligned}∑_{k≥1} \frac{1}{k(e^{2αk} − 1)} & − \frac{1}{4} log α + \frac{α}{12} \\ & = ∑_{k≥1} \frac{1}{k(e^{2βk} − 1)} − \frac{1}{4} log β + \frac{β}{12}. \end{aligned}  (3.28)

1A full proof of Lemma 8 is long and difficult and included in [10].

In fact, (3.28) is equivalent to a transformation result on Dedekind’s η-function (compare [3])

η(τ) = e^{πiτ/12} ∏_{n≥1} (1 − e^{2πinτ} ) ,  ℑ(τ) > 0,  (3.29)

namely

η(−\frac{1}{τ}) = (−iτ)^{1/2} · η(τ),  ℑ(τ) > 0.  (3.30)

(This is a special instance of Dedekind’s famous result on the behaviour of η under a transformation of the modular group.)

The consequences of Lemma 8 are twofold. On the one hand, we find from (3.26) that the N^{2}-term in Var L_{N} cancels, so that Var L_{N} = O(N). On the other hand we may use the identity to express β_{2} by the other terms occurring in Lemma 8, including [δ_{1}^{2}]_{0} which yields the final form of the constant C in Theorem 2. [δ_{1}δ_{2}]_{0} is the mean of δ_{1}(x)δ_{2}(x), originating from l_{N}^{2}, which has to be extracted to end up with a fluctuation δ(x) of mean zero.

We would like to point out some final remarks concerning this analysis:

i) The occurrence of the finite products Q_{k} gives rise to use results from the theory of partitions, especially Euler’s product identities (3.12) and (3.13).

ii) A periodic fluctuation δ_{1}(x) which has mean zero and very small amplitude may be safely neglected for practical purposes as long as we are only interested in the expectation. In order to establish the correct order of the variance it is of vital importance to study the behaviour of δ_{1}(x), especially the mean of δ_{1}^{2}(x).

iii) The predicted value 0.26600 . . .·N matches perfectly with the values obtained by computer simulations.

iv) As we have mentioned in the Introduction, with this paper we have finally achieved very good information on the average case behaviour of Tries, Patricia Tries and Digital Search Trees in the symmetric case (i.e. we start from 0, 1sequences which contain 0 and 1 with equal probability). Nevertheless the methods of this paper do not seem to be confined to this instance: indeed we hope that sharp results for the asymmetric case may also be established with a similar technical apparatus.

Acknowledgement: The authors would like to thank R.F.Tichy for some helpful remarks.

References

1. M.Abramowitz, I.A.Stegun, Handbook of Mathematical Functions, Dover, New York, 1970.

2. A.Aho, J.Hopcroft, J.Ullman, Data Structures and Algorithms, Addison Wesley, Reading, MA, 1983.

3. T.M.Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer, New York, 1976.

4. E.G.Coffman Jr., J.Eve, File Structures Using Hashing Functions, Comm. ACM 13 (1970), 427–436.

5. R.Fagin, J.Nievergelt, N.Pippenger, H.Strong, Extendible Hashing: A fast Access Method for Dynamic Files, ACM TODS 4 (1979), 315–344.

6. P.Flajolet, R.Sedgewick, Digital Search Trees Revisited, SIAM J. Comput. 15 (1986), 748–767.

7. G. Gonnet, Handbook of Algorithms and Data Structures, Addison-Wesley, Reading MA, 1983.

8. P. Jacquet, M.Regnier, Normal Limiting Distributions for the Size and the External Path Length of Tries, INRIA Technical Report 827 (1988).

9. P.Kirschenhofer, H.Prodinger, Further Results on Digital Search Trees, Theor. Comput. Sci. 58 (1988), 143–154.

10. P.Kirschenhofer, H.Prodinger, On some Applications of Formulae of Ramanujan in the Analysis of Algorithms, preprint (1988).

11. P.Kirschenhofer, H.Prodinger, W.Szpankowski, On the Variance of the External Path Length in a Symmetric Digital Trie, Discrete Appl. Math. 25 (1989), 129–143.

12. P.Kirschenhofer, H.Prodinger, W.Szpankowski, On the Balance Property of Patricia Tries: External Path Length Viewpoint, Theor. Comput. Sci. 68 (1989), 1–17.

13. P.Kirschenhofer, H.Prodinger, W.Szpankowski, Digital Search Trees - Further Results on a Fundamental Data Structure, Proceedings of IFIP 89,G.X.Ritter, ed. (1989), 443–447.

14. D.E.Knuth, The Art of Computer Programming Vol. 3, Addison-Wesley, Reading MA, 1973.

15. A.G.Konheim, D.J.Newman, A Note on Growing Binary Trees, Discrete Mathematics 4 (1973), 57–63.

16. P.Mathys, P.Flajolet, Q-ary Collision Resolution Algorithms in Random-Access Systems with Free and Blocked Channel Access, IEEE IT 31 (1985), 217–243.

17. N.E.Nörlund, Vorlesungen über Differenzenrechnung, Chelsea, New York, 1954.

18. B.Pittel, Paths in a Random Digital Tree: Limiting Distributions, Adv. Appl. Prob. 18 (1986), 139–155.

19. M.Régnier, P.Jacquet, New Results on the Size of Tries, IEEE Trans.Inf.Theory 35 (1989), 203–205.

20. J.Riordan, Combinatorial Identities, John Wiley & Sons, New York, 1968.

21. A.N.Shiryayev, Probability, Springer, New York, 1984.

22. W.Szpankowski, Some Results on v-ary Asymmetric Tries, J.Algorithms 9 (1988), 224-244.

23. W.Szpankowski, A Characterization of Digital Search Trees from the Successful Search Viewpoint, Theor. Comput. Sci. (in press) (1990).

24. W.Szpankowski, Patricia Tries again Revisited, Journal of the ACM (in press) (1990).

TU Vienna, Wiedner Hauptstraße 8-10, A-1040 Vienna, Austria and Purdue University, West Lafayette, IN 47907, USA