TheAnnalsofAppliedProbability 2008,Vol.18,No.1,288–333 DOI:10.1214/07-AAP457 (cid:13)c InstituteofMathematicalStatistics,2008 A FUNCTIONAL LIMIT THEOREM FOR THE PROFILE 8 0 OF SEARCH TREES 0 2 By Michael Drmota,1 Svante Janson and Ralph Neininger2 n a TU Wien, Uppsala University and J. W. Goethe University J WestudytheprofileX ofrandomsearchtreesincludingbinary 2 n,k 2 search trees and m-ary search trees. Our main result is a functional limit theorem of thenormalized profile Xn,k/EXn,k for k=⌊αlogn⌋ ] in a certain range of α. R Acentralfeatureoftheproofistheuseofthecontractionmethod P toproveconvergenceindistributionofcertainrandomanalyticfunc- . tions in a complex domain. This is based on a general theorem con- h cerning the contraction method for random variables in an infinite- t a dimensional Hilbert space. As part of the proof, we show that the m Zolotarev metric is complete for a Hilbert space. [ 2 1. Introduction. Searchtreesareusedincomputerscienceasdatastruc- v tures that hold data (also called keys) from a totally ordered set in order to 5 support operations on the data such as searching and sorting. After having 8 3 constructed the search tree for a set of keys, the complexity of operations 9 performedonthedataisidentifiedbycorrespondingshapeparametersofthe 0 search tree (examples are given below). Usually, one assumes a probabilistic 6 0 model for the set of data or uses randomized procedures to build up search / trees so that the resulting trees become random and the typical complexity h t of operations can be captured by computing expectations, variances, limit a laws or tail bounds. In this paper, we study the profile of a general class of m random search trees that includes many trees used in computer science such : v as the binary search tree and m-ary search trees with respect to functional i X limit laws. A random binary search tree is constructed for a set of keys as follows. r a One key, the so-called pivot, is chosen uniformly from the set of data and Received September2006; revised June 2007. 1Supportedby theAustrian Science Foundation FWF, project S9604. 2Supportedby an Emmy Noetherfellowship of the DFG. AMS 2000 subject classifications. Primary 60F17; secondary 68Q25, 68P10, 60C05. Key words and phrases. Functionallimittheorem,searchtrees,profileoftrees,random trees, analysis of algorithms. This is an electronic reprint of the original article published by the Institute of Mathematical Statistics in The Annals of Applied Probability, 2008,Vol. 18, No. 1, 288–333. This reprint differs from the original in pagination and typographic detail. 1 2 M. DRMOTA,S.JANSON ANDR.NEININGER Fig. 1. A random binary search tree for the data set {1,2,3,4,5}. In the first step, key 2 is chosen as the pivot. For the right subtree of the root holding the keys {3,4,5}, key 4 is chosen as a pivot. The profile of this tree is (1,2,2,0,0,...). inserted in the root of the tree. All other keys are compared with the pivot. Those which are smaller are used to build a random binary search tree as the left subtree of the root; those which are larger (or equal) than the pivot are used to build the right subtree of the root. For building these subtrees, the procedure is recursively applied. An example is given in Figure 1. For the general class of search trees, explained in Section 2 and studied in this paper, this construction rule is generalized so that nodes may hold m 1 1keysandhavemsubtreesand,further,theruletochoosethepivots − ≥ may be more general, resulting in more balanced trees as a parameter t 0 ≥ is increased; see Section 2. For example, if m=2, then the pivot is chosen as the median of 2t+1 random elements. This more general search tree model reduces to the binary search tree for the choice (m,t)=(2,0). Thedepth of akey in the tree is its node’sdistance to the rootof thetree. This quantity is a measure of the complexity involved in searching for the number inserted in that node. Other quantities, important in the context of computer science, are the internal path length of the tree, which is the sum of the depths of all keys, and the height of the tree, which is the maximal depth in the tree. In this paper, we study the profile of search trees, which is the infinite vector X =(X ) , where X is the number of keys that are stored in n n,k k≥0 n,k nodes with depth k. The profile of binary search trees (and related structures) has been in- tensively studied in the literature [4, 6, 7, 8, 10, 11, 12, 15, 17, 25]. Most results concern 1st and 2nd moments. However, there are also distributional results, particularly for binary search trees and recursive trees [4, 6, 15] that are of the form X n,⌊αlogn⌋ d X(α) EX −→ n,⌊αlogn⌋ A FUNCTIONAL LIMIT THEOREMFOR THE PROFILEOF SEARCHTREES 3 for fixed α (contained inasuitableinterval). Theadvantage ofbinarysearch trees and recursive trees is that there is an underlying martingale structure whichalsoallowsfunctionallimittheoremstobeproven(see[4,6]forbinary search trees). Unfortunately, this martingale structure is (generally) missing in the kind of trees that we want to study. Our main result is the following, where we actually prove functional con- vergence of random functions on an interval I′. More precisely, we use the spaceD(I′)ofright-continuousfunctionswithleft-handlimitsequippedwith the Skorohod topology; see Section 4 for the definition and note that when, as here, the limit is continuous, convergence in the Skorohod topology is equivalent to uniform convergence on every compact subinterval. In the formulation of Theorem 1.1, we also use the function λ (z), de- 1 fined in Section 3 as the dominant root of (3.4), and the stochastic process (Y(z),z B) (of analytic functions in a certain domain B containing the ∈ interval I) that is defined as the unique solution of a stochastic fixed point equation (3.7) which is discussed in Section 9, satisfying the further condi- tions that EY(z)=1 and that for each x I, there exists an s(x)>1 such ∈ that E Y(z)s(x) is finite and bounded in a neighborhood of x. | | Theorem 1.1. Let m 2 and t 0 be given integers and let (X ) n,k k≥0 ≥ ≥ be the profile of the corresponding random search tree with n keys. Set I = β > 0:1<λ (β2)<2λ (β) 1 , I′ = βλ′(β):β I and let { 1 1 − } { 1 ∈ } β(α)>0 be defined by β(α)λ′(β(α))=α. We then have, in D(I′), that 1 X (1.1) n,⌊αlogn⌋ ,α I′ d (Y(β(α)),α I′). EX ∈ −→ ∈ (cid:18) n,⌊αlogn⌋ (cid:19) Remark 1.1. From the definitions of I and I′, it is not clear that they are in fact intervals. We will make this precise in Lemma 8.5. Remark 1.2. In exactly the same way, one can consider other similarly defined parameters. For example, in Section 11, we discuss the external profile. TheproofofTheorem1.1isdividedintoseveralsteps.Afterdefiningsuit- able function spaces (Section 4), we show (Section 9) the following theorem, which states that if W (z):= X zk are the profile polynomials, then n k n,k the normalized profile polynomials W (z)/EW (z) converge weakly to Y(z) P n n for z contained in a suitable complex region B, where Y(z) is, as above, the solution of a stochastic fixed point equation (3.7). Note that convergence in (B) means uniform convergence on every compact subset of B. H 4 M. DRMOTA,S.JANSON ANDR.NEININGER Theorem 1.2. There exists a complex region B that contains the real interval (1/m,β(α )), where α is defined in (1.3), and an analytic stochas- + + tic process (Y(z),z B) satisfying (3.7) and EY(z)=1, such that, in (B), ∈ H W (z) n d (1.2) ,z B (Y(z),z B). EW (z) ∈ −→ ∈ (cid:18) n (cid:19) Finally, we apply a suitable continuous functional (which is related to Cauchy’s formula) in order to derive Theorem 1.1 from this property (Sec- tion 10). Important tools in this argument are Theorems 5.1 and 6.1, which show that one can use the contraction method with the Zolotarev metric ζ for s random variables with values in a separable Hilbert space. (We do not know whether these theorems extend to arbitrary Banach spaces.) In the special case of binary search trees, Theorems 1.1 and 1.2 have been proven earlier, also in stronger versions [4, 6, 7]. Before we go into the details, we wish to comment on the interval I of Theorem 1.1. It is well known that the height of random search trees is of order logn. Thus, it is natural that there might be a restriction on the parameter α=k/logn, where k denotes the depth. In fact, there are several critical values for α=k/logn, namely 1 1 1 −1 α=α := + + + ; 0 • t+1 t+2 ··· (t+1)m 1 (cid:18) − (cid:19) 1 1 1 −1 α=α := + + + ; max • t+2 t+3 ··· (t+1)m (cid:18) (cid:19) α=α , where α >α is the solution of the equation + + 0 • (1.3) λ (β(α)) αlog(β(α)) 1=0. 1 − − In order to explain these critical values, we must look at the expected profile EX . If α=k/logn α ε (for some ε>0), then n,k 0 ≤ − EX (m 1)mk, n,k ∼ − whereas if α=k/logn α +ε, then 0 ≥ E(β(α))nλ1(β(α))−αlog(β(α))−1 EX n,k ∼ 2π(α+β(α)2λ′′(β(α)))logn 1 q for some continuous function E(z); see Lemma 8.3. This means that up to level k=α logn, the tree is (almost) complete. Note that the critical value 0 k/logn=α corresponds to z=β=1/m and λ (1/m)=1, and thus that 0 1 nλ1(β(α0))−α0log(β(α0))−1=nα0logm=mk. A FUNCTIONAL LIMIT THEOREMFOR THE PROFILEOF SEARCHTREES 5 We can be even more precise. If α=k/logn [ε,α ε], then 0 ∈ − EX =(m 1)mk r , n,k n,k − − with E (β(α))nλ1(β(α))−αlog(β(α))−1 1 r n,k ∼ 2π(α+β(α)2λ′′(β(α)))logn 1 q for some continuous function E (z). 1 The second critical value k/logn=α corresponds to z =β =1 and max λ (1)=2. Here, we have 1 n (k α logn)2 EX exp − max n,k∼ 2π(αmax+λ′1′(1))logn (cid:18)−2(αmax+λ′1′(1))logn(cid:19) q [uniformly for k=α logn+O(√logn)]. This means that most nodes are max concentrated around that level. In fact, α logn is the expected depth. max Finally, if α=k/logn<α , then EX and if α=k/logn>α , + n,k + then EX 0. This means that the range →α=∞k/logn (0,α ) is exactly n,k + → ∈ the range where the profile X is actually present. n,k We also see that the interval I′ of Theorem 1.1 is strictly contained in (α ,α ), but we have α I′. This means that we definitely cover the 0 + max ∈ most important range. However, it seems that Theorem 1.1 is not optimal. The condition λ (β2)<2λ (β) 1 comes from the fact that we are using L2 1 1 − techniques in order to derive Theorem 1.1 from Theorem 1.2. We conjecture that this is just a technical restriction and that Theorem 1.1 actually holds for α (α ,α ). 0 + ∈ Incidentally, r has a similar critical value α <α that is the second n,k − 0 positive solution of (1.3). If α < α , then r 0 and if α > α , then − n,k − → r . The two constants α ,α are related to the speed of the leftmost n,k − + →∞ and rightmost particles in suitable discrete branching random walks (see [5]). Note that they can be also computed by (t+1)(m−1)−1 −1 1 α = − j=0 λ−+t+j! X and (t+1)(m−1)−1 −1 1 α = , + j=0 λ++t+j! X where λ and λ are the two solutions of − + (t+1)(m−1)−1 log(λ+t+j) log(m(tm+m 1)!/t!) − − j=0 X 6 M. DRMOTA,S.JANSON ANDR.NEININGER (1.4) (t+1)(m−1)−1 λ 1 = − . λ+t+j j=0 X Further, the expected height of m-ary search trees satisfies EH α logn n + and the expected saturation level EH˜ α logn. ∼ n − ∼ Notation. Iff andg aretwofunctionsonthesamedomain,then f .g means the same as f =O(g), that is, f Cg for some constant C. | |≤ 2. Randomsearch trees. Todescribetheconstruction of thesearch tree, we begin with the simplest case t=0. If n=0, the tree is empty. If 1 n ≤ ≤ m 1, the tree consists of a root only, with all keys stored in the root. − If n m, we randomly select m 1 keys that are called pivots (with the ≥ − uniform distribution over all sets of m 1 keys). The pivots are stored in − the root. The m 1 pivots split the set of the remaining n m+1 keys − − into m subsets I ,...,I : if the pivots are x <x < <x , then I := 1 m 1 2 m−1 1 ··· x :x <x , I := x :x <x <x ,...,I := x :x <x . We then i i 1 2 i 1 i 2 m i m−1 i { } { } { } recursively construct a search tree for each of the sets I of keys (ignoring I i i if it is empty) and attach the roots of these trees as children of the root in the search tree. In the case m=2, t=0, we thus have the well-studied binary search tree [4, 6, 7, 11, 12, 15, 26]. In the case t 1, the only difference is that the pivots are selected in a ≥ different way, which affects the probability distribution of the set of pivots and thus of the trees. We now select mt+m 1 keys at random, order them − as y < <y and let the pivots be y ,y ,...,y . In 1 mt+m−1 t+1 2(t+1) (m−1)(t+1) ··· the case m n<mt+m 1, when this procedure is impossible, we select ≤ − the pivots by some supplementary rule (possibly random, but depending only on the order properties of the keys); our results do not depend on the choice of this supplementary rule. This splitting procedure was first introduced by Hennequin for the study of variants of the Quicksort algorithm and is referred to as the generalized Hennequin Quicksort (cf. Chern, Hwang and Tsai [9]). In particular, in the case m=2, we let the pivot be the median of 2t+1 randomly selected keys (when n 2t+1). Wedescribethesplittingofthe≥keysbytherandomvectorV =(V ,V , n n,1 n,2 ...,V ),whereV := I isthenumberofkeysinthekthsubsetandthus n,m n,k k | | the number of nodes in the kth subtree of the root (including empty sub- trees). We thus always have, provided n m, ≥ V +V + +V =n (m 1)=n+1 m n,1 n,2 n,m ··· − − − A FUNCTIONAL LIMIT THEOREMFOR THE PROFILEOF SEARCHTREES 7 and elementary combinatorics, counting the number of possible choices of the mt+m 1 selected keys, shows that the probability distribution is, for − n mt+m 1 and n +n + +n =n m+1, 1 2 m ≥ − ··· − n1 nm (2.1) P V =(n ,...,n ) = t ··· t . { n 1 m } n (cid:0) m(cid:1)t+m(cid:0)−1 (cid:1) (The distribution of V for m n<mt+m(cid:0) 1 is no(cid:1)t specified.) n ≤ − In particular, for n mt+m 1, the components V are identically n,j ≥ − distributedandanothersimplecountingargumentyields,forn mt+m 1 ≥ − and 0 ℓ n 1, ≤ ≤ − ℓ n−ℓ−1 (2.2) P V =ℓ = t (m−1)t+m−2 . { n,j } (cid:0) (cid:1)(cid:0) n (cid:1) mt+m−1 For example, for the binary search t(cid:0)ree with(cid:1)m=2 and t=0, we thus have V and V =n 1 V uniformly distributed on 0,...,n 1 . n,1 n,2 n−1 − − { − } 3. The profile polynomial. The recursive construction of the random search tree in Section 2 leads to a recursion for the profile X =(X ) : n n,k k≥0 d (1) (2) (m) (3.1) X =X +X + +X , n,k Vn,1,k−1 Vn,2,k−1 ··· Vn,m,k−1 jointly in k 0 for every n m, where the random vector V =(V ,V , n n,1 n,2 ≥ ≥ ...,V ) is as in Section 2 and is the same for every k 0, and X(j) = n,m n ≥ (X(j)) , j=1,...,m, are independentcopies of X that are also indepen- n,k k≥0 n dent of V . We further have X =m 1 for n m. For n m 1, we n n,0 − ≥ ≤ − simply have X =n and X =0, k 1. n,0 n,k Note that, by induction, X =0 wh≥en k n. Hence, each vector X has n,k n ≥ only a finite number of nonzero components. Let W (z)= X zk denote the random profile polynomial. By (3.1), n k n,k it is recursively given by W (z)=n for n m 1 and n P ≤ − d (1) (2) (m) (3.2) W (z)=zW (z)+zW (z)+ +zW (z)+m 1, n m, n Vn,1 Vn,2 ··· Vn,m − ≥ (j) where W (z), j=1,...,m, are independent copies of W (z) that are inde- ℓ ℓ pendent of V , ℓ 0. From this relation, we obtain a recurrence for the ex- n pected profilepoly≥nomial EW (z). We have, using(2.2),for n mt+m 1, n ≥ − n−1 ℓ n−ℓ−1 (3.3) EW (z)=mz t (m−1)t+m−2 EW (z)+m 1. n (cid:0) (cid:1)(cid:0) n (cid:1) ℓ − ℓ=0 mt+m−1 X For any fixed complex z, this is a(cid:0) recursi(cid:1)on of the type studied in Chern, Hwang and Tsai [9]. More precisely, it fits ([9], (13)) with a =EW (z), n n 8 M. DRMOTA,S.JANSON ANDR.NEININGER r=mt+m 1 and c =mzr!/t!, while c =0 for j=t. Further, b =m 1 t j n − 6 − for n mt+m 1, while b =a =EW (z) for n<mt+m 1. n n n ≥ − − It follows from [9] that the asymptotics of EW (z) as n depend on n →∞ the roots of the indicial polynomial (mt+m 1)! Λ(θ;z):=θmt+m−1 mz − θt − t! (3.4) =θ(θ+1) (θ+mt+m 2) ··· − (mt+m 1)! mz − θ(θ+1) (θ+t 1) − t! ··· − using the notation xm:=x(x+1) (x+m 1)=Γ(x+m)/Γ(x). If we set ··· − t! (3.5) F(θ):= (θ+t)(θ+t+1) (θ+mt+m 2), m(mt+m 1)! ··· − − then m(mt+m 1)! Λ(θ;z)= − θt(F(θ) z), t! − which implies that the roots of Λ(λ;z)=0 are 0, 1, 2,..., t+1 (if t − − − ≥ 1) together with the roots of F(θ)= z. Let λ (z), j = 1,...,(m 1)(t+ j − 1), denote the roots of F(θ)=z (counted with multiplicities), arranged in decreasing order of their real parts: λ (z) λ (z) . 1 2 ℜ ≥ℜ ≥··· Further,letD ,forreals,bethesetofallcomplex z suchthat λ (z)>s s 1 ℜ and λ (z)> λ (z) [in particular, λ (z) is a simple root]. It is easily seen 1 2 1 ℜ ℜ that the set D is open and that λ (z) is an analytic function of z D . If s 1 s ∈ z D is real, then λ (z) must be real (and thus greater than s) because s 1 ∈ otherwise, λ (z) would be another root with the same real part. 1 By [9], Theorem 1(i), we have the following result. Note that K and K 0 1 [our E(z)] in [9], Theorem 1(i), are analytic functions of z and λ , and thus 1 of z D , and that they are positive for λ >0 because b =m 1>0 for 1 1 k ∈ − k mt+m 1and b =EW (z) 0 for smaller k. (See also Lemma 8.2 and k k ≥ − ≥ the Appendix.) Lemma 3.1. If z D , then 1 ∈ EW (z)=(E(z)+o(1))nλ1(z)−1 n for some analytic function E(z) with E(z)>0 for z D (0, ). 1 ∈ ∩ ∞ Lemma 3.2. The set D is an open domain in the complex plane that 1 contains the interval (1/m, ). ∞ A FUNCTIONAL LIMIT THEOREMFOR THE PROFILEOF SEARCHTREES 9 [Lemma 3.2 will be proven in a more general context in Lemma 8.1. Note that F(1)=1/m and thus λ (1/m)=1.] 1 Set M (z)=W (z)/G (z), where G (z) =EW (z). Then (3.2) can be n n n n n rewritten as G (z) G (z) m 1 M (z)=d Vn,1 zM(1) (z)+ + Vn,m zM(m) (z)+ − . n G (z) Vn,1 ··· G (z) Vn,m G (z) n n n Note that G (z), where V is an integer-valued random variable, is con- V sidered as therandom variable EW (z) and notas EW (z), that is, the n n=V V expected value is only taken with respe|ct to X . Next, let the random vec- n tor V=(V ,V ,...,V )besupportedonthesimplex ∆= (s ,...,s ):s 1 2 m 1 m j { ≥ 0,s + +s =1 with density 1 m ··· } ((t+1)m 1)! f(s ,...,s )= − (s s )t, 1 m (t!)m 1··· m where t 0 is the same integer parameter as above. (This is known as a ≥ Dirichlet distribution.) It is easy to show that 1 (3.6) V d V as n . n n −→ →∞ Remark 3.1. For n mt+m 1, the shifted random vector (V n,1 ≥ − − t,...,V t) has a multivariate Po´lya–Eggenberger distribution that can n,m − bedefinedasthedistributionofthevectorofthenumbersofballsofdifferent color drawn in the first n (mt+m 1) draws from an urn with balls of m − − colors, initially containing t+1 balls of each color, where we draw balls at random and replace each drawn ball together with a new ball of the same color (see, e.g., Johnson and Kotz [20], Section 4.5.1). This distribution can be obtained by first taking a random vector V with the Dirichlet distribution above and then a multinomial variable with parameters n (mt+m 1) and V ([20], Section 4.5.1). Using this repre- − − sentation, (3.6) follows immediately from the law of large numbers, even in the stronger form V /n a.s. V. n −→ It follows from (3.6) and Lemma 3.1 that G (z) Vn,j d Vλ1(z)−1 G (z) −→ j n if z D and E(z)=0. Hence, if M (z) has a limit (in distribution) Y(z) 1 n ∈ 6 for some z D with E(z)=0, then this limit must satisfy the stochastic 1 ∈ 6 fixed point equation Y(z)=d zVλ1(z)−1Y(1)(z)+zVλ1(z)−1Y(2)(z)+ +zVλ1(z)−1Y(m)(z), 1 2 ··· m (3.7) 10 M. DRMOTA,S.JANSON ANDR.NEININGER where Y(j)(z) are independent copies of Y(z) that are independent of V. [Note that z D and E(z)=0 imply that G (z) .] 1 n ∈ 6 →∞ In Section 9, we will show that this limit relation is actually true in a suitable domain, even in a strong sense, as asserted in Theorem 1.2. We will alsoseethatwehaveauniquesolutionofthisstochasticfixedpointequation under the assumption EY(z)=1 and a certain integrability condition. 4. Function spaces. For functions defined on an interval I R, we use ⊆ the space D(I) of right-continuous functions with left-hand limits equipped with the Skorohod topology. A general definition of this topology is that f f as n if and only if there exists a sequence λ of strictly increas- n n → →∞ ing continuous functions that map I onto itself such that λ (x) x and n → f (λ (x)) f(x), uniformly on every compact subinterval of I; see, for ex- n n → ample, [2], Chapter 3, (I =[0,1]), [24], [18], Chapter VI, [21], Appendix A2 ([0, )), [19], Section 2. It is of technical importance that this topology ∞ can be induced by a complete, separable metric [2], Chapter 14, [18], Theo- rem VI.1.14, [21], Theorem A2.2. Note that it matters significantly whether or not the endpoints are included in the interval I, but we can always re- duce to the case of compact intervals because f f in D(I) if and only n → if f f in D(J ) for an increasing sequence of compact intervals J with n k k → J =I. In particular, when f is continuous, f f in D(I) if and only if k n → f f uniformly on every compact subinterval. Similarly, if F and F are Sn→ n d random elements of D(I) and F is a.s. continuous, then F F in D(I) n −→ d if and only if F F in D(J) for every compact subinterval J I. n −→ ⊆ For analytic functions on a domain (i.e., a nonempty open connected set) D C, we will use two topological vector spaces. ⊆ (D) is the space of all analytic functions on D with the topology of • H uniform convergence on compact sets. This topology can be defined by the family of seminorms f sup f , where K ranges over the compact 7→ K| | subsets of D. (D) is a Fr´echet space, that is, a locally convex space H with a topology that can be defined by a complete metric, and it has (by Montel’s theorem on normal families) the property that every closed bounded subset is compact (see, e.g., [28], Chapter 1.45, or [29], Example 10.II and Theorem 14.6). It is easily seen that the topology is separable [e.g., by regarding (D) as a subspace of C∞(D)]. H 0 (D) is the Bergman space of all square-integrable analytic functions on • B D, equipped with the norm given by f 2 = f(z)2dm(z), where k kB(D) D| | m is the two-dimensional Lebesgue measure. (D) can be regarded as a R B closed subspace of L2(R2) and is thus a separable Hilbert space (see, e.g., [22], Chapter 1.4).