THE HEIGHT OF q-BINARY SEARCH TREES

MICHAEL DRMOTA AND HELMUT PRODINGER

Abstract. q–binary search trees are obtained from words, equipped with the geometric distribution instead of permutations. The average and variance of the height are computated, based on random words of length n, as well as a Gaussian limit law.

1. Introduction

The paper [6] introduces for the first time a meaningful q–model of binary search trees: Instead of binary search trees, one considers tournament trees, which differ only marginally from binary search trees; if one starts from a permutation ( \begin{matrix}1 & 2 & ··· & n \\ π_{1} & π_{2} & ··· & π_{n} \end{matrix}), then one inserts the number i instead of the number π_{i}. Thus, traversing the tree in inorder, we might think of the associated permutation as ρ1σ, where 1 goes into the root, and ρ resp. σ form (recursively) the left resp. right subtree.

Now instead of considering permutations π_{1}π_{2} ⋯ π_{n}, we consider words over the alphabet {1, 2, 3, … }, and (geometric) probabilities attached to the letters, i. e. the probability of letter i is pq^{i−1}, with p+q = 1. The binary search tree is then constructed by writing a nonempty word w as w = xay, where a is the smallest letter occurring, and x ∈ {a + 1, a + 2, … }^{∗} and y ∈ {a, a + 1, … }^{∗}. The letter a goes into the root and x resp. y form the left resp. right subtree.

The paper [6] dealt with the path length; here we consider the height. The height of a binary search tree (and thus of the trees in our model) is defined to be the largest number of nodes in a path from the root to a leaf; the empty tree (related to the empty word) has height 0.

We will prove that the expected height, when considering random words of length n, is asymptotic to pn; the variance will also be computed as well as a Gaussian limit law. (The letter p will always denote 1 − q in this paper.) Recall that the result for traditional binary search trees is ∼ c log n with c = 4.31107, see [1]; unfortunately we do not get that result as the limit q → 1 as it so happened for the path length. However, nothing is wrong here, since the limit q → 1 in pn simply tells us that the average height should be less than linear. Although this original hope of getting the classical result as a corollary did not work out, we nevertheless think that the results presented here are of independent interest. Note also that pn is the expected number of letters 1 in a (random) string of length n. In our asymmetric model, they must all lie on one path.

Key words and phrases. Binary search tree, q–analog, height.

In more detail, we will obtain the following results:

Let H_{n} denote the height of q–binary search trees with n (internal) nodes (this is a random variable, defined on words of length n).

Theorem 1. For every positive q < 1 the height H_{n} of q–binary search trees with n (internal) nodes satifies a central limit theorem of the form

sup_{x∈ℝ} | Pr\{H_{n} ≤ x\} − Φ (\frac{x − pn}{\sqrt{npq}}) | = O(n^{−1/2}),  (1)

where Φ(x) denotes the normal distribution function

Φ(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{x} e^{−t^{2}/2} dt.

The expected value is given by

𝔼 H_{n} = pn + O (\frac{1}{p}) ,  (2)

in which the O-constant is uniform for 0 < q < 1. The variance can be estimated by

𝕍 H_{n} = pqn + O_{q} (n^{1/2} log^{2} n) .  (3)

The O-constant in the error term of the variance is not uniform for 0 < q < 1. The dependency on q has not been worked out since the order of magnitude of the error term is surely not optimal. However, although the error term for the expected value is uniform, this theorem cannot be used to cover the case q → 1 where it is known that the expected value is given by

𝔼 H_{n} = c log n + O (log log n)

(with c = 4.31107 ⋯, see [1]) and the variance is bounded:

𝕍 H_{n} = O(1)

(see [3, 4]).

2. Weak Convergence

Lemma 1. Let y_{k}(x) denote the generating function

y_{k}(x) = ∑_{n≥0} Pr{H_{n} ≤ k}x^{n}.

Then we have y_{k}(0) = 1 and

y_{k+1}(x) = pxy_{k}(x)y_{k}(qx) + y_{k+1}(qx).  (4)

Proof. The proof is a straight forward translation of the basic decomposition w = xay: If a = 1 (described by px), then the left subtree consists only of letters in {2, 3, … }, described by y_{k}(qx), but the right subtree can have any letters, which is described by y_{k}(x). However, if a > 1, we get the term y_{k+1}(qx) (we might then think of all letters being reduced by 1).

If we write this in the form

\frac{y_{k+1}(x) − y_{k+1}(qx)}{(1 − q)x} = y_{k}(qx)y_{k}(x),

then the limit q → 1 gives

y′_{k+1}(x) = y_{k}^{2}(x),

the usual recursion in the instance of binary search trees. (Recall that \frac{f(x)−f(qx)}{(1−q)x} =: (D_{q} f)(x), and D_{q} is called the q–difference operator.) Also, if we write

y_{k}(x) = ∑_{0≤j<2^{k}} a_{k,j}x^{j},

then we get, by comparing coefficients,

a_{k+1,j} = \frac{p}{1 − q^{j}} ∑_{0≤i<j} a_{k,i} a_{k,j−1−i} q^{i} for j ≥ 1,

and a_{k,0} = 1 for all k ≥ 0.

Lemma 2. The generating functions y_{k}(x) are bounded above by

y_{k}(x) ≤ \frac{1}{1 − x} − \frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1} .  (5)

Furthermore, this inequality is also true on the level of coefficients, i. e.

\begin{aligned}Pr\{H_{n} ≤ k\} & = [x^{n}]y_{k}(x) \\ & ≤ 1 − [x^{n}]\frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1} \\ & = ∑_{l=0}^{k} \binom{n − 1}{l}p^{l}q^{n−1−l}. \end{aligned}  (6)

Note that this upper bound is an exact binomial distribution function which is asymptotically normal with mean p(n − 1) and variance pq(n − 1).

Proof. Since y_{k}(x) ≤ 1/(1 − x) we get from (4) that

y_{k+1}(x) ≤ \frac{px}{1 − qx}y_{k}(x) + \frac{1}{1 − qx}.

4 MICHAEL DRMOTA AND HELMUT PRODINGER

Thus, (5) follows by induction. Note that any step in these calculations is also true on the level of coefficients. Thus,

Pr\{H_{n} ≤ k\} ≤ 1 − [x^{n}]\frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1} .

Set

Y_{k}(x) = \frac{1}{1 − x} − \frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1}

and

Δ_{k}(x) = Y_{k}(x) − Y_{k−1}(x) = \frac{1}{p} (\frac{px}{1 − qx})^{k+1} .

Since

[x^{n}]Δ_{k}(x) = \binom{n − 1}{k}p^{k}q^{n−1−k},

(6) follows immediately. Lemma 3. The generating functions y_{k}(x) are bounded below by

\begin{aligned}y_{k}(x) & ≥ \frac{1}{1 − x} − \frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1} \\ & − \frac{(qx)^{2}}{1 − qx} \frac{(\frac{px}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} \\ & − \frac{qx}{1 − x} (\frac{px}{1 − qx}) \frac{(\frac{px}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} \\ & + \frac{qx^{2}}{1 − x} (\frac{px}{1 − qx})^{k+1} \frac{1 − (qx)^{k}}{1 − qx} . \end{aligned}  (7)

Furthermore, this inequality is also true on the level of coefficients.

Proof. First we use the trivial lower bound

y_{k}(x) ≥ \frac{1 − x^{k+1}}{1 − x}

and the upper bound (5) to obtain the inequality

y_{k+1}(x) = pxy_{k}(x)y_{k}(qx) + y_{k+1}(qx)

≥ x(1 − q)y_{k}(x) (\frac{1}{1 − qx} − \frac{(qx)^{k+1}}{1 − qx} ) + \frac{1}{1 − qx} − \frac{(qx)^{k+2}}{1 − qx}

≥ \frac{px}{1 − qx}y_{k}(x) + \frac{1}{1 − qx}

− px\frac{(qx)^{k+1}}{1 − qx} (\frac{1}{1 − x} − \frac{x}{1 − x} (\frac{px}{1 − qx})^{k+1}) − \frac{(qx)^{k+2}}{1 − qx} .

Now (7) follows by induction. As in the proof of Lemma 2 it can be observed that (7) is also true on the level of coefficients.

In order to obtain proper error terms for the lower bound for Pr{H_{n} ≤ k} which may derived from Lemma 3 we make use of the following lemma.

Lemma 4. Let 0 < q < 1 be given and let F (x) be a function which is analytic for |x| < 1 + ε for some ε > 0. Then there exist c > 0 and η > 0 such that

[x^{n}]F (x) (\frac{px}{1 − qx})^{k} = O (n^{−1/2} exp (−\frac{c}{n}(k − pn)^{2}))  (8)

and

[x^{n}]F (x)\frac{(\frac{px}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} = O (n^{−1/2} exp (−\frac{c}{n}(k − pn)^{2})) + O(q^{k})  (9)

uniformly for |k − pn| ≤ ηn as n → ∞.

Proof. By using standard saddle point asymptotics (compare with [2]) it follows that

[x^{n}]F (x) (\frac{px}{1 − qx})^{k} = \frac{1}{2πi} ∫_{|z|=x_{0}} F (z) (\frac{pz}{1 − qz} )^{k} \frac{dz}{z^{n+1}}

= O (n^{−1/2}x_{0}^{−n} (\frac{px_{0}}{1 − qx_{0}} )^{k}) ,

where the saddle point x = x_{0} = (1 − \frac{k}{n}) /q is determined by the equation

\frac{x\frac{d}{dx} (\frac{px}{1−qx})}{\frac{px}{1−qx}} = \frac{n}{k}.

In particular we have x_{0} = 1 if k/n = p. Finally a local expansion of

x_{0}^{−n} (\frac{px_{0}}{1 − qx_{0}} )^{k} = \frac{q^{n−k}p^{k}}{(1 − \frac{k}{n})^{n−k} (\frac{k}{n})^{k}}

completes the proof of (8).

The proof of (9) runs along similar lines. However, we have to be a little bit more careful. The reason is that the denominator

\frac{pz}{1 − qz} − qz

is singular for z_{1} = 0 and for z_{2} = (−1 + 2q)/q^{2}. Nevertheless the whole part

\frac{(\frac{pz}{1−qz} )^{k} − (qz)^{k}}{\frac{pz}{1−qz} − qz}

is regular for |z| < 1/q. Note that |z_{2}| > 1 for 0 < q < \sqrt{2} − 1 and that |z_{2}| < 1 for \sqrt{2} − 1 < q < 1. Thus, if q ≠ \sqrt{2} − 1 we get similarly to the above

[x^{n}]F (x)\frac{(\frac{px}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} = \frac{1}{2πi} ∫_{|z|=x_{0}} F (z)\frac{(\frac{pz}{1−qz} )^{k} − (qz)^{k}}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}}

= \frac{1}{2πi} ∫_{|z|=x_{0}} F (z) \frac{(\frac{pz}{1−qz} )k}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}} − \frac{1}{2πi} ∫_{|z|=x_{0}} F (z) \frac{(qz)^{k}}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}}

= \frac{1}{2πi} ∫_{|z|=x_{0}} F (z) \frac{(\frac{pz}{1−qz} )k}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}} − \frac{1}{2πi} ∫_{|z|=1} F (z) \frac{(qz)^{k}}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}}

= O (n^{−1/2}x_{0}^{−n} (\frac{px_{0}}{1 − qx_{0}} )^{k}) + O(q^{k}).

Note that we just shifted the paths of integration in regions of analyticity if η is chosen sufficiently small such that |x_{0} − 1| < |1 − z_{2}|.

If q = \sqrt{2}−1 then there are polar singularities at z_{2} = −1 after splitting the integral. However, the residues of the functions involved (at z = −1) are both of order

O((\sqrt{2} − 1)^{k}) = O(q^{k}),

which implies that we get the same error term as in the case q ≠ \sqrt{2} − 1.

Note further that (with a little bit more effort) we could have been much more precise. However, the bound given by Lemma 4 is sufficient for our purposes.

Lemma 5. For every 0 < q < 1 there exist c > 0 and η > 0 such that

| Pr\{H_{n} ≤ k\} − ∑_{l=0}^{k} \binom{n − 1}{l}p^{l}q^{n−1−l} | = O (n^{−1/2} exp (−\frac{c}{n}(k − pn)^{2})) (10)

THE HEIGHT OF q-BINARY SEARCH TREES 7

uniformly for |k − pn| ≤ ηn and

| Pr\{|H_{n} − pn| ≥ m\}| = O (exp ( − c\frac{m^{2}}{n} ))  (11)

uniformly for |m| ≤ ηn as n → ∞.

Proof. First we note that Lemma 4 applies to the function

\frac{(qx)^{2}}{1 − qx} \frac{(\frac{px}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} .

The remaining error term will now be treated in the same way as in the proof of Lemma 4:

[x^{n}](\frac{qx}{1 − x} (\frac{px}{1 − qx}) \frac{(\frac{px)}{1−qx})^{k} − (qx)^{k}}{\frac{px}{1−qx} − qx} + \frac{qx^{2}}{1 − x} (\frac{px}{1 − qx})^{k+1} \frac{1 − (qx)^{k}}{1 − qx} )

= \frac{1}{2πi} ∫_{|z|=1−ε} (\frac{qz}{1 − z} (\frac{pz}{1 − qz} ) \frac{(\frac{pz}{1−qz} )^{k} − (qz)^{k}}{\frac{pz}{1−qz} − qz} − \frac{qz^{2}}{1 − z} (\frac{pz}{1 − qz} )^{k+1} \frac{1 − (qz)^{k}}{1 − qz} ) \frac{dz}{z^{n+1}}

= \frac{1}{2πi} ∫_{|z|=x_{0}} (\frac{qz}{1 − z} (\frac{pz}{1 − qz} ) \frac{1}{\frac{pz}{1−qz} − qz} − \frac{qz^{2}}{1 − z} \frac{pz}{1 − qz} \frac{1}{1 − qz} ) (\frac{pz}{1 − qz} )^{k} \frac{dz}{z^{n+1}}

− \frac{1}{2πi} ∫_{|z|=1−k^{−1}} \frac{qz}{1 − z} (\frac{pz}{1 − qz} ) \frac{(qz)^{k}}{\frac{pz}{1−qz} − qz} \frac{dz}{z^{n+1}}

+ \frac{1}{2πi} ∫_{|z|=1−k^{−1}} \frac{qz^{2}}{1 − z} (\frac{pz}{1 − qz} )^{k+1} \frac{(qz)^{k}}{1 − qz} \frac{dz}{z^{n+1}}

= O (n^{−1/2}x_{0}^{−n} (\frac{px_{0}}{1 − qx_{0}} )^{k}) + O(kq^{k}).

Here we used the estimates

max_{|z|=1−k^{−1}} |z^{k}| = O(1)

and

max_{|z|=1−k^{−1}} |\frac{pz}{1 − qz} | = O(1).

Finally observe that in the range |k − pn| ≤ ηn we surely have

kq^{k} = O (n^{−1/2} exp (−\frac{c}{n}(k − pn)^{2}))

which completes the proof of (10).

The proof of (11) is now easy. We just have to combine a proper tail estimate for the binomal distribution, i. e.

∑_{|l−pn|≥m} \binom{n − 1}{l}p^{l}q^{n−1−l} = O (exp ( − c\frac{m^{2}}{n} )) ,

with (10).

We are now able to complete the first part of Theorem 1. It is well known that the distribution function of the binomial distribution can be estimated by the distribution function of the normal distribution up to a uniform error of order O(n^{−1/2}), i. e., as n → ∞,

sup_{x∈ℝ} | ∑_{l≤x} \binom{n − 1}{l}p^{l}q^{n−1−l} − Φ (\frac{l − pn}{\sqrt{pqn}})| = O(n^{−1/2}),  (12)

compare with [5, p. 542].

Furthermore, by (10) we get a similar result for the distribution of H_{n}:

sup_{x∈ℝ} | Pr\{H_{n} ≤ x\} − ∑_{l≤x} \binom{n − 1}{l}p^{l}q^{n−1−l}| = O(n^{−1/2}).  (13)

Note that (10) provides (13) just for x with |x − pn| ≤ ηn. However, by (11) we know that

| Pr{|H_{n} − pn| ≥ ηn}| = O (exp (−cη^{2}n)) .

By the monotonicity of the distribution function this implies that for x with |x−pn| ≥ ηn we also have

| Pr{|H_{n} − pn| ≥ x}| = O (exp (−cη^{2}n)) .

Thus (13) follows.

The first part of Theorem 1, i. e. (1), is now a trivial consequence of (12) and (13).

3. Convergence of Moments

Lemmata 2 and 3 can be easily used to get quite tight bounds for the expected value. Note that

∑_{n≥0} 𝔼 H_{n} x^{n} = ∑_{k≥0} (\frac{1}{1 − x} − y_{k}(x))  (14)

Lemma 6. The expected value of H_{n} can be bounded by

pn − p ≤ 𝔼 H_{n} ≤ pn + O (\frac{1}{p}) .  (15)

Proof. Set

E(x) = ∑_{k≥0} (\frac{1}{1 − x} − y_{k}(x)) .

Then by (5) we obtain

E(x) ≥ \frac{x}{1 − x} ∑_{k≥0} (\frac{px}{1 − qx})^{k+1} = \frac{px^{2}}{(1 − x)^{2}} ,

which is also true on the level of coefficients. Thus, we have

𝔼 H_{n} ≥ p(n − 1).

Similarly we get the upper bound. From

E(x) ≤ \frac{px^{2}}{(1 − x)^{2}} + \frac{(qx)^{2}}{1 − qx} \frac{1}{(\frac{px}{1−qx}) − qx} (\frac{1}{1 − \frac{px}{1−qx}} − \frac{1}{1 − qx})

+ \frac{qx}{1 − x} (\frac{px}{1 − qx}) \frac{1}{(\frac{px}{1−qx}) − qx} (\frac{1}{1 − \frac{px}{1−qx}} − \frac{1}{1 − qx})

− \frac{qx^{2}}{1 − x} \frac{(\frac{px}{1−qx})}{1 − qx} (\frac{1}{1 − \frac{px}{1−qx}} − \frac{1}{1 − \frac{qx^{2}(1−q)}{1−qx}} )

= \frac{px^{2}}{(1 − x)^{2}} + \frac{(qx)^{2}}{(1 − x)(1 − qx)}

+ \frac{pqx^{2}}{(1 − x)^{2}(1 − qx)} − \frac{pqx^{3}}{(1 − x)^{2}(1 − qx)} + \frac{pqx^{3}}{(1 − x)(1 − qx) (1 − \frac{pqx^{2}}{1−qx})}

= \frac{px^{2}}{(1 − x)^{2}} + \frac{(qx)^{2}}{(1 − x)(1 − qx)} + \frac{pqx^{2}}{(1 − x)(1 − qx)} + \frac{pqx^{3}}{(1 − x) (1 − qx − pqx^{2})}

we directly obtain

𝔼 H_{n} ≤ pn + O (\frac{1}{p}) .

This completes the proof of Lemma 6.

Unfortunately it seems that we cannot prove similarly tight estimates for the variance. However, we can obtain a non–trivial result:

Lemma 7. The variance of H_{n} can be bounded by

𝕍 H_{n} = pqn + O_{q} (n^{1/2} log^{2} n) .  (16)

Proof. If F (x) = Pr{X ≤ x} denotes the distribution function of a random variable X (of compact support) then the variance of X can be represented by

𝕍 X = 2 ∫_{−∞}^{𝔼X}(𝔼X − y)F (y) dy + 2 ∫_{𝔼X}^{∞}(y − 𝔼X)(1 − F (y)) dy.

We apply this formula for the height H_{n} where we have very precise estimates for 𝔼H_{n} and its distribution function F_{n}(x) = Pr{H_{n} ≤ x}, compare with Lemma 5 and Lemma 6.

Let u ≤ η\sqrt{n} be a parameter to be defined later. By applying Lemma 5 and Lemma 6 we get

2 ∫_{0}^{𝔼H_{n}−u\sqrt{n}}(𝔼H_{n} − y)F_{n}(y) dy = O (ne^{−cu^{2}}) ,

2 ∫_{𝔼H_{n}−u\sqrt{n}}^{𝔼H_{n}}(𝔼H_{n} − y)F_{n}(y) dy = \frac{pqn}{2} + O (u^{2}\sqrt{n} ) ,

2 ∫_{𝔼H_{n}}^{𝔼H_{n}−u\sqrt{n}}(y − 𝔼H_{n})(1 − F_{n}(y)) dy = \frac{pqn}{2} + O (u^{2}\sqrt{n} ) ,

and

2 ∫_{𝔼H_{n}−u\sqrt{n}}^{n}(y − 𝔼H_{n})(1 − F_{n}(y)) dy = O (ne^{−cu^{2}}) .

Choosing u = log^{2} n gives the result.

References

[1] L. Devroye and B. Reed, On the variance of the height of random binary search trees, SIAM J. Comput. 24 (1995), 1157–1162.

[2] M. Drmota, A bivariate asymptotic expansion of coefficients of powers of generating functions, Europ. J. Combinatorics 15 (1994), 139–152.

[3] M. Drmota, The variance of the height of binary search trees, Theoret. Comput. Sci., to appear.

[4] B. Reed, The height of a random binary search tree, J. Assoc. Comput. Mach., submitted.

[5] W. Feller, An Introduction to Probability Theory and Its Applications, Vol. II , 2^{nd} ed., J. Wiley, New York, 1971.

[6] H. Prodinger, A q–analogue of the path length of binary search trees, Algorithmica, to appear, 2001.

Department of Geometry, Technical University of Vienna, Wiedner Hauptstrasse 8–10, A-1040 Vienna, Austria

 E-mail address: michael.drmota@tuwien.ac.at

The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

 E-mail address: helmut@gauss.cam.wits.ac.za