# Them-Version of Binary Search Trees: An Average Case Analysis

Authors: Helmut Prodinger
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Following a suggestion of Cichoń and Macyna, binary search trees are
generalized by keepingm (classical) binary search trees and distributing incoming data at random to the individual trees. Costs for unsuccessful and successful search are analyzed, as well as the internal path length.


---

## Body

## 1. Introduction

Cichoń, together with his coauthor Macyna, had the seminal idea [1] to generalize approximate counting to approximate counting withmcounters. While in the original version [2] a stream of letters (a word) is dealt with a counter in a certain way (that is of no interest here), the new version uses m counters and chooses for each letter one of these counters (with probability 1/m), where it is dealt with as usual. The result of the procedure is the sum of the individual results of the m counters.This fundamental idea should, however, not be restricted to approximate counting! Indeed, it can be considered within a variety of different contexts. In this paper, the fundamental idea is applied tobinary search trees. They are very well understood and described in classic books such as [3, 4], with plenty of backward pointers to the older literature due to Lynch, Hibbard, Louchard, Brown, Shubert, and many others. We assume that, instead of just one, m binary search trees are kept, and for each element, when inserting it, a decision is made to which of the m trees it is being sent. Of course, for algorithmic purposes, this choice must be deterministic, so that one knows in which tree to search. However, for the analysis, it is assumed that each tree is equally likely and will be selected with probability 1/m.Almost all the information about binary search trees that is known to this day can be found in the encyclopedic books [3, 4]. We only mention that they originate from random permutations (typically of {1,…,n}); a new element is compared to the root and, if there is no space for it, is moved to the left/right if it is smaller/larger than the root; then the process continues. A binary search tree is used as a data structure. It is, thus, essential that one can find existing elements in a reasonable number of steps and also get the information that a searched element is not present after a small number of comparisons.This is the first paper aboutm binary search trees, and the hope is that many more will be written in the future, by various specialists. Thus, no completeness is aimed at. Three parameters are studied. The cost for inserting a new element into the m trees, which is related to the cost of unsuccessful search, then the cost for successful search, which is the average of the level of all the elements in all m trees, and then the internal path length, which is the sum of the internal path lengths of the m trees.In the classical case, probability generating functions are available, so that one can extract moments from them, which can be written in terms of harmonic numbers and generalizations. We describe here how this probability generating functions translate to them-model.We try to use consistent notation: if the probability generating function isf(z), then we write ℱ(z) for the transformed m-version. We always write n for the number of nodes in a classical binary search tree and N for the total number of nodes in the m binary search trees. Furthermore, we write Pn,k, 𝒫N,k, En, En(2), ℰN, and ℰN(2) for probabilities and moments. We use the second factorial moments on our way to the variance.A crucial expression is(1)m-NN!n1!⋯nm!,
with n1+⋯+nm, which is the probability that the N data split into m sets of sizes n1,…,nm each.It turns out that we have to use three auxiliary quantities, namedSN, TN, and UN, which are introduced in the next section. All our quantities of interest can be expressed in terms of them. This is done in full in the section on unsuccessful search but only sketched in the remaining sections, since the actual computations are quite long.The intuition is of course that each of them binary search tree should have roughly N/m nodes; the analysis that follows will make this precise.The classic book [5] is an excellent source on harmonic numbers and their manipulation; in fact, quantity Tn appears already in it!


## 2.  Unsuccessful Search

The first parameter that we study is the number of comparisons to insert noden into a binary search tree with n nodes. This is directly related to searching for a key which is not present, since it is equivalent to insert this (nonexistent) item as the (n+1)st node. The probability generating function is
(2)gn(z)=1n!2z(2z+1)⋯(2z+n-2),
so that the probability that k comparisons are needed is
(3)Pn,k=1n![zk]2z(2z+1)⋯(2z+n-2).
From this, one derives that
(4)En=gn′(1)=∑j=0n-2‍2j+2=2∑j=2n‍2j=2(Hn-1),(5)En(2)=8∑2≤i<j≤n‍1ij=8∑1≤i<j≤n‍1ij-8∑1<j≤n‍1j=4Hn2-4Hn(2)-8Hn+8.
All this is classical. Now we translate this into the m-model. The largest node N sits in one of the m binary search trees of size n. Therefore,
(6)𝒫n,k=m-N∑n1+⋯+nm=N‍N!n1!⋯nm!∑i=1m‍(N-1ni-1)(Nni)Pni,k=m1-N∑n1+⋯+nm=N‍N!n1!…nm!n1NPn1,k=m1-N∑n=1N‍(Nn)(m-1)N-nnNPn,k=m1-N∑n=1N‍(N-1n-1)(m-1)N-nPn,k.
The quotient (N-1ni-1)/(Nni) is the probability that the remaining ni-1 nodes can be chosen. On the level of probability generating functions, this means that
(7)𝒢n(z)=m1-N∑n=1N‍(N-1n-1)(m-1)N-ngn(z).
The last form is obtained by multiplication by zk and summing. Moments can be computed from this using differentiations. In order to do so, we need some auxiliary sums, that will be also useful in later sections.Lemma 1.
(
1
)
(8)
S
n
=
∑
k
=
1
n
‍
(
n
k
)
x
k
1
k
=
∑
k
=
1
n
‍
(
1
+
x
)
k
k
-
H
n
,
(
2
)
(9)
T
n
=
∑
k
=
1
n
‍
(
n
k
)
x
k
H
k
=
H
n
(
1
+
x
)
n
-
(
1
+
x
)
n
∑
k
=
1
n
‍
1
k
(
1
+
x
)
k
,
(
3
)
(10)
U
n
=
∑
k
=
1
n
‍
(
n
k
)
x
k
∑
1
≤
i
<
j
≤
k
‍
1
i
j
=
(
1
+
x
)
n
H
n
2
-
H
n
(
2
)
2
-
(
1
+
x
)
n
∑
k
=
1
n
‍
1
k
(
1
+
x
)
k
H
n
-
k
+
(
1
+
x
)
n
∑
k
=
1
n
‍
1
k
(
1
+
x
)
k
H
k
-
(
1
+
x
)
n
∑
k
=
1
n
‍
1
k
2
(
1
+
x
)
k
.Proof.
All the proofs are using the basic recursion for binomial coefficients, to create a first order recursion which can be solved by summation. The procedure forTn is contained in [5]:
(11)Sn+1=∑k=1n+1‍[(nk)+(nk-1)]xk1k=Sn+∑k=1n+1‍(nk-1)xk1k=Sn+1n+1∑k=1n+1‍(n+1k)xk=Sn+1n+1(1+x)n+1-1n+1,Tn+1=∑k=1n+1‍[(nk)+(nk-1)]xkHk=Tn+∑k=1n+1‍(nk-1)xkHk-1+∑k=1n+1‍(nk-1)xk1k=Tn+x∑k=0n‍(nk)xkHk+1n+1∑k=1n+1‍(n+1k)xk=(1+x)Tn+1n+1(1+x)n+1-1n+1,Un+1=Un+∑k=1n+1‍(nk-1)xk∑1≤i<j≤k‍1ij=Un+x∑k=0n‍(nk)xk∑1≤i<j≤k+1‍1ij=Un+x∑k=0n‍(nk)xk∑1≤i<j≤k‍1ij+x∑k=0n‍(nk)xk∑1≤i≤k‍1i(k+1)=(1+x)Un+1n+1∑k=0n‍(n+1k+1)xk+1Hk=(1+x)Un+1n+1∑k=1n+1‍(n+1k)xk(Hk-1k)=(1+x)Un+1n+1∑k=1n+1‍(n+1k)xkHk-1n+1∑k=1n+1‍(n+1k)xk1k=(1+x)Un+1n+1Tn+1-1n+1Sn+1.
Therefore,
(12)Un(1+x)n=Un-1(1+x)n-1+1n(1+x)nTn-1n(1+x)nSn=Un-1(1+x)n-1+1nHn-1n∑k=1n‍1k(1+x)k-1n(1+x)n∑k=1n‍(1+x)kk+1n(1+x)nHn=∑j=1n‍1jHj-∑j=1n‍1j∑k=1j‍1k(1+x)k-∑j=1n‍1j(1+x)j∑k=1j‍(1+x)kk+∑j=1n‍1j(1+x)jHj=Hn2+Hn(2)2-∑k=1n‍∑j=kn‍1k(1+x)k1j-∑k=1n‍∑j=kn‍(1+x)kk1j(1+x)j+∑j=1n‍1j(1+x)jHj=Hn2+Hn(2)2-∑k=1n‍1k(1+x)k(Hn-Hk-1)-∑k=1n‍∑j=0n-k‍1(j+k)k(1+x)j+∑j=1n‍1j(1+x)jHj=Hn2+Hn(2)2-Hn∑k=1n‍1k(1+x)k+∑k=1n‍1k(1+x)kHk-∑k=1n‍1k2(1+x)k-∑k=1n‍∑j=1n-k‍1(j+k)k(1+x)j-∑k=1n‍1k2+∑j=1n‍1j(1+x)jHj=Hn2-Hn(2)2-Hn∑k=1n‍1k(1+x)k+2∑k=1n‍1k(1+x)kHk-∑k=1n‍1k2(1+x)k-∑j=1n-1‍∑k=1n-j‍1jk(1+x)j+∑j=1n-1‍∑k=1n-j‍1(j+k)j(1+x)j=Hn2-Hn(2)2-Hn∑k=1n‍1k(1+x)k+2∑k=1n‍1k(1+x)kHk-∑k=1n‍1k2(1+x)k-∑j=1n-1‍1j(1+x)jHn-j+∑j=1n-1‍1j(1+x)j(Hn-Hj)=Hn2-Hn(2)2+∑k=1n‍1k(1+x)kHk-∑k=1n‍1k2(1+x)k-∑k=1n‍1k(1+x)kHn-k.In our applications,x=1/(m-1), and then the formulae read
(13)(1-1m)NTN=HN-∑k=1N‍1k(1-1m)k,(14)(1-1m)NUN=HN2-HN(2)2-∑k=1N‍1k(1-1m)kHN-k+∑k=1N‍1k(1-1m)kHk-∑k=1N‍1k2(1-1m)k.After these long but necessary computations have been done, we can now compute the moments:(15)ℰN=m1-N∑n=1N‍(N-1n-1)(m-1)N-n2(Hn-1)=2m1-N∑n=1N‍(N-1n-1)(m-1)N-nHn-2=2m1-N∑n=1N‍(N-1n-1)(m-1)N-n(Hn-1+1n)-2=2m1-N(m-1)N-1TN-1+2mN-2mN(1-1m)N-2.
Therefore,
(16)ℰN=2HN-1-2∑k=1N-1‍1k(1-1m)k+2mN-2mN(1-1m)N-2.
Now, by two differentiations,  we find by a similar (but much longer) computation as before:(17)ℰN(2)+4ℰN=m1-N∑n=1N‍(N-1n-1)×(m-1)N-n[4Hn2-4Hn(2)]=8(1-1m)N-1UN-1+8mN(1-1m)NTN-8mN(1-1m)NSN=4(HN-12-HN-1(2))-8∑k=1N-1‍1k(1-1m)kHN-1-k+8∑k=1N-1‍1k(1-1m)kHk-8∑k=1N-1‍1k2(1-1m)k+8mNHN-8mN∑k=1N‍1k(1-1m)k-8mN∑k=0N-1‍1N-k(1-1m)k+8mN(1-1m)NHN.From these results, we can get the varianceexplicitly as (ℰN(2)+4ℰN)-3ℰN-(ℰN)2. We do not display it, since it is quite long. However, we will drop exponentially small terms of the form O(ϱN) with 1-(1/m)<ϱ<1; then the results are a bit more appealing:
(18)ℰN~2HN-1-2logm+2mN-2,ℰN(2)+4ℰN~4(HN-12-HN-1(2))-8∑k=1N-1‍1k(1-1m)kHN-1-k+8C1(m)-8C2(m)+8mNHN-8mNlogm-8mN∑k=0N-1‍1N-k(1-1m)k,
with
(19)C1(m)=∑k≥1‍1k(1-1m)kHk,C2(m)=∑k≥1‍1k2(1-1m)k.
The sums can be extended to infinity; the extra terms are absorbed in our exponentially small remainder term.The remaining sums can be asymptotically evaluated:(20)∑k=0N-1‍1N-k(1-1m)k=[zN]log11-z·11-z(1-(1/m))=[zN]log11-z·[m-m(m-1)(1-z)+⋯]=mN-m(m-1)(1N-1N-1)+O(N-3),∑k=1N-1‍1k(1-1m)kHN-1-k=[zN-1]∑k≥1‍1k(1-1m)kzk·∑k≥1‍Hkzk=[zN-1]log11-z(1-(1/m))11-zlog11-z=[zN-1][12logm-(m-1)(1-z)+12(m-1)2(1-z)2+⋯]×11-zlog11-z=(logm)HN-1-(m-1)1N-1+12(m-1)2(1N-1-1N-2)+O(N-3).
Not more is required than the generating function of the harmonic numbers. What we have done here is justified by singularity analysis, as described in [6]; note that z=1 is the dominant singularity here.Theorem 2.
The expectation and variance of the number of comparisons needed to insert the last element intom binary search trees of altogether N nodes are given by
(21)ℰN=2logNm+2γ-2+O(1N),𝒱N=2logNm-4log2m+2γ+2-23π2+8C1(m)-8C2(m)+O(1N).
More terms in the asymptotic expansions are easily available.


## 3. Successful Search

Now, we look at successful search in binary search trees. The model is that the comparisons to find all possible nodes areadded, and this count is then divided by the total number of nodes. This parameter has the following probability generating function:
(22)Rn(z)=z(2z)(2z+1)⋯(2z+n-1)nn!(2z-1)-zn(2z-1).
It translates into the m-model as follows:
(23)ℛN(z)=m-N∑n1+⋯+nm=N‍(Nn1,…,nm)×n1Rn1(z)+⋯+nmRnm(z)N=m-N1N∑n=1N‍(Nn)(m-1)N-nnRn(z).
Note that we add the comparisons in each subtree, given by niRni(z), and then divide by the total number N. The following results are classical:
(24)nRn′(1)=nEn=2(n+1)Hn-3n,nRn′′(1)=nEn(2)=4(n+1)×(Hn2-Hn(2))-12nHn-4Hn+16n.
Consequently, we can evaluate moments, in the same style as in the last section. We do not present all the long computations here:
(25)ℰN=m1-N1N∑n=1N‍(Nn)(m-1)N-n[2(n+1)Hn-3n]=2(1-1m)N-1TN-1+2mN-2mN×(1-1m)N+2mN(1-1m)NTN-3=2HN-1-2∑k=1N-1‍1k(1-1m)k+2mN-2mN(1-1m)N-3+2mNHN-2mN∑k=1N‍1k(1-1m)k.
Further,
(26)ℰN(2)=m1-N1N∑n=1N‍(Nn)(m-1)N-nnRn′′(1)=m1-N1N∑n=1N‍(Nn)(m-1)N-n×[4(n+1)(Hn2-Hn(2))-12nHn-4Hn+16n]=8(1-1m)N-1UN-1+4mN(1-1m)N×TN-8mN(1-1m)NSN+8mN(1-1m)NNUN-12(1-1m)N-1×TN-1-12mN+12mN(1-1m)N+16=4(HN-12-HN-1(2))+4mN(HN2-HN(2))-8∑k=1N-1‍1k(1-1m)kHN-1-k+8∑k=1N-1‍1k(1-1m)kHk-8∑k=1N-1‍1k2(1-1m)k+4mNHN-4mN∑k=1N‍1k(1-1m)k-8mN∑k=1N-1‍1N-k(1-1m)k-8mN2+8mNHN(1-1m)N-8mN∑k=1N‍1k(1-1m)kHN-k+8mN∑k=1N‍1k(1-1m)kHk-8mN∑k=1N‍1k2(1-1m)k-12HN-1+12∑k=1N-1‍1k(1-1m)k-12mN+12mN(1-1m)N+16.
Once again, we drop exponentially small terms to get shorter formulæ:
(27)ℰN~2HN-1-2logm+2mN-3+2mNHN-2mNlogm,EN(2)~4(HN-12-HN-1(2))+4mN(HN2-HN(2))-8∑k=1N-1‍1k(1-1m)kHN-1-k+8C1(m)-8C2(m)+4mNHN-4mNlogm-8mN∑k=0N-1‍1N-k(1-1m)k-8mN∑k=1N‍1k(1-1m)kHN-k+8mNC1(m)-8mNC2(m)-12HN-1+12logm-12mN+16.
The asymptotic form is now computed as in the previous section.Theorem 3.
The expectation and variance of the number of comparisons in a successful search related tom binary search trees of altogether N nodes are given by
(28)ℰN=2logNm-3+2γ+O(1N),𝒱N=2logNm-4log2m+4-23π2+2γ+8C1(m)-8C2(m)+O(1N).
More terms in the asymptotic expansions are easily available.


## 4. Internal Path Length

The last parameter that we study is the (internal) path length, namely, the sum of the distances of all the nodes to the root (in the classical case). In them-version, it is simply the sum of the path lengths in the m-individual trees. It is known that the probability generating functions satisfy
(29)gn(z)=zn-1n∑k=1n‍gk-1(z)gn-k(z),g0(z)=1,
whence,
(30)𝒢N(z)=m-N∑n1+⋯+nm=N‍(Nn1,…,nm)×(gn1(z)+⋯+gnm(z))=m-N∑n=0N‍(Nn)(m-1)N-ngn(z).
It is known that
(31)gn′(1)=2(n+1)Hn-4n,gn′′(1)=4(n+1)2(Hn2-Hn(2))-4(n+1)×(4n+1)Hn+n(23n+17).
Therefore, (and again, the extremely long computations are not displayed)
(32)𝒢N′(1)=m-N∑n=0N‍(Nn)(m-1)N-n[2(n+1)Hn-4n]=2m-N(m-1)N-1NTN-1+2-2(1-1m)N+2m-N(m-1)NTN-4Nm=2NmHN-1-2Nm∑k=1N-1‍1k(1-1m)k+2-2(1-1m)N+2HN-2∑k=1N‍1k(1-1m)k-4Nm.
Further,
(33)𝒢N′′(1)=m-N∑n=0N‍(Nn)(m-1)N-n×[4(n+1)2(Hn2-Hn(2))-4(n+1)(4n+1)Hn+n(23n+17)(Hn2-Hn(2))]=8N(N-1)m2(1-1m)N-2UN-2+24Nm×(1-1m)N-1UN-1+8(1-1m)NUN-16N(N-1)m2(1-1m)N-2TN-2-20Nm(1-1m)N-1TN-1+12(1-1m)NTN-8Nm(1-1m)N-1SN-1-16(1-1m)NSN-20+16Nm(1-1m)N-1+20(1-1m)N+8Nm+23N(N-1)m2.
One can now plug in the aforementioned explicit formulæ for S, T, and U, which we do not display, because of length. Instead, we decided to produce an asymptotic formula including terms of order N or higher:
(34)𝒢N′′(1)~8N(N-1)m2(1-1m)N-2×UN-2+24Nm(1-1m)N-1UN-1-16N(N-1)m2(1-1m)N-2TN-2-20Nm(1-1m)N-1TN-1+8Nm+23N(N-1)m2~8N(N-1)m2[HN-22-HN-2(2)2-(logm)HN-2∽8N(N-1)m2+m-1N-2+C1(m)-C2(m)HN-12-HN-1(2)2]+24Nm[HN-12-HN-1(2)2-(logm)HN-1+24Nm+m-1N-1+C1(m)-C2(m)HN-12-HN-1(2)2]-16N(N-1)m2[HN-2-logm]-20Nm×[HN-1-logm]+8Nm+23N(N-1)m2.
Eventually, we arrive at the last result of this paper.Theorem 4.
The expectation and variance of the internal path length ofm binary search trees of altogether N nodes are given by
(35)ℰN=Nm[2logNm+2γ-4m]+O(logN),𝒱N=N2m2[7-23π2+8C1(m)N2m2-8C2(m)-4log2m23]+O(NlogN).
More terms in the asymptotic expansions are easily available.


## 5. Conclusion

This was a first step towards the analysis of them-model of binary search trees. Much more is known about binary search trees and could/should be lifted to that level. Just to mention something explicit, one could look at the depth of node j in an m-binary search tree of N random nodes. The average of this (in the classical case) is due to Arora and Dent [7] and is related to the number of passes that the recursive algorithm Quickselect needs to find the jth largest element, see [8, 9].If one wants to compute higher moments, then one needs to introduce sums like(36)∑k=1n‍(nk)xk∑1≤h<i<j≤k‍1hij,
and similar ones.The quantityC2(m) is related to the dilog function.



---

*Source: 450627-2012-12-19.xml*