Mathematics – Probability
Scientific paper
2003-04-25
Mathematics
Probability
119 pages, 13 figures. This is a single-spaced version. The original is double-spaced
Scientific paper
Search trees are fundamental data structures in computer science. We study functionals on random search trees that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so-called shape functional fall under this framework. Our goal is to derive asymptotics of moments and identify limiting distributions of these functionals under two commonly studied probability models -- the random permutation model and the uniform model. For the random permutation model, our approach is based on establishing transfer theorems that link the order of growth of the input into a particular deterministic recurrence to the order of growth of the output. For the uniform model, our approach is based on the complex-analytic tool of singularity analysis. To facilitate a systematic analysis of these additive functionals we extend singularity analysis, a class of methods by which one can translate on a term-by-term basis an asymptotic expansion of a functional around its dominant singularity into a corresponding expansion for the Taylor coefficients of the function. The most important extension is the determination of how singularities are composed under the operation of Hadamard product of analytic power series. The transfer theorems derived are used in conjunction with the method of moments to establish limit laws for m-ary search trees under the random permutation model. For the uniform model on binary search trees, the extended singularity analysis toolkit is employed to establish the asymptotic behavior of the moments of a wide class of functionals. These asymptotics are used, again in conjunction with the method of moments, to derive limit laws.
No associations
LandOfFree
Additive functionals on random search trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Additive functionals on random search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Additive functionals on random search trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-699151