m-ary Search trees whenm ? 27: A strong asymptotics for the space requirements
2004; Wiley; Volume: 24; Issue: 2 Linguagem: Inglês
10.1002/rsa.10108
ISSN1098-2418
AutoresBrigitte Chauvin, Nicolas Pouyanne,
Tópico(s)Algorithms and Data Compression
ResumoAbstract 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
Referência(s)