A q–ANALOGUE OF THE PATH LENGTH OF BINARY SEARCH TREES

HELMUT PRODINGER

Abstract. A reformulation of the path length of binary search trees is given in terms of permutations, allowing to extend the definition to the instance of words, where the letters are obtained by independent geometric random variables (with parameter q). In this way, expressions for expectation and variance are obtained which in the limit for q → 1 are the classical expressions.

The path length ρ(t) of a binary search tree t satisfies the recursion ρ(t) = ρ(t_{L}) + ρ(t_{R}) + |t_{L}| + |t_{R}| where t_{L} and t_{R} are the left resp. right subtree of the root. (|t| denotes the size of the tree t, i. e. the number of nodes.)

Binary search trees are obtained from permutations. For some background see [5, 2, 3]. Our aim is to rewrite the definition of the path length in terms of permutations, since then we are able to obtain q–analogues: This is done by considering words over the alphabet {1, 2, … } instead, with probabilities (weights) for the letters p, pq, pq^{2}, …, where p + q = 1 (geometric probability distribution). In the limit q → 1, this model turns into the model of random permutations, as equal letters appear with probability 0 and each relative ordering is equally likely.

For a permutation π = π_{1} … π_{n} we define ρ(π) by

ρ(π) = |{(j, k) | 1 ≤ j < k ≤ n, π_{j} = min{π_{j}, …, π_{k}} or π_{k} = min{π_{j}, …, π_{k}}}|.

Then ρ(□) = 0 and, if π = σ1τ, then ρ(π) = ρ(σ) + ρ(τ) + |σ| + |τ|, as pairs with the left coordinate in σ and the right coordinate in τ are definitely not counted.

This definition gives the path length of the binary search tree associated to the permutation π = π_{1} … π_{n}, provided we interpret π_{i} as the arrival position of key i.

But this definition of π can be taken as it is, where π_{1} … π_{n} now denotes a word over the alphabet {1, 2, … }. This will be our starting point.

We want to point out that our previous paper [4] contains easier but related parameters.

In the sequel we want to compute the expectation and the variance of the parameter ρ, for random words of length n. The probability model is as follows: the probability of letter i is pq^{i−1}, and the letters are independent, so that the word a_{1} … a_{m} appears with probability (\frac{p}{q})^{m}q^{a_{1}+···+a_{m}}. We define random variables

Date: October 14, 2000.

1991 Mathematics Subject Classification. 05A15, 05A30, 68P10.

Key words and phrases. Binary search tree, path length, permutations, geometric distribution, q–analogues, harmonic numbers.

L_{jk} = \begin{cases}1 & if π_{j} = min\{π_{j}, …, π_{k}\} \\ 0 & otherwise, \end{cases}
R_{jk} = \begin{cases}1 & if π_{k} = min\{π_{j}, …, π_{k}\} \\ 0 & otherwise, \end{cases}
B_{jk} = L_{jk} · R_{jk},
N_{jk} = (1 − L_{jk}) · (1 − R_{jk}).

(The letters L, R, B, N are chosen to indicate left, right, both, not.) Then the parameter ρ may be described as

ρ = ∑_{1≤j<k≤n} [L_{jk} + R_{jk} − B_{jk}].

Now we can introduce the generating function

f(v) = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∏_{1≤j<k≤n} [L_{jk}v + R_{jk}v − B_{jk}v + N_{jk}];

the coefficient of v^{k} in f(v) is the probability that parameter ρ has value k, assuming random words of length n. As always, the expected value is obtained via 𝔼 = f′(1);

𝔼 = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∑_{1≤j<k≤n} (L_{jk} + R_{jk} − B_{jk})

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j}[ ∑_{L_{jk}=1} q^{i_{j}+···+i_{k}} + ∑_{R_{jk}=1} q^{i_{j}+···+i_{k}} − ∑_{B_{jk}=1} q^{i_{j}+···+i_{k}}]

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j}[2 ∑_{i≥1} q^{i(k+1−j)} \frac{1}{p^{k−j}} − ∑_{i≥1} q^{i(k+1−j)} \frac{1}{p^{k−j−1}} ]

= (2p − p^{2}) ∑_{1≤j<k≤n} (\frac{1}{q})^{k+1−j} ∑_{i≥1} q^{i(k+1−j)}

= p(2 − p) ∑_{1≤j<k≤n} \frac{1}{1 − q^{k+1−j}}

= p(2 − p) ∑_{2≤i≤n} \frac{n + 1 − i}{1 − q^{i}}

= p(2 − p) ∑_{1≤i≤n} \frac{n + 1 − i}{1 − q^{i}} − n(2 − p).

The terms that would survive the limit q → 1 are

2p ∑_{1≤i≤n}(n + 1 − i)\frac{1}{1 − q^{i}} − 2n,

and the limit is

lim_{q→1} 𝔼 = 2 ∑_{1≤i≤n} \frac{n + 1 − i}{i} − 2n = 2(n + 1)H_{n} − 4n,

as is of course well known. (The notations H_{n} = ∑_{1≤k≤n} \frac{1}{k} and H_{n}^{(2)} = ∑_{1≤k≤n} \frac{1}{k^{2}} refer to harmonic numbers of the first and second order, see e. g. [1].)

Now we turn to the variance, and this is much harder, since we must first compute the second factorial moment, which is obtained by a second derivative;

𝔼\underline{2} = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ×

× ∑_{1≤j<k≤n,1≤l<m≤n,(j,k)≠(l,m)} (L_{jk} + R_{jk} − B_{jk})(L_{lm} + R_{lm} − B_{lm})

= (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ×

× ∑_{1≤j<k≤n,1≤l<m≤n,(j,k)≠(l,m)} (2L_{jk}L_{lm} + 2L_{jk}R_{lm} − 4L_{jk}B_{lm} + B_{jk}B_{lm})

= 2Ξ^{LL} + 2Ξ^{LR} − 4Ξ^{LB} + Ξ^{BB}

(using several symmetries). Observe that we use quantities like L_{jk} now also in a deterministic sense. This slight abuse of notation has been chosen in order not to overburden the paper with heavy notation.

The range Λ = {1 ≤ j < k ≤ n, 1 ≤ l < m ≤ n, (j, k) ≠ (l, m)} must be split into the following 12 disjoint subranges:

Λ_{1} = {1 ≤ j < k < l < m ≤ n},
Λ_{2} = {1 ≤ j < l < m < k ≤ n},
Λ_{3} = {1 ≤ j < l < k < m ≤ n},
Λ_{4} = {1 ≤ j < k = l < m ≤ n},
Λ_{5} = {1 ≤ j < l < m = k ≤ n},
Λ_{6} = {1 ≤ j = l < k < m ≤ n},
Λ_{7} = {1 ≤ l < m < j < k ≤ n},
Λ_{8} = {1 ≤ l < j < k < m ≤ n},
Λ_{9} = {1 ≤ l < j < m < k ≤ n},
Λ_{10} = {1 ≤ l < m = j < k ≤ n},
Λ_{11} = {1 ≤ l < j < k = m ≤ n},

Λ_{12} = {1 ≤ l = j < m < k ≤ n}.

And we will have contributions Θ_{i}^{LL}, Θ_{i}^{LR}, Θ_{i}^{LB}, Θ_{i}^{BB}, to Ξ^{LL}, Ξ^{LR}, Ξ^{LB}, Ξ^{BB}, for i = 1, …, 12, according to the 12 ranges Λ_{i}. Therefore we must compute 48 (not necessarily) different contributions. For convenience, we state them as a lemma. Lemma 1. The contributions Θ_{i}^{LL}, Θ_{i}^{LR}, Θ_{i}^{LB}, Θ_{i}^{BB}, for i = 1, …, 12, are given by

Θ_{1}^{LL} = Θ_{7}^{LL} = p^{2} ∑_{1≤j<k<l<m≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{2}^{LL} = Θ_{8}^{LL} = p^{2} ∑_{1≤j<l<m<k≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{3}^{LL} = Θ_{9}^{LL} = p^{2} ∑_{1≤j<l<k<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{4}^{LL} = Θ_{10}^{LL} = p^{2} ∑_{1≤j<k=l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−k}} ,
Θ_{5}^{LL} = Θ_{11}^{LL} = p^{2} ∑_{1≤j<l<m=k≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{6}^{LL} = Θ_{12}^{LL} = p ∑_{1≤j=l<k<m≤n} \frac{1}{1 − q^{m+1−j}};

Θ_{1}^{LR} = Θ_{7}^{LR} = p^{2} ∑_{1≤j<k<l<m≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{2}^{LR} = Θ_{8}^{LR} = p^{2} ∑_{1≤j<l<m<k≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{3}^{LR} = Θ_{9}^{LR} = p^{2} ∑_{1≤j<l<k<m≤n} [\frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} + \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{k+1−j}} − \frac{1}{1 − q^{m+1−j}} ],
Θ_{4}^{LR} = p^{2} ∑_{1≤j<k=l<m≤n} [\frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−k}} + \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{k+1−j}} − \frac{1}{1 − q^{m+1−j}} ],
Θ_{5}^{LR} = p^{2} ∑_{1≤j<l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,
Θ_{6}^{LR} = p^{2} ∑_{1≤j<k<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{k+1−j}} ,
Θ_{10}^{LR} = p ∑_{1≤l<m=j<k≤n} \frac{1}{1 − q^{k+1−l}} ,

Θ_{11}^{LR} = Θ_{12}^{LR} = p^{2} ∑_{1≤l=j<m<k≤n} \frac{1}{1 − q^{k+1−l}};

Θ_{1}^{LB} = Θ_{7}^{LB} = p^{3} ∑_{1≤j<k<l<m≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{2}^{LB} = Θ_{8}^{LB} = p^{3} ∑_{1≤j<l<m<k≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{3}^{LB} = Θ_{9}^{LB} = p^{3} ∑_{1≤j<l<k<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{4}^{LB} = p^{3} ∑_{1≤j<k=l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−k}} ,

Θ_{5}^{LB} = p^{3} ∑_{1≤j<l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{6}^{LB} = p^{2} ∑_{1≤j<k<m≤n} \frac{1}{1 − q^{m+1−j}} ,

Θ_{10}^{LB} = p^{2} ∑_{1≤l<m=j<k≤n} \frac{1}{1 − q^{k+1−l}} ,

Θ_{11}^{LB} = p^{3} ∑_{1≤l<j<k=m≤n} \frac{1}{1 − q^{k+1−l}} ,

Θ_{12}^{LB} = p^{2} ∑_{1≤l=j<m<k≤n} \frac{1}{1 − q^{k+1−l}};

Θ_{1}^{BB} = Θ_{7}^{BB} = p^{4} ∑_{1≤j<k<l<m≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{2}^{BB} = Θ_{8}^{BB} = p^{4} ∑_{1≤j<l<m<k≤n} \frac{1}{1 − q^{k+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{3}^{BB} = Θ_{9}^{BB} = p^{4} ∑_{1≤j<l<k<m≤n} \frac{1}{1 − q^{m+1−j}} ,

Θ_{4}^{BB} = Θ_{10}^{BB} = p^{3} ∑_{1≤j<k=l<m≤n} \frac{1}{1 − q^{m+1−j}} ,

Θ_{5}^{BB} = Θ_{11}^{BB} = p^{3} ∑_{1≤j<l<m≤n} \frac{1}{1 − q^{m+1−j}} \frac{1}{1 − q^{m+1−l}} ,

Θ_{6}^{BB} = Θ_{12}^{BB} = p^{3} ∑_{1≤j=l<k<m≤n} \frac{1}{1 − q^{m+1−j}} .

Proof. The computations are as (or slightly more complicated than) the one for the expected value. We don’t give more details.

We simplify those sums and write a_{i} = \frac{1}{1−q^{i}} for convenience.

Lemma 2.

Ξ^{LL} = 2p^{2} ∑_{2≤i,j≤n−2,i+j≤n} a_{i}a_{j}\binom{n + 2 − i − j}{2}

+ 2p^{2} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)(j − i − 1)

+ 2p^{2} ∑_{3≤i<j≤n} a_{i}a_{j}(n + 1 − j)(i − 2)

+ 4p^{2} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)

+ 2p ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i),

Ξ^{LR} = 2p^{2} ∑_{2≤i,j≤n−2,i+j≤n} a_{i}a_{j}\binom{n + 2 − i − j}{2}

+ 2p^{2} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)(j − i − 1)

+ 4p^{2} ∑_{3≤i<j≤n} a_{i}a_{j}(n + 1 − j)(i − 2)

− 2p^{2} ∑_{4≤i≤n} a_{i}\binom{i − 2}{2}(n + 1 − i)

+ 4p^{2} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)

+ p^{2} ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i)

+ p ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i),

Ξ^{LB} = 2p^{3} ∑_{2≤i,j≤n−2,i+j≤n} a_{i}a_{j}\binom{n + 2 − i − j}{2}

+ 2p^{3} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)(j − i − 1)

A q–ANALOGUE OF THE PATH LENGTH OF BINARY SEARCH TREES 7

+ 2p^{3} ∑_{3≤i<j≤n} a_{i}a_{j}(n + 1 − j)(i − 2)

+ 2p^{3} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)

+ (3p^{2} + p^{3}) ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i),

Ξ^{BB} = 2p^{4} ∑_{2≤i,j≤n−2,i+j≤n} a_{i}a_{j}\binom{n + 2 − i − j}{2}

+ 2p^{4} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)(j − i − 1)

+ 2p^{3} ∑_{2≤i<j≤n} a_{i}a_{j}(n + 1 − j)

+ 2p^{4} ∑_{4≤i≤n} a_{i}\binom{i − 2}{2}(n + 1 − i)

+ 4p^{3} ∑_{3≤i≤n} a_{i}(i − 2)(n + 1 − i).

The variance is given by

𝕍 = 2Ξ^{LL} + 2Ξ^{LR} − 4Ξ^{LB} + Ξ^{BB} + 𝔼 − (𝔼)^{2}.

In order to simplify this expression, we note the following formula: Lemma 3.

p^{2} ∑_{2≤i,j≤n−2,i+j≤n}a_{i}a_{j}\binom{n + 2 − i − j}{2}

= 2p^{2} ∑_{1≤i<j≤n} a_{i}a_{j}\binom{n + 2 − j}{2} − p^{2} ∑_{1≤i≤n} a_{i}\binom{n + 2 − i}{2}(i − 1)

− 2p ∑_{1≤i≤n} a_{i}\binom{n + 1 − i}{2} + \binom{n}{2}.

Proof. Note that

\frac{1}{1 − q^{i}} \frac{1}{1 − q^{j}} = \frac{1}{1 − q^{i+j}} (\frac{1}{1 − q^{i}} + \frac{1}{1 − q^{j}} − 1)

and do some trivial rearrangements. Lemma 4.

( ∑_{1≤i≤n} a_{i}(n + 1 − i))^{2} = 2 ∑_{1≤i<j≤n} a_{i}a_{j}(n + 1 − i)(n + 1 − j) + ∑_{1≤i≤n} a_{i}^{2}(n + 1 − i)^{2}.

Proof. Obvious.

Using these lemmata and numerous simplifications that were partially supported by Maple, we can state our main result:

Theorem 1. The expectation and the variance of the q–ified path length in words of length n, generated by n independent geometric random variables are given by

𝔼 = p(2 − p) ∑_{1≤i≤n} \frac{n + 1 − i}{1 − q^{i}} − n(2 − p)

and

𝕍 = 2p^{2} ∑_{1≤i<j≤n} \frac{(n + 1 − j)(4i + p(5 − 4i))}{(1 − q^{i})(1 − q^{j})}

− p^{2}(2 − p)^{2} ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{(1 − q^{i})^{2}}

+ p ∑_{1≤i≤n} \frac{n + 1 − i}{1 − q^{i}}(6i − 2 + p(−4ni + 4n − 19i + 3i^{2} + 7)

+ 4p^{2}(ni − n + 3i − 1 − i^{2}) + p^{3}(−ni + n + 2i^{2} − 8i + 8))

+ 5pn − 3p^{2}n − 2p^{3}n.

The terms in the variance that would survive the limit q → 1 are these:

8p^{2} ∑_{1≤i<j≤n} \frac{(n + 1 − j)i}{(1 − q^{i})(1 − q^{j})} − 4p^{2} ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{(1 − q^{i})^{2}} + 2p ∑_{1≤i≤n} \frac{(n + 1 − i)(3i − 1)}{1 − q^{i}}.

The limit is

lim_{q→1} 𝕍 = 8 ∑_{1≤j≤n} \frac{(n + 1 − j)(j − 1)}{j} − 4 ∑_{1≤i≤n} \frac{(n + 1 − i)^{2}}{i^{2}} + 2 ∑_{1≤i≤n} \frac{n + 1 − i}{i}(3i − 1)
= 4(n + 1)n − 8(n + 1)H_{n} + 8n − 4(n + 1)^{2}H_{n}^{(2)} + 8(n + 1)H_{n} − 4n
+ 3n(n + 1) − 2(n + 1)H_{n} + 2n
= 7n^{2} − 4(n + 1)^{2}H_{n}^{(2)} − 2(n + 1)H_{n} + 13n.

This is (of course!) the variance in the classical case.

Remark. As one referee has pointed out and as was clear to me from the beginning, one could study the alternative version

ρ(π) = |{(j, k) | 1 ≤ j < k ≤ n, π_{j} or π_{k} is a strict minimum of {π_{j}, …, π_{k}}|.

The expected value is then

\frac{2p}{q} ∑_{1≤j<k≤n} ∑_{i≥1} q^{i(k−j+1)} = 2p ∑_{1≤i≤n}(n + 1 − i)\frac{q^{i}}{1 − q^{i}} − 2qn,

which in the limit q → 1 gives the result 2(n+1)H_{n}−4n, as it should. The computation of the variance would be a bit easier, since terms like B_{jk} would disappear. Nevertheless, a new computation would be complicated enough, perhaps requiring a full day’s work, and so I leave it as an exercise to the interested.

References

[1] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[2] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. Second edition, 1998.

[3] H. M. Mahmoud. Evolution of Random Search Trees. John Wiley, New York, 1992.

[4] H. Prodinger. Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth. submitted, 2000.

[5] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, Department of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa, email: helmut@gauss.cam.wits.ac.za.

Homepage: http://www.wits.ac.za/helmut/index.htm