Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T10:47:23.177Z Has data issue: false hasContentIssue false
  • English
  • Français

Distribution of the Steiner Distance in Generalized M-ary Search Trees

Published online by Cambridge University Press:  24 September 2004

ALOIS PANHOLZER
ALOIS PANHOLZER
Affiliation:
Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Wiedner Hauptstraße 8–10, A-1040 Wien, Austria (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we show for generalized $M$-ary search trees that the Steiner distance of $p$ randomly chosen nodes in random search trees is asymptotically normally distributed. The special case $p=2$ shows, in particular, that the distribution of the distance between two randomly chosen nodes is asymptotically Gaussian. In the presented generating functions approach, we consider first the size of the ancestor-tree of $p$ randomly chosen nodes. From the obtained Gaussian limiting distribution for this parameter, we deduce the result for the Steiner distance. Since the size of the ancestor-tree is essentially the same as the number of passes in the (generalized) Multiple Quickselect algorithm, the limiting distribution result also holds for this parameter.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 13 , Issue 4-5 , July 2004 , pp. 717 - 733
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)