<i>m</i>‐ary Search trees when <i>m</i> ≥ 27: A strong asymptotics for the space requirements

Abstract

Abstract It is known that the joint distribution of the number of nodes of each type of an m ‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector X n = t ( X , … , X ), where X denotes the number of nodes containing i − 1 keys after having introduced n − 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that ( X n − nX )/ n − ρ( C cos(τ 2 log n + φ) + S sin(τ 2 log n + φ)) → n →∞ 0 almost surely and in L 2 ; σ 2 and τ 2 denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004