The space requirement of m-ary search trees: distributional asymptotics for m >= 27
arXiv:math/0405144
Abstract
We study the space requirement of -ary search trees under the random permutation model when is fixed. Chauvin and Pouyanne have shown recently that , the space requirement of an -ary search tree on keys, equals , where and are certain constants, is a complex-valued random variable, and a.s. and in as . Using the contraction method, we identify the distribution of .
arXiv comment10 pages, 1 figure
Cited by in corpus (7)
- Polya urns via the contraction method
- An algebraic approach to Polya processes
- Degree profile of -ary search trees: A vehicle for data structure compression
- Limit distributions for multitype branching processes of m-ary search trees
- Smoothing equations for large Pólya urns
- Solutions to complex smoothing equations
- Central limit theorem analogues for multicolour urn models